On the statistics of random-to-top shuffles

Abstract

We prove limit theorems for the number of fixed points, descents, and inversions of iterated random-to-top shuffles in two asymptotic regimes. Our proofs are analytic, and they utilize new combinatorial decompositions that represent each statistic as a randomly indexed statistic of a uniformly random permutation. This perspective gives new combinatorial proofs of the expected number of fixed points and inversions. In particular, we solve an open problem of Pehlivan on fixed points, and we answer a question of Diaconis and Fulman on inversions.

arXiv comment26 pages, 3 figures, second version. Substantial rewrite with changes made to the presentation