Random walks on wreath products of groups and Markov chains on related homogeneous spaces

For a certain random walk on the symmetric group Sn that is generated by random transpositions, Diaconis and Shahshahani (1981) obtained bounds on the rate of convergence to uniformity using group representation theory. Similarly, we bound the rate of convergence to uniformity for a random walk on the hyperoctahedral group Z2&m22;Sn that is generated by random signed transpositions. Specifically, we determine that, to first order in n, ½ n log n steps are both necessary and sufficient for total variation distance to become small. Moreover, we show that our walk exhibits the so-called "cutoff phenomenon." We also examine a slight variant of this random walk, establishing upper and lower bounds on its rate of convergence to uniformity. We extend our results on both of these random walks to the generalized symmetric groups Zm&m22;Sn and further to the complete monomial groups G&m22;Sn for any finite group G.;For the classical Bernoulli-Laplace model for diffusion, Diaconis and Shahshahani (1987) obtained bounds on the rate of convergence to stationarity. Similarly, we bound the rate of convergence to stationarity for a signed generalization of (a variant of) the classical Bernoulli-Laplace diffusion model; this generalization is a Markov chain on the homogeneous space &parl0;Z2&m22;Sn &parr0;/SrxSn-r . Specifically, for r not too far from n/2, we determine that, to first order in n, ¼ n log n steps are both necessary and sufficient for total variation distance to become small. Moreover, for r not too far from n/2, we show that our signed model also exhibits the "cutoff phenomenon." We also examine a slight variant of this signed model, establishing upper and lower bounds on its rate of convergence to stationarity.;We also develop a method for establishing upper bounds on the distance to stationarity for very general random walks on the complete monomial group G&m22;Sn and very general Markov chains on the homogeneous space G &m22;Sn/ SrxSn-r, without the use of group representation theory. We derive an exact formula for the so-called "X2 distance" in terms of the ℓ2 distances to uniformity for closely related random walks on the symmetric groups Sj for 0 ≤ j ≤ n or closely related Markov chains on the homogeneous spaces Si+j/Six Sj for 0≤i≤r and 0≤j≤n-r, respectively. For those cases in which this method is appropriate, its results are consistent with those found above.;The comparison technique was introduced by Diaconis and Saloff-Coste (1993) as a method for bounding the rate of convergence to uniformity of a symmetric random walk on a finite group by comparing it to a benchmark random walk whose rate of convergence is known. Our random walks on the hyperoctahedral, generalized symmetric, and complete monomial groups provide such benchmarks to which many other random walks, modeling a wide range of phenomena, may be compared, thereby yielding bounds on the rates of convergence to uniformity for previously intractable random walks. We analyze two specific examples using this technique, one of which has applications in mathematical biology. We further specialize the comparison technique to random walks generated by random transpositions along the edges of a graph and analyze several examples.