Sept 17, 2025, 1300 (HK/SG/CN)
Speaker: Michael Choi (NUS).
Title: Improving the convergence of Markov chains via permutations and projections
Abstract: This talk aims to improve the convergence to equilibrium of finite Markov chains via permutations and projections. First, we prove that a specific mixture of permuted Markov chains arises naturally as a projection under the KL divergence or the squared-Frobenius norm. We then compare various mixing properties of the mixture with other competing Markov chain samplers and demonstrate that it enjoys improved convergence. This geometric perspective motivates us to propose samplers based on alternating projections to combine different permutations and to analyze its rate of convergence. We give necessary, and under some additional assumptions, also sufficient, conditions for the projection to achieve stationarity in the limit in terms of a trace of the transition matrix. We proceed to discuss tuning strategies of the projection samplers when these permutations are viewed as parameters. Along the way, we reveal connections between the mixture and a Markov chain Sylvester's equation and assignment problems, highlighting how these can be used to understand and improve Markov chain mixing. Finally, we provide numerical experiments on simple statistical physics models to illustrate the improved performance of projection samplers. This is based on joint work with Max Hird (UCL) and Youjia Wang (NUS).