= 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>, and
$$
d_{\mathrm{TV}}(t)\leq\mathbb P(T>t).
$$
The <coupon collector problem> gives $T=n\log n+O_{\mathbb P}(n)$, so for $c\to\infty$,
$$
d_{\mathrm{TV}}(n\log n+cn)\longrightarrow0.
$$
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\geq k)\to1$. The bottom $k$ cards are then in their original relative order, whereas under the uniform distribution this has probability $1/k!$. Hence
$$
d_{\mathrm{TV}}(n\log n-cn)\longrightarrow1.
$$
The 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 \b[top-to-random has the same cutoff at $n\log n$ with window $O(n)$].
Back to article page
