Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 6 (2001) > Paper 11 open journal systems 


Mixing Times for Markov Chains on Wreath Products and Related Homogeneous Spaces

James Allen Fill, The Johns Hopkins University
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 Sn and a quite general class of Markov chains on the homogeneous space (G wr Sn) / (Sr times Sn-r). We derive an exact formula for the L2 distance in terms of the L2 distances to uniformity for closely related random walks on the symmetric groups Sj for 1 leq j leq n or for closely related Markov chains on the homogeneous spaces Si+j / (Si times Sj) 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: PDF

Pages: 1-22

Published on: April 23, 2001


Bibliography
  1. 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.
  2. Diaconis, P.(1988), Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA. Math. Review 90a:60001
  3. Diaconis, P. and Saloff-Coste, L. (1993a), Comparison techniques for random walk on finite groups. Ann. Probab. 21, 2131-2156. Math. Review 95a:60009
  4. Diaconis, P. and Saloff-Coste, L. (1993b), Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696-730. Math. Review 94i:60074
  5. Diaconis, P. and Shahshahani, M. (1981), Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57, 159-179. Math. Review 82h:60024
  6. 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
  7. 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
  8. 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.
  9. Schoolfield, C.H. (2001a), Random walks on wreath products of groups. J. Theoret. Probab. To appear. Preprint available. Math. Review number not available.
  10. 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.
  11. Stanley, R.P. (1986). Enumerative Combinatorics, Vol. I. Wadsworth and Brooks/Cole, Monterey, CA. Math. Review 87j:05003
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489