Separation cutoffs for random walk on irreducible representations (Q659593)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Separation cutoffs for random walk on irreducible representations |
scientific article |
Statements
Separation cutoffs for random walk on irreducible representations (English)
0 references
24 January 2012
0 references
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.
0 references
Markov chain
0 references
cutoff phenomenon
0 references
irreducible representation of a finite group
0 references
separation distance
0 references
Lagrange-Sylvester interpolation
0 references
0 references
0 references