Fastest Mixing Markov Chain on a Path

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

January 2006

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

Publication type | Article |

Published in | The American Mathematical Monthly |

Pages | 70-74 |

Volume | 113 |

Number | 1 |

- Energy-aware server provisioning and load dispatching for connection-intensive internet services
- Fast Linear Iterations for Distributed Averaging
- Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback

> Publications > Fastest Mixing Markov Chain on a Path