Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2008 | public
Journal Article

Symmetry Analysis of Reversible Markov Chains

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.

Additional Information

© 2005 A. K. Peters, Ltd. Received December 6, 2003; accepted May 21, 2004. We thank Daniel Bump, Robin Forman, Mark Jerrum, Arun Ram, and Andrez Zuk for incisive contributions to this paper.

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023