Rechercher

sur ce site


Accueil du site > Résumés des séminaires > Labo > Mélanger en transposant les plus proches voisins

Mélanger en transposant les plus proches voisins

Nous étudions la chaîne de Markov $sigma_n$ sur le groupe symétrique $S_N$ définie comme suit : on part de l’identité et à chaque étape, $sigma$ est composée (à gauche) avec une transposition $(X_n,X_n+1)$ où $X_n$ est choisi uniformément au hasard dans $1,dots,N-1$.

Nous nous intéressons au temps de mélange $T^N_mel$ de cette chaîne, c’est-à-dire au nombre d’étapes nécessaires pour obtenir approximativement une permutation aléatoire (uniformément distribuée sur $S_N$). Nous démontrons une conjecture de David Wilson en donnant une asymptotique précise de $T^N_mel$ ($T_mel := frac12pi^2N^3log N$ pour la chaîne en temps discret).


CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46