Random shuffles and group representations (Q1058225): Difference between revisions

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.