Fastest Mixing Markov Chain on a Path

The American Mathematical Monthly, 113(1):70-74, January 2006.

• fmmc_path.pdf

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).