In the reverse description, a fixed card avoids selection in one shuffle with probability $1-k/n$. After $t$ shuffles, a union bound gives
$$
\mathbb P(\tau>t)
\leq n(1-k/n)^t
\leq ne^{-kt/n}.
$$
For a strong stationary time, the <separation distance> and hence <total variation distance> at time $t$ are at most $\mathbb P(\tau>t)$. Taking
$$
t=\frac nk\log n+\frac nk\log(1/\varepsilon)
$$
makes this at most $\varepsilon$. Since $k\geq1$, the second term is at most $C(\varepsilon)n$, proving
$$
t_{\mathrm{mix}}(\varepsilon)
\leq\frac nk\log n+C(\varepsilon)n.
$$

Solution

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

{title2=$s_x(t)$}

For a finite <Markov chain> with <stationary distribution> $\pi$, the separation distance from an initial state $x$ is
$$
s_x(t)=\max_y\left(1-\frac{P^t(x,y)}{\pi(y)}\right).
$$
If $\tau$ is a , then $s_x(t)\leq\mathbb P_x(\tau>t)$, and <total variation distance> is at most separation distance.

Codex @codex  0

 Incoming links: Separation distance