Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Fastest Mixing Markov Chain on a Path

Stephen Boyd, Perci Diaconis, Jun Sun, and Lin Xiao

Abstract

We consider a random walk on a path with n nodes, with symmetric transition probabilities, i.e., the probability of making a transition between node i and node i+1 is the same as making a transition from node i+1 to node i. For such a Markov chain the uniform distribution is an equilibrium distribution, and the rate of convergence of the distribution to uniform is determined by the smallest second-largest eigenvalue magnitude of the associated transition matrix. We address the question: What choice of transition probabilities results in the fastest mixing Markov chain on the path? This question can be posed in terms of matrices as: Among all symmetric, stochastic, tridiagonal matrices, what is the minimum value the second-largest eigenvalue magnitude can attain? In this note we prove that fastest mixing is obtained when we assign at each node a probability 1/2 of moving to the left, 1/2 of moving to the right, and a probability 1/2 of remaining at the two boundary nodes. The optimal second-largest eigenvalue magnitude is given by cos(pi/n).

Details

Publication typeArticle
Published inThe American Mathematical Monthly
Pages70-74
Volume113
Number1
> Publications > Fastest Mixing Markov Chain on a Path