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 isP. 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 toP. Diaconis, S. Holmes andR. 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 alsoS. Boyd, P. Diaconis andL. Xiao [SIAM Rev. 46, No. 4, 667–689 (2004;Zbl 1063.60102)].

Reviewer: Fabio Scarabotti (Roma)