PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2000 | 86 | 1 | 111-135
Tytuł artykułu

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

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
Rocznik
Tom
86
Numer
1
Strony
111-135
Opis fizyczny
Daty
wydano
2000
otrzymano
1999-01-29
poprawiono
1999-10-03
Twórcy
  • 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
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-cmv86i1p111bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.