Symmetry Analysis of Reversible Markov Chains

S. Boyd, P. Diaconis, P. Parrilo, and L. Xiao (listed in alphabetical order)

Internet Mathematics, 2(1):31-71, 2005.

We show how to use subgroups of the symmetry group of a reversible Markov chain to give useful bounds on eigenvalues and their multiplicity. We supplement classical representation theoretic tools involving a group commuting with a self-adjoint operator with criteria for an eigenvector to descend to an orbit graph. As examples, we show that the Metropolis construction can dominate a max-degree construction by an arbitrary amount and that, in turn, the fastest mixing Markov chain can dominate the Metropolis construction by an arbitrary amount.