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

Consider K ≥ 2 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 \documentclass{article} \usepackage{amsmath,amsfonts}\pagestyle{empty}\begin{document} $n\in \mathbb{N}$ \end{document} , 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 )/(2 K ) 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 \documentclass{article} \usepackage{amsmath,amsfonts}\pagestyle{empty}\begin{document} $N^{1+\frac{2}{K}}$ \end{document} (at least for K ≥ 3), 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. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012