Symmetry Analysis of Reversible Markov Chains

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

Abstract

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.

Details

Publication typeArticle
Published inInternet Mathematics
URLhttp://stanford.edu/~boyd/papers/symmetry.html
Pages31-71
Volume2
Number1
> Publications > Symmetry Analysis of Reversible Markov Chains