Random shuffles and group representations. (English) Zbl 0564.60007

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.
Reviewer: U.Krengel


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