Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 1 / Solution

Start the random-to-top card shuffle from a fixed ordering and let $T$ be the first time every card has been selected. Once a card has been selected, its location relative to the other selected cards is determined by their most recent selection times. At $T$ these times have a uniformly random strict order, so the deck is uniform and independent of the event $\{T=t\}$. Thus $T$ is a strong stationary time, andThe coupon collector problem gives $T=n\log n+O_{\mathbb{P}}(n)$, so for $c\to \infty$,

Before all cards have been selected, the unselected cards form the bottom block of the deck in their original relative order. At time $n\log n-cn$, with $c\to \infty$ sufficiently slowly, the number $U$ of unselected cards tends to infinity in probability. Choose $k\to \infty$ with $\mathbb{P}(U\ge k)\to 1$. The bottom $k$ cards are then in their original relative order, whereas under the uniform distribution this has probability $1/k!$. HenceThe random-to-top shuffle therefore has cutoff for Markov chains at $n\log n$ with window $O(n)$.

The top-to-random card shuffle is the time reversal of the random-to-top card shuffle under the uniform stationary distribution. Equivalently, their step distributions on the symmetric group are carried into one another by permutation inversion, which preserves total variation from uniform. Their mixing profiles agree, so top-to-random has the same cutoff at $n\log n$ with window $O(n)$.