Publishing house / Journals and Serials / Colloquium Mathematicum / All issues

Abstract

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.