Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Symmetry Analysis of Reversible Markov Chains

Stephen Boyd, Persi Diaconis, Pablo Parrilo, and Lin Xiao


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.


Publication typeArticle
Published inInternet Mathematics
> Publications > Symmetry Analysis of Reversible Markov Chains