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

Tom 86 / 2000

Sandrine Roussel Colloquium Mathematicum 86 (2000), 111-135 DOI: 10.4064/cm-86-1-111-135


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.


  • Sandrine Roussel

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek