Symmetry Analysis of Reversible Markov Chains
Let \(G\) be a finite group acting on a finite set \(X\). Let \(\{P(x,y)\}_{x,y\in X}\) be the transition kernel of a reversible Markov chain on \(X\). We say that \(P\) is \(G\)-invariant when \(P(gx,gy)=P(x,y)\) for all \(g\in G,x,y\in X\). A standard way to get the spectrum of \(P\) is to use the representation theory of \(G\). The case in which \(G\) is transitive on \(X\) has been extensively studied; the best reference on this subject is \textit{P. Diaconis} [``Group representations in probability and statistics (1988; Zbl 0695.60012)]. The case in which \(G\) is not transitive is less known; as a limiting case (i.e. \(G\) is the trivial group) it contains the spectral analysis of an arbitrary reversible Markov chain and even the case \(G=C_2\) is interesting and worth studying it leads to various trigonometric transforms and to the diagonalization of various Markov chains on the path \(\{0,1,\ldots,n\}\) (this is carefully explained in the paper under review). If \(X=O_1\cup O_2\cup\cdots\cup O_n\) is the decomposition of \(X\) into the orbits of \(G\), then one can define an orbit chain on \(\{O_1,O_2,\dots, O_n\}\) by setting \[ P_G(O_i,O_j)=\sum_{v\in O_j}P(u_i,v) \] where \(u_i\) is any point in \(O_i\). The orbit chain does not necessarily contain all the eigenvalues of the original chain; neverthless, in the paper under review the authors develop an orbit chain theory that leads them to prove the following important result: if \(H_i\) is the stabilizer of a point in \(O_i\) (that is \(O_i=G/H_i\)) and \(P_{H_i}\) is the orbit chain relative to the action of \(H_i\) on \(X\) then all the eigenvalues of \(P\) occur among the eigenvalues of the transition matrices \(\{P_{H_i}\}_{i=1,2,\ldots,n}\). Then they apply this result to the simple random walk on two graphs with nontransitive isometry group. The first is a flower with \(M\) petals obtained by taking \(m\) copies of the discrete circle \(C_n\) (the standard Cayley graph of the finite cyclic group) and joining them at the vertex \(0\). The second is the graph obtained by taking two copies of the complete graph \(K_n\) (with a loop at each vertex) and joining them by an extra edge (that connects a point in the first copy with a point in the second copy). In the first case, the isometry group is the wreath product \(C_2\wr S_n\) (the hyperoctahedral group); in the second case it is \(S_{n-1}\wr C_2\). A complete spectral analysis is given for both examples and it is applied to the computation of the rate of convergence to the stationary distribution. In the first case an unusual phenomenon occurs: in the \(L^2\) norm order \(n^2\log m\) are necessary and sufficient to achieve stationarity, while in the \(L^1\) (or total variation) norm the relaxation time has order \(n^2\), independent of \(m\) (for another example of discrepancy between \(L^1\) and \(L^2\) rates of convergences we refer to \textit{P. Diaconis, S. Holmes} and \textit{R. M. Neal} [Ann. Appl. Probab. 10, No.~3, 726--752 (2000; Zbl 1083.60516)]). The last section of the paper is devoted to the analysis of two different Markov chains on the flower, the max-degree chain and the Metropolis chain; both the chains have uniform stationarity distribution. The authors use symmetry analysis and geometric techniques to give sharp bounds on the spectral gap of both chains. They show that the spectral gap for the max-degree chain is a factor of \(\min\{n,m\}\) times smaller than the spectral gap for the Metropolis chain. They also discuss the fastest mixing Markov chain on the flower; see also \textit{S. Boyd, P. Diaconis} and \textit{L. Xiao} [SIAM Rev. 46, No.~4, 667--689 (2004; Zbl 1063.60102)].
- Spectral analysis of finite Markov chains with spherical symmetries
- Geometric ergodicity and the spectral gap of non-reversible Markov chains
- Examples of Markov chains on spaces with multiplicities
- Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
- Spectral theory for weakly reversible Markov chains
- Reproducing kernel orthogonal polynomials on the multinomial distribution
- Spectral analysis of finite Markov chains with spherical symmetries
- Communication constraints in the average consensus problem
- Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler
- Fast linear iterations for distributed averaging
- Radon transforms and lamplighter random walks
- Involutive random walks on total orders and the anti-diagonal eigenvalue property
- Invariant Semidefinite Programs
- Fastest mixing Markov chain problem for the union of two cliques
- Aspects of large random Markov kernels
- Composition Markov chains of multinomial type
- The lumpability property for a family of Markov chains on poset block structures
- An introduction to multivariate Krawtchouk polynomials and their applications
- Remarks and open problems on the minimum permanent of acyclic doubly stochastic matrices
- Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009))
- Examples of Markov chains on spaces with multiplicities
- A rule of thumb for riffle shuffling
- Double coset Markov chains
- Harmonic analysis of finite lamplighter random walks
- Geometric bounds on the fastest mixing Markov chain
- Caged Markov process -- a continuous-time framework for modeling a constrained Markov process within a freely-evolving Markov process
- The Dirichlet Markov ensemble
- Inequalities for the spectra of symmetric doubly stochastic matrices
This page was built for publication: Symmetry Analysis of Reversible Markov Chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5700147)
