Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique

Sandrine Roussel

Colloquium Mathematicae (2000)

  • Volume: 86, Issue: 1, page 111-135
  • ISSN: 0010-1354

Abstract

top
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 k n for which the total variation norm between Q * k and π stays very close to 1 for k ≪ k n , and falls rapidly to a value close to 0 for k ≥ k n with a fall-off phase much shorter than k n . 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.

How to cite

top

Roussel, Sandrine. "Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique." Colloquium Mathematicae 86.1 (2000): 111-135. <http://eudml.org/doc/210834>.

@article{Roussel2000,
author = {Roussel, Sandrine},
journal = {Colloquium Mathematicae},
language = {fre},
number = {1},
pages = {111-135},
title = {Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique},
url = {http://eudml.org/doc/210834},
volume = {86},
year = {2000},
}

TY - JOUR
AU - Roussel, Sandrine
TI - Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique
JO - Colloquium Mathematicae
PY - 2000
VL - 86
IS - 1
SP - 111
EP - 135
LA - fre
UR - http://eudml.org/doc/210834
ER -

References

top
  1. [AD] D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. Appl. Math. 8 (1987), 69-97. 
  2. [Ay] R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., Providence, RI, 1963. 
  3. [D1] P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 1659-1664. Zbl0849.60070
  4. [D2] P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes Monogr. Ser. 11, Hayward, CA, 1988. 
  5. [DS] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), 159-179. Zbl0485.60006
  6. [Fel] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed., Wiley, New York, 1968. 
  7. [Ing] R. E. Ingram, Some characters of the symmetric group, Proc. Amer. Math. Soc. 1 (1950), 358-369. Zbl0054.01103
  8. [Jam] G. D. James, The Representation Theory of the Symmetric Group, Lecture Notes in Math. 682, Springer, Berlin, 1978. 
  9. [JK] G. James and A. Kerber, The Representation Theory of the Symmetric Group, Addison-Wesley, Reading, MA, 1981. 
  10. [R1] Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), 451-485. Zbl0854.20015
  11. [R2] S. Roussel, Marches aléatoires sur le groupe symétrique, thèse de doctorat (en préparation), 1999. 
  12. [Sag] B. E. Sagan, The Symmetric Group , Representations , Combinatorial Algorithms and Symmetric Functions, Wadsworth and Brooks/Cole Math. Ser., 1991. 
  13. [SC1] L. Saloff-Coste, Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Z. 217 (1994), 641-677. Zbl0815.60074
  14. [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. Zbl0885.60061
  15. [Ser] J. P. Serre, Représentations linéaires des groupes finis, Hermann, Paris, 1977. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.