Random shuffles and group representations

DOI10.1214/AOP/1176993073MaRDI QIDQ1058225zbMATH OpenOpenAlexWikidataFDO

Authors L. Flatto, Andrew Odlyzko, David Wales

Publication date 1985

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aop/1176993073

zbMATH Keywords

card shufflingrandom walks on a finite group

Mathematics Subject Classification ID

Ordinary representations and characters (20C15) Modular representations and characters (20C20) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Sums of independent random variables; random walks (60G50)

Review text

The authors consider random walks on a finite group G with a uniform initial distribution, and ask for the distribution of the number T of steps it takes to reach a particular element of G, which may be assumed to be the unit of G. They obtain a formula for the generating function of T, involving the irreducible representations of G. These problems were motivated by questions on card shuffling. If one starts with a deck of n cards in random order and reshuffles it by choosing two cards at random and interchanging them, how long does it take that the deck is fully sorted? It turns out that the expected number of shuffles is \(n!+2(n-2)!+o((n-2)!)\). The paper also studies limit laws for T and other related results.

Recommendations

• Shuffling Cards and Stopping Times
• Riffle shuffles, cycles, and descents
• Analysis of Top To Random Shuffles
• scientific article; zbMATH DE number 3872370
• Remarks on the shuffling problem for finite groups

Cited in

(58)

• On the Betti numbers of chessboard complexes
• Decomposition of the conjugacy representation of the symmetric groups
• Rate of convergence for shuffling cards by transpositions
• A recursive rule for Kazhdan-Lusztig characters
• Expansion properties of Cayley graphs of the alternating groups
• Kazhdan constants for conjugacy classes of compact groups.
• Likelihood orders for the \(p\)-cycle walks on the symmetric group
• Cutoff for conjugacy-invariant random walks on the permutation group
• Efficiency test of pseudorandom number generators using random walks
• Card shuffling and the decomposition of tensor products.
• An introduction to covering problems for random walks on graphs
• Random walks on a finite graph with congestion points
• The stepping stone model: New formulas expose old myths
• The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transfor\-mations.
• Sparse topologies with small spectrum size
• Fourier transform over semi-simple algebras and harmonic analysis for probabilistic algorithms
• Time inhomogeneous Markov chains with wave-like behavior
• The second eigenvalue of some normal Cayley graphs of highly transitive groups
• The full spectrum of random walks on complete finite \(d\)-ary trees
• Signal processing on the permutahedron: tight spectral frames for ranked data analysis
• Eigenvalues of Cayley graphs
• Sorting by shuffling methods and a queue
• Total variation cutoff for the transpose top-2 with random shuffle
• \(PI\)-eigenfunctions of the Star graphs
• On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\)
• The second largest eigenvalues of some Cayley graphs on alternating groups
• Mixing times for exclusion processes on hypergraphs
• The spectral gap of graphs arising from substring reversals
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Modified logarithmic Sobolev inequalities for some models of random walk
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• A few remarks on the octopus inequality and Aldous' spectral gap conjecture
• The random k cycle walk on the symmetric group
• scientific article; zbMATH DE number 4205848 (Why is no real title available?)
• Group representations that resist random sampling
• Proof of Aldous' spectral gap conjecture
• Self-intersections of random walks on discrete groups
• scientific article; zbMATH DE number 4082591 (Why is no real title available?)
• Hitting times for random walks on vertex-transitive graphs
• Spectrum of Cayley graphs on the symmetric group generated by transpositions
• scientific article; zbMATH DE number 515793 (Why is no real title available?)
• Character-theoretic techniques for near-central enumerative problems
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• Total variation cutoff for the flip-transpose top with random shuffle
• Generalizations of an expansion formula for top to random shuffles
• The distance spectra of Cayley graphs of Coxeter groups
• The small world effect on the coalescing time of random walks
• Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems
• Cutoff phenomenon for the warp-transpose top with random shuffle
• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
• Character estimates for finite simple groups and applications
• Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
• Comparing limit profiles of reversible Markov chains
• The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups
• Representation theory and cycle statistics for random walks on the symmetric group
• Cutoff for the biased random transposition shuffle
• Tests of randomness by the gambler's ruin algorithm
• Intermediate range migration in the two-dimensional stepping stone model

This page was built for publication: Random shuffles and group representations

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