Mixing Times for Markov Chains on Wreath Products and Related Homogeneous Spaces
Clyde H. Schoolfield, Jr. (Harvard University)
Abstract
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.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-22
Publication Date: April 23, 2001
DOI: 10.1214/EJP.v6-84
References
- Aldous, D. and Fill, J.A. (200x), Reversible Markov Chains and Random Walks on Graphs. Book in preparation. Draft of manuscript available. Math. Review number not available.
- Diaconis, P.(1988), Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA. Math. Review 90a:60001
- Diaconis, P. and Saloff-Coste, L. (1993a), Comparison techniques for random walk on finite groups. Ann. Probab. 21, 2131-2156. Math. Review 95a:60009
- Diaconis, P. and Saloff-Coste, L. (1993b), Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696-730. Math. Review 94i:60074
- Diaconis, P. and Shahshahani, M. (1981), Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57, 159-179. Math. Review 82h:60024
- Diaconis, P. and Shahshahani, M. (1987), Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal. 18, 208-218. Math. Review 88e:60014
- Roussel, S. (2000), Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique. Colloq. Math. 86, 111-135 Math. Review 1799892
- Schoolfield, C.H. (1998), Random walks on wreath products of groups and Markov chains on related homogeneous spaces. Ph.D. dissertation, Dept. of Mathematical Sciences, The Johns Hopkins University. Manuscript available. Math. Review number not available.
- Schoolfield, C.H. (2001a), Random walks on wreath products of groups. J. Theoret. Probab. To appear. Preprint available. Math. Review number not available.
- Schoolfield, C.H. (2001b), A signed generalization of the Bernoulli-Laplace diffusion model. J. of Theoret. Probab. To appear. Preprint available. Math. Review number not available.
- Stanley, R.P. (1986). Enumerative Combinatorics, Vol. I. Wadsworth and Brooks/Cole, Monterey, CA. Math. Review 87j:05003
This work is licensed under a Creative Commons Attribution 3.0 License.