Separation cutoffs for random walk on irreducible representations (Q659593): Difference between revisions

This paper deals with the convergence rates of a random walk on a finite group. Starting from a commonly used definition for the separation distance between two probability distributions \[ s (P, Q) := \max_{x \in X}\biggl[1- \frac{P (x)}{Q(x)}\biggr], \tag{1} \] the author shows that, for the separation distance after \(r\) steps, say \(s(r)\), of a random walk on \(\text{Irr} (G)\), where \(G\) is a symmetric group, one has \[ s(n \log(n) + cn) = 1- e^{-e{}^{-c}} 1 + e^{-c} + O \biggl( \frac{ \log(n)}{n}\biggr).\tag{2} \] The proofs of the results are very clear and performed in different ways. By using combinatorial arguments and the diagonalization of the random walk on \(\text{Irr} (G)\), the author provides the formula for the separation distance. Furthermore the author shows that this formula can be also obtained by applying the Lagrange-Sylvester interpolation when only the eigenvalues of a random walk on \(\text{Irr} (G)\) are known. The organization of the paper is clear and some useful background from Markov chain theory is presented in Section 2. This facilitates the reading of the paper. In the introduction, the author explains very well the motivation of this kind of works and some hints for possible applications are given, e.g., these random walks arise in quantum computing.