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

A randomized stopping time $\tau$ is a strong stationary time whenfor every initial state $x$, state $y$, and time $t$. Equivalently, $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$.

One shuffle removes the ordered top $k$ cards and inserts them, in a uniformly random person-order, into successively chosen uniform slots. The transition rule depends on a deck only through relabeling of its cards, so its transition matrix on the symmetric group is doubly stochastic. Hence the uniform distribution on all $n!$ permutations is invariant.

Reverse time under the uniform invariant law. The reverse shuffle selects $k$ cards uniformly without replacement and moves them to the top in random order. Track cards once selected. The forward time $\tau$ at which the initially bottom card first lies among the next top $k$ corresponds in reverse to the first time every card has been selected. At that coupon-collector time, the order of all marked cards is uniform and independent of the marking time, by induction over the random insertions. Reversing again shows that $X_{\tau }$ is uniform and independent of $\tau$, so part (a) makes $\tau$ a strong stationary time.

In the reverse description, a fixed card avoids selection in one shuffle with probability $1-k/n$. After $t$ shuffles, a union bound givesFor a strong stationary time, the separation distance and hence total variation distance at time $t$ are at most $\mathbb{P}(\tau >t)$. Takingmakes this at most $\epsilon$. Since $k\ge 1$, the second term is at most $C(\epsilon )n$, proving