PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Colloquium Mathematicum

2000 | 86 | 1 | 111-135
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
FR EN
Abstrakty
EN
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.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Numer
Strony
111-135
Opis fizyczny
Daty
wydano
2000
otrzymano
1999-01-29
poprawiono
1999-10-03
Twórcy
autor
• Université P. Sabatier, F-31062 Toulouse Cedex, France
Bibliografia
• [AD] D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. Appl. Math. 8 (1987), 69-97.
• [Ay] R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., Providence, RI, 1963.
• [D1] P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 1659-1664.
• [D2] P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes Monogr. Ser. 11, Hayward, CA, 1988.
• [DS] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), 159-179.
• [Fel] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed., Wiley, New York, 1968.
• [Ing] R. E. Ingram, Some characters of the symmetric group, Proc. Amer. Math. Soc. 1 (1950), 358-369.
• [Jam] G. D. James, The Representation Theory of the Symmetric Group, Lecture Notes in Math. 682, Springer, Berlin, 1978.
• [JK] G. James and A. Kerber, The Representation Theory of the Symmetric Group, Addison-Wesley, Reading, MA, 1981.
• [R1] Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), 451-485.
• [R2] S. Roussel, Marches aléatoires sur le groupe symétrique, thèse de doctorat (en préparation), 1999.
• [Sag] B. E. Sagan, The Symmetric Group$,$ Representations$,$ Combinatorial Algorithms and Symmetric Functions, Wadsworth and Brooks/Cole Math. Ser., 1991.
• [SC1] L. Saloff-Coste, Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Z. 217 (1994), 641-677.
• [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.
• [Ser] J. P. Serre, Représentations linéaires des groupes finis, Hermann, Paris, 1977.
Typ dokumentu
Bibliografia
Identyfikatory