Separation cutoffs for random walk on irreducible representations

DOI10.1007/S00026-010-0062-5MaRDI QIDQ659593zbMATH OpenOpenAlexFDO

Authors Jason Fulman

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703291

zbMATH Keywords

cutoff phenomenonirreducible representation of a finite groupLagrange-Sylvester interpolationMarkov chainseparation distance

Mathematics Subject Classification ID

Probabilistic methods in group theory (20P05) Combinatorial probability (60C05)

Abstract: Random walk on the irreducible representations of the symmetric and general linear groups is studied. A separation distance cutoff is proved and the exact separation distance asymptotics are determined. A key tool is a method for writing the multiplicities in the Kronecker tensor powers of a fixed representation as a sum of non-negative terms. Connections are made with the Lagrange-Sylvester interpolation approach to Markov chains.

Review text

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.

Recommendations

• Convergence rates of random walk on irreducible representations of finite groups
• scientific article; zbMATH DE number 2042290
• The random k cycle walk on the symmetric group
• Enumeration and random walks on finite groups
• Comparison techniques for random walk on finite groups

Cites work

• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A course in combinatorics.
• Analysis of Top To Random Shuffles
• Applications of symmetric functions to cycle and increasing subsequence structure after shuffles
• Card shuffling and the decomposition of tensor products.
• Combinatorial operators for Kronecker powers of representations of \(\mathfrak S_n\).
• Commutation relations and Markov chains
• Convergence rates of random walk on irreducible representations of finite groups
• Derangement characters of the finite general linear group.
• Exchangeable pairs and Poisson approximation
• scientific article; zbMATH DE number 431548 (Why is no real title available?)
• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 5485489 (Why is no real title available?)
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 4068961 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 51129 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• Littelmann paths and Brownian paths
• Mixing times of lozenge tiling and card shuffling Markov chains
• Representations of finite classical groups. A Hopf algebra approach
• Separation cut-offs for birth and death chains
• Shuffling Cards and Stopping Times
• Spectral Analysis, without Eigenvectors, for Markov Chains
• Stein's method and random character ratios
• Stein's method, Jack measure, and the Metropolis algorithm
• Stein’s method and Plancherel measure of the symmetric group
• Strong stationary times via a new form of duality
• Strong uniform times and finite random walks
• The cutoff phenomenon in finite Markov chains.

Cited in

(5)

• Commutation relations and Markov chains
• Tensor product Markov chains
• Tensor powers of the defining representation of \(S_n\)
• Tensor quasi-random groups
• Tensor product Markov chains and Weil representations

This page was built for publication: Separation cutoffs for random walk on irreducible representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659593)