×

Mixing times for Markov chains on wreath products and related homogeneous spaces. (English) Zbl 0976.60069

Summary: We develop a method for analyzing the mixing times for a quite general class of Markov chains on the complete monomial group \(G \wr S_n\) and a quite general class of Markov chains on the homogeneous space \((G \wr S_n) / (S_r \times S_{n-r})\). We derive an exact formula for the \(L^2\) distance in terms of the \(L^2\) distances to uniformity for closely related random walks on the symmetric groups \(S_j\) for \(1 \leq j \leq n\) or for closely related Markov chains on the homogeneous spaces \(S_{i+j}/(S_i\times S_j)\) for various values of \(i\) and \(j\), respectively. Our results are consistent with those previously known, but our method is considerably simpler and more general.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
20E22 Extensions, wreath products, and other compositions of groups
60B10 Convergence of probability measures
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML EMIS