Symmetry analysis of reversible markov chains

Stephen Boyd, Persi Diaconis, Pablo Parrilo, Lin Xiao

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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.

Original languageEnglish
Pages (from-to)31-71
Number of pages41
JournalInternet Mathematics
Volume2
Issue number1
DOIs
StatePublished - Jan 1 2005
Externally publishedYes

Fingerprint

Dive into the research topics of 'Symmetry analysis of reversible markov chains'. Together they form a unique fingerprint.

Cite this