Abstract FR:

Nous considerons des marches aleatoires evoluant sur le groupe symetrique, de mesure stationnaire la mesure uniforme et de noyau de transition k(x,y) = q(x 1y) ou q est la mesure uniforme sur une classe de conjugaison donnee. L'objet de cette these est de mettre en evidence le phenomene de cutoff, etudie en particulier par aldous et diaconis. Ce phenomene traduit le fait que la norme en variation totale entre et q * k, le noyau de transition apres k etapes, reste proche de sa valeur maximale 1 pendant un moment, puis, en un laps de temps tres court autour d'une valeur critique, se rapproche de 0 avant de decroitre a une vitesse exponentielle. Diaconis et shahshahani ont montre en 1981 que ce phenomene se produisait pour la marche aleatoire engendree par les transpositions autour de la valeur 1/2n ln n. Une conjecture naturelle est que pour une classe de conjugaison a n c points fixes, avec c$$n, la valeur critique est 1/cn ln n. Les techniques utilisees reposent sur l'analyse de fourier et plus precisement sur la valeur des caracteres irreductibles de s n sur les classes de conjugaison. Un premier resultat de la these est que pour une marche aleatoire engendree par une classe a n c points fixes, la valeur critique est au moins egale a 1/cn ln n. Pour montrer qu'il s'agit de la valeur exacte, nous devons verifier, pour chaque cas etudie, un certain nombre d'hypotheses techniques sur les valeurs propres de la marche aleatoire qui s'expriment en fonction des caracteres irreductibles de s n. A partir des resultats d'un article d'ingram datant de 1950 que nous avons etendus, nous montrons dans cette these que la conjecture est verifiee pour les marches aleatoires engendrees par des classes de conjugaison d'au moins n 6 points fixes ou par la classe des cycles de longueur 7.