On the cut-off phenomenon for the transitivity of randomly generated subgroups

• Published in: Random structures & algorithms 2012-03, Vol.40 (2), p.189-219
• Main Authors: Galligo, André, Miclo, Laurent
• Format: Article
• Language: English
• Subjects: Mathematics; Probability
• ISSN: 1042-9832; 1098-2418

Consider $K\geq2$ independent copies of the random walk on the symmetric group $S_N$ starting from the identity and generated by the products of either independent uniform transpositions or independent uniform neighbor transpositions. At any time $n\in\NN$, let $G_n$ be the subgroup of $S_N$ generated by the $K$ positions of the chains. In the uniform transposition model, we prove that there is a cut-off phenomenon at time $N\ln(N)/(2K)$ for the non-existence of fixed point of $G_n$ and for the transitivity of $G_n$, thus showing that these properties occur before the chains have reached equilibrium. In the uniform neighbor transposition model, a transition for the non-existence of a fixed point of $G_n$ appears at time of order $N^{1+\frac 2K}$ (at least for $K\geq3$), but there is no cut-off phenomenon. In the latter model, we recover a cut-off phenomenon for the non-existence of a fixed point at a time proportional to $N$ by allowing the number $K$ to be proportional to $\ln(N)$. The main tools of the proofs are spectral analysis and coupling techniques.