On the cut-off phenomenon for the transitivity of randomly generated subgroups
Résumé
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 successive 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 reach equilibrium. In the uniform successive transposition model, a transition for the non-existence of 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 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.
Mots clés
isoperimetric bounds
random walks on symmetric groups
uniform transposition model
uniform successive transposition model
cut-off phenomenon
flared transition phenomenon
existence of fixed point(s) for random subgroups
transitivity for random subgroups
spectral analysis
coupling techniques
exclusion processes
isoperimetric bounds.
Domaines
Probabilités [math.PR]
Origine : Fichiers produits par l'(les) auteur(s)