Fastest Mixing Markov Chain on a Path

We consider the problem of assigning transition probabilities to the edges of a path, so the resulting Markov chain or random walk mixes as rapidly as possible. In this note we prove that fastest mixing is obtained when each edge has a transition probability of 1/2. Although this result is intuitive (it was conjectured in [7]), and can be found numerically using convex optimization methods [2], we give a self-contained proof. In [2], the authors consider the problem of assigning transition probabilities to the edges of a connected graph in such a way that the associated Markov chain mixes as rapidly as possible. We show that this problem can be solved, at least numerically, using tools of convex PSfrag optimization, replacements in particular, semidefinite programming [9, 3]. The present note presents a simple, self contained example where the optimal Markov chain can be identified analytically. Consider a path with n ≥ 2 nodes, labeled 1, 2,..., n, with n − 1 edges connecting pairs of adjacent nodes, and a loop at each node, as shown in figure 1. We consider a Markov chain (or random walk) on this path, with transition probability from node i to node j denoted Pij. The requirement that transitions can only occur along an edge or loop of the path is