Symmetry Analysis of Reversible Markov Chains

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.

symmetry.pdf
PDF file

In  Internet Mathematics

Details

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