Boyd, Stephen and Diaconis, Persi and Parrilo, Pablo and Xiao, Lin (2008) Symmetry Analysis of Reversible Markov Chains. Internet Mathematics , 2 (1). pp. 31-71. ISSN 1944-9488 http://resolver.caltech.edu/CaltechAUTHORS:20110602-133842599
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110602-133842599
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.|
|Official Citation:||Symmetry Analysis of Reversible Markov Chains Internet Mathematics Volume 2, Issue 1, 2008, Pages 31 - 71 Authors: Stephen Boyda; Persi Diaconisb; Pablo Parriloc; Lin Xiaod DOI: 10.1080/15427951.2005.10129100|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||02 Jun 2011 21:13|
|Last Modified:||02 Jun 2011 21:13|
Repository Staff Only: item control page