Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique
Roussel, Sandrine
Colloquium Mathematicae, Tome 84/85 (2000), p. 111-135 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

The main purpose of this paper is to exhibit the cutoff phenomenon, studied by Aldous and Diaconis [AD]. Let Q*k denote a transition kernel after k steps and π be a stationary measure. We have to find a critical value kn for which the total variation norm between Q*k and π stays very close to 1 for k≪kn, and falls rapidly to a value close to 0 for k≥kn with a fall-off phase much shorter than kn. According to the work of Diaconis and Shahshahani [DS], one can naturally conjecture, for a conjugacy class with n-c fixed points, with c≪n, that the associated random walk presents a cutoff, with critical value equal to (1/c)nln(n). Using Fourier analysis, we prove that, in this context, the critical value can not be less than (1/c)nln(n). We also prove that the conjecture is true for conjugacy classes with at least n-6 fixed points and for a conjugacy class of cycle length 7.

Publié le : 2000-01-01
EUDML-ID : urn:eudml:doc:210834 
@article{bwmeta1.element.bwnjournal-article-cmv86i1p111bwm,
     author = {Sandrine Roussel},
     title = {Ph\'enom\`ene de cutoff pour certaines marches al\'eatoires sur le groupe sym\'etrique},
     journal = {Colloquium Mathematicae},
     volume = {84/85},
     year = {2000},
     pages = {111-135},
     zbl = {0961.60063},
     language = {fra},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-cmv86i1p111bwm}
}

Roussel, Sandrine. Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique. Colloquium Mathematicae, Tome 84/85 (2000) pp. 111-135. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-cmv86i1p111bwm/

[000] [AD] D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. Appl. Math. 8 (1987), 69-97.

[001] [Ay] R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., Providence, RI, 1963.

[002] [D1] P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 1659-1664. | Zbl 0849.60070

[003] [D2] P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes Monogr. Ser. 11, Hayward, CA, 1988.

[004] [DS] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), 159-179. | Zbl 0485.60006

[005] [Fel] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed., Wiley, New York, 1968.

[006] [Ing] R. E. Ingram, Some characters of the symmetric group, Proc. Amer. Math. Soc. 1 (1950), 358-369. | Zbl 0054.01103

[007] [Jam] G. D. James, The Representation Theory of the Symmetric Group, Lecture Notes in Math. 682, Springer, Berlin, 1978.

[008] [JK] G. James and A. Kerber, The Representation Theory of the Symmetric Group, Addison-Wesley, Reading, MA, 1981.

[009] [R1] Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), 451-485. | Zbl 0854.20015

[010] [R2] S. Roussel, Marches aléatoires sur le groupe symétrique, thèse de doctorat (en préparation), 1999.

[011] [Sag] B. E. Sagan, The Symmetric Group, Representations, Combinatorial Algorithms and Symmetric Functions, Wadsworth and Brooks/Cole Math. Ser., 1991.

[012] [SC1] L. Saloff-Coste, Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Z. 217 (1994), 641-677. | Zbl 0815.60074

[013] [SC2] L. Saloff-Coste, Lectures on finite Markov chains, in: Lectures on Probability Theory and Statistics, Lecture Notes in Math. 1665, Springer, 1997, 301-413. | Zbl 0885.60061

[014] [Ser] J. P. Serre, Représentations linéaires des groupes finis, Hermann, Paris, 1977.