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≀ S _n for any group G. Specifically, we determine that $${\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}$$ n log n+ $$\frac{1}{4}$$ n log (| G|−1|) steps are both necessary and sufficient for ℓ² distance to become small. We also determine that $${\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}$$ n 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 ℤ₂≀ S _n, the generalized symmetric group ℤ _m≀ S _n, and S _m≀ S _n. In the special case of the hyperoctahedral group, our random walk exhibits the “cutoff phenomenon.” [ABSTRACT FROM AUTHOR]