Random Walks on Wreath Products of Groups

We bound the rate of convergence to uniformity for a certain random walk on the complete monomial groups G(wreath product)S n for any group G. Specifically, we determine that 1/2n log n+ 1/4n log (|G|–1|) steps are both necessary and sufficient for l^2 distance to become small. We also determine that 1/2n log n steps are both necessary and sufficient for total variation distance to become small. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group Z2(wreath product)S n , the generalized symmetric group Zm (wreath product)S n , and S m (wreath product)S n . In the special case of the hyperoctahedral group, our random walk exhibits the “cutoff phenomenon.”