Random walks on wreath products of groups

Abstract

We bound the rate of convergence to uniformity for certain random walks on the complete monomial groups G \wr S_n for any group G. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group Z_2 \wr S_n, the generalized symmetric group Z_m \wr S_n, and S_m \wr S_n. These results provide benchmarks to which many other random walks, modeling a wide range of phenomena, may be compared using the comparison technique, thereby yielding bounds on the rates of convergence to uniformity for previously intractable random walks.

arXiv comment46 pages. See also http://www.fas.harvard.edu/~chschool/ . Submitted for publication in May, 2000