Strong stationary time; coupling argument

Intuition [Beginner]

A strong stationary time is a cleverly designed stopping rule that tells you the exact moment when a random walk has reached the uniform distribution. Instead of bounding how far the walk is from uniform at each step, you define a random time $T$ and prove: at time $T$, the position of the walk is exactly uniform, and $T$ itself reveals no information about which position was reached.

The idea comes from card shuffling. If you shuffle cards by repeatedly moving the top card to a random position, there is a natural moment when the original bottom card first reaches the top and is then inserted randomly. At that moment, the deck becomes exactly uniform — not approximately, but exactly. The random time $T$ when this happens is a strong stationary time.

The power of this approach is that the distribution of $T$ gives an upper bound on the total variation distance. If $T$ is likely to be small, the walk mixes fast. If $T$ can be large, the walk mixes slowly.

Visual [Beginner]

A diagram showing the top-to-random shuffle. At each step, the top card is removed and inserted at a uniformly random position in the deck. A marker shows when the original bottom card first reaches the top — that moment is a strong stationary time.

The key insight: once the original bottom card reaches the top and is reinserted randomly, every ordering of the deck is equally likely.

Worked example [Beginner]

Consider the top-to-random shuffle on a deck of 4 cards, initially in order $(1,2,3,4)$ from top to bottom. At each step, take the top card and insert it at a uniformly random position in the deck (including back on top).

Step 1. After one step: the top card (1) is inserted at a random position among positions 1, 2, 3, 4. Each position has probability $1/4$. If card 1 goes to position 4 (the bottom), the deck is $(2,3,4,1)$.

Step 2. Card 4 (the original bottom card) reaches the top when all cards originally above it have been moved. The probability that card 4 reaches the top by step $k$ involves a coupon-collector type argument.

Step 3. Once card 4 is on top and is then inserted at a random position (at some step $T$), the deck becomes exactly uniform. The time $T$ is a strong stationary time. For a deck of $n$ cards, the expected time for $T$ is $n\cdot H_n=n(1+1/2+\cdots +1/n)$, which is approximately $n\log n$.

What this tells us: for $n=4$, the expected $T$ is $4\cdot (1+1/2+1/3+1/4)=4\cdot 2.083\approx 8.3$ steps. The top-to-random shuffle mixes in about $n\log n$ steps.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $(X_k{)}_{k\ge 0}$ be a Markov chain on a finite state space $\Omega$ with stationary distribution $\pi$. A stopping time is a random variable $T$ taking values in $\{0,1,2,\dots \}\cup \{\infty \}$ such that the event $\{T=k\}$ depends only on $(X_0,X_1,\dots ,X_k)$.

Definition (Strong stationary time). A stopping time $T$ is a strong stationary time (SST) if:

1. $X_T$ has distribution $\pi$ (the position at time $T$ is exactly stationary), and
2. $X_T$ is independent of $T$ (the position reveals nothing about when $T$ occurred).

The second condition is what makes $T$ strong: it is not enough that $X_T\sim \pi$ on average; $X_T$ must be independent of the event $\{T=k\}$ for every $k$.

Definition (Separation distance). The separation distance at step $k$ is

$$s(k)=\underset{x\in \Omega }{\max }\left(1-\frac{Q^{\ast k}(x)}{\pi (x)}\right).$$

Separation distance is an upper bound on total variation distance: $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\le s(k)$. The separation distance equals $\mathrm{Pr}(T>k)$ for the fastest strong stationary time.

Proposition (SST bound). If $T$ is a strong stationary time, then

$$\Vert Q^{\ast k}-\pi {\Vert }_{\mathrm{TV}}\le s(k)=\mathrm{Pr}(T_{\ast }>k)$$

where $T_{\ast }$ is the fastest (stochastically smallest) SST.

Counterexamples to common slips

• Stationary time is not strong stationary time. A stationary time requires only $X_T\sim \pi$ (condition 1). A strong stationary time adds the independence condition (condition 2). Every SST is a stationary time, but not conversely.
• Coupling time is not SST. A coupling of two copies of the chain from different starting positions gives a coupling time when they first meet. The coupling time bounds TV distance via the coupling inequality, but it is not in general a strong stationary time because the meeting point need not be uniformly distributed.
• SST gives separation distance, not TV. The SST bound $\mathrm{Pr}(T>k)$ bounds the separation distance $s(k)$, which is at least as large as the TV distance. The SST bound can overestimate TV distance.

Key theorem with proof [Intermediate+]

Theorem (Aldous-Diaconis strong stationary time criterion 1987). Let $T$ be a strong stationary time for the random walk on a finite group $G$ driven by $Q$. Then:

$$\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\le s(k)=\mathrm{Pr}(T>k).$$

Moreover, the separation distance $s(k)$ equals ${\inf }_T\mathrm{Pr}(T>k)$ where the infimum ranges over all strong stationary times $T$.

Proof. The proof has two parts: the upper bound and the characterisation of separation distance.

Part (i): Upper bound. Let $T$ be any SST. Define the "foreknowledge" distribution: at step $k$, if $T\le k$ then the chain is already uniform (by the SST property), and if $T>k$ then we use the worst-case bound. Formally, for any $g\in G$:

$$Q^{\ast k}(g)=\mathrm{Pr}(X_k=g)=\mathrm{Pr}(X_k=g\mid T\le k)\mathrm{Pr}(T\le k)+\mathrm{Pr}(X_k=g\mid T>k)\mathrm{Pr}(T>k).$$

By the SST property, $\mathrm{Pr}(X_T=g\mid T\le k)=U(g)=1/|G|$. But $X_k$ for $k\ge T$ is obtained by further convolutions after $T$, so $X_k$ need not equal $X_T$. However, for a random walk on a group, convolution with any measure preserves the uniform distribution: if $X_T$ is uniform, then $X_k$ for $k\ge T$ is also uniform (since $U\ast Q^{\ast m}=U$ for any $m$). Therefore:

$$Q^{\ast k}(g)\ge U(g)\cdot \mathrm{Pr}(T\le k)=\frac{1}{|G|}(1-\mathrm{Pr}(T>k)).$$

This gives $Q^{\ast k}(g)/U(g)\ge 1-\mathrm{Pr}(T>k)$, so $s(k)={\max }_g(1-Q^{\ast k}(g)/U(g))\le \mathrm{Pr}(T>k)$.

For the TV bound: $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}=\frac{1}{2}{\sum }_g|Q^{\ast k}(g)-U(g)|\le {\max }_g(1-Q^{\ast k}(g)/U(g))=s(k)\le \mathrm{Pr}(T>k)$.

Part (ii): Separation distance equals the infimum. The separation distance $s(k)$ can be achieved by an optimal SST constructed via duality. The strong stationary dual chain $({\hat{X}}_k)$ on a partially ordered state space $(\hat{\Omega },⪯)$ with maximum element $\hat{1}$ satisfies $\mathrm{Pr}(X_k=g)\ge U(g)\cdot \mathrm{Pr}({\hat{X}}_k=\hat{1})$. Setting $T=\min \{k:{\hat{X}}_k=\hat{1}\}$ gives an SST with $\mathrm{Pr}(T>k)=1-\mathrm{Pr}({\hat{X}}_k=\hat{1})=s(k)$. Hence the infimum is achieved and equals $s(k)$. $\square$

Bridge. The Aldous-Diaconis SST criterion builds toward the duality theory for strong stationary times, which provides a systematic method for constructing optimal SSTs, and appears again in the analysis of specific shuffle models where the dual chain has a natural combinatorial interpretation. The foundational reason SSTs work is that the independence condition (position independent of stopping time) forces the distribution to be exactly uniform at time $T$, and the Markov property preserves this uniformity for all later times. This is exactly the coupling perspective: the SST couples the walk from its starting position to a walk started from the uniform distribution, and the coupling time is the SST. The bridge is between the probabilistic notion of a stopping time and the analytic notion of separation distance; putting these together identifies the optimal SST with the separation distance, generalising the coupling inequality.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Top-to-random mixing time — Aldous-Diaconis 1986). The top-to-random shuffle on $S_n$ has mixing time $t_{\mathrm{mix}}(\epsilon )=n\log n-n\log (-\log (1-\epsilon ))+O(n)$ with cutoff at $t_n=n\log n$. The SST is the time when the original bottom card reaches the top and is reinserted.

The proof constructs the strong stationary dual on $\{0,1,\dots ,n\}$ as in Exercise 7 and shows that ${\hat{X}}_k$ reaches $n$ (complete uniformity) at a coupon-collector time, giving $\mathrm{Pr}(T>k)\le e^{-k/n+\log n}$.

Theorem 2 (Duality for SST — Diaconis-Griffiths 2018, Fill 1998). Every strong stationary time corresponds to a strong stationary dual chain on a partially ordered set with a maximum element. Conversely, every such dual gives rise to an SST. The separation distance at time $k$ equals $1-\mathrm{Pr}({\hat{X}}_k=\hat{1})$ for the optimal dual.

This duality is the definitive structural result: it converts the probabilistic problem of finding an SST into the combinatorial problem of constructing a dual chain on a poset.

Theorem 3 (Coupling inequality — Aldous 1983). For any coupling $(X_k,Y_k)$ of two copies of the Markov chain with $Y_0\sim \pi$ (started from stationarity), define the coupling time $\tau =\min \{k:X_k=Y_k\}$. Then $\Vert Q^{\ast k}-\pi {\Vert }_{\mathrm{TV}}\le \mathrm{Pr}(\tau >k)$.

The coupling inequality is more general than the SST bound (it applies to any coupling, not just SSTs) but typically gives weaker bounds because the coupling time need not be an SST.

Theorem 4 (Random transposition SST and cutoff). The SST "every card touched" for random transpositions on $S_n$ gives $s(k)\le \mathrm{Pr}(T>k)$ where $T$ is the coupon collector time with batch size 2. The separation distance achieves cutoff at $\frac{1}{2}n\log n$, matching the TV cutoff from the Upper Bound Lemma. In fact, separation cutoff and TV cutoff occur simultaneously for this walk.

Theorem 5 (Separation vs TV — separation can be much larger). For some walks, the separation distance $s(k)$ is much larger than the TV distance $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}$. For the lazy random walk on $\mathbb{Z}/p\mathbb{Z}$ with $p$ prime: $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\to 0$ at rate ${\beta }_2^k$, but $s(k)$ can be bounded below by $e^{-k/p}$, which is much slower when $p$ is large. The SST approach overestimates the mixing time for chains without cutoff.

Theorem 6 (SST for riffle shuffles — leakage argument). There is no known simple SST for the riffle shuffle. The best bounds come from the Fourier-analytic Upper Bound Lemma rather than from strong stationary times. This contrasts with the top-to-random shuffle and the random transposition walk, where SSTs give sharp results.

Synthesis. Strong stationary times provide the foundational reason that certain random walks admit sharp mixing bounds via probabilistic coupling. The central insight is that the independence condition in the SST definition — the position at time $T$ is uniform and independent of $T$ — forces the distribution to be exactly stationary at a random time, and the separation distance measures how long this takes. Putting these together with the duality construction, the separation distance is identified with the tail probability of the optimal dual chain hitting its maximum, converting the mixing problem into a first-passage problem on a poset. This is exactly the content that generalises from the top-to-random shuffle (where the dual is the coupon collector) to arbitrary walks with known SST constructions. The bridge is between the probabilistic coupling framework and the analytic separation distance; the pattern recurs across walks where a natural "randomisation threshold" can be identified, and identifies the mixing time with the coupon collector time of the dual chain. The strong stationary time approach complements the Fourier-analytic Upper Bound Lemma, and for walks with cutoff the two methods agree.

Full proof set [Master]

Proposition 1 (Top-to-random SST). The time $T$ at which the original bottom card in the top-to-random shuffle first reaches the top and is then reinserted at a random position is a strong stationary time.

Proof. Index the positions $1,\dots ,n$ from top to bottom. The original bottom card starts at position $n$. Call a card "good" if it is uniformly distributed among all cards below it in the deck. Initially, all cards are good vacuously.

When the top card is removed and reinserted at position $i$: if $i=1$, the top card returns to the top and nothing changes. If $i>1$, the top card is placed at position $i$ and all cards in positions $2,\dots ,i$ shift up one position. The key claim: if the bottom $j$ cards were uniformly distributed before this step, then after the step the bottom $\min (j+1,n)$ cards are uniformly distributed.

This holds because the inserted card is placed at a uniformly random position among all $n$ positions. If it lands among the bottom $j+1$ positions, the randomised block grows by 1. By induction, once $j=n$ (all cards randomised), the permutation is uniform.

The time $T$ when $j=n$ is exactly the time when the original bottom card reaches position 1 (the top) and is then reinserted. At this moment all $n$ cards are randomised, so $X_T$ is uniform. The independence of $X_T$ and $T$ follows because the distribution of the permutation at the randomisation threshold does not depend on when the threshold is reached. $\square$

Proposition 2 (Coupling inequality). For any coupling $(X_k,Y_k)$ of two copies of the Markov chain with $Y_0\sim \pi$:

$$\Vert P^k(x,\cdot )-\pi {\Vert }_{\mathrm{TV}}\le \mathrm{Pr}(\tau >k)$$

where $\tau =\min \{k:X_k=Y_k\}$.

Proof. For any event $A\subseteq \Omega$:

$$|P^k(x,A)-\pi (A)|=|\mathrm{Pr}(X_k\in A)-\mathrm{Pr}(Y_k\in A)|.$$

On the event $\{\tau \le k\}$, the two chains have coupled so $X_k=Y_k$, contributing 0 to the difference. On $\{\tau >k\}$:

$$|\mathrm{Pr}(X_k\in A)-\mathrm{Pr}(Y_k\in A)|\le \mathrm{Pr}(\tau >k).$$

Taking the supremum over $A$: $\Vert P^k(x,\cdot )-\pi {\Vert }_{\mathrm{TV}}\le \mathrm{Pr}(\tau >k)$. $\square$

Connections [Master]

• Non-abelian Fourier transform 07.01.09. The Fourier-analytic bounds from the Upper Bound Lemma complement the SST approach: the Fourier transform gives TV bounds directly, while the SST gives separation bounds. For walks with cutoff, both methods converge to the same mixing time.

• Symmetric group representation 07.05.01. The irreducible representations of $S_n$ indexed by partitions control the eigenvalues of the shuffle transition matrix, which in turn determine the rate at which the SST dual chain approaches its maximum. The character values on cycle types developed in 07.05.01 appear in both the Fourier-analytic and SST approaches.

• Regular representation 07.01.05. The random walk on a group acts by convolution on the group algebra, which is the regular representation. The spectral decomposition of the regular representation into irreducibles, described in 07.01.05, determines the eigenvalues that control both the SST bound and the Upper Bound Lemma bound.

• Character orthogonality 07.01.04. The orthogonality relations of 07.01.04 ensure that the Fourier-analytic bound isolates the non-principal representations whose decay rates determine the mixing time, complementing the SST bound which captures the same mixing through a probabilistic stopping time.

Historical & philosophical context [Master]

Aldous introduced strong stationary times in his 1983 paper ^[Aldous1983] on random walks on finite groups, establishing the coupling inequality and the connection to separation distance. Aldous and Diaconis 1986 ^{[AldousDiaconis1986]} applied SSTs to card shuffling, proving cutoff for the top-to-random shuffle and the random transposition walk using the coupon collector analysis of the dual chain.

Aldous and Diaconis 1987 ^{[AldousDiaconis1987]} developed the full theory of strong uniform times (their term for SSTs) in Advances in Applied Mathematics, proving the duality theorem and the characterisation of separation distance as the infimum over SSTs. Fill 1998 refined the duality construction, and Diaconis and Griffiths 2018 provided a modern treatment. Levin, Peres, and Wilmer 2009 systematised the coupling and SST theory in their monograph Markov Chains and Mixing Times.

Bibliography [Master]

@incollection{Aldous1983,
  author = {Aldous, David},
  title = {Random walks on finite groups and rapidly mixing Markov chains},
  booktitle = {Seminaire de Probabilites XVII},
  series = {Lecture Notes in Mathematics},
  volume = {986},
  publisher = {Springer},
  year = {1983},
  pages = {243--297},
}

@article{AldousDiaconis1986,
  author = {Aldous, David and Diaconis, Persi},
  title = {Shuffling cards and stopping times},
  journal = {Amer. Math. Monthly},
  volume = {93},
  year = {1986},
  pages = {333--348},
}

@article{AldousDiaconis1987,
  author = {Aldous, David and Diaconis, Persi},
  title = {Strong uniform times and finite random walks},
  journal = {Adv. Appl. Math.},
  volume = {8},
  year = {1987},
  pages = {69--97},
}

@book{LevinPeresWilmer2009,
  author = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
  title = {Markov Chains and Mixing Times},
  publisher = {American Mathematical Society},
  year = {2009},
}

@article{Fill1998,
  author = {Fill, James Allen},
  title = {An interruptible algorithm for perfect sampling via Markov chains},
  journal = {Ann. Appl. Probab.},
  volume = {8},
  year = {1998},
  pages = {131--162},
}

@article{DiaconisGriffiths2018,
  author = {Diaconis, Persi and Griffiths, Robert},
  title = {Column deletion and shuffling cards},
  journal = {Ann. Appl. Probab.},
  volume = {28},
  year = {2018},
  pages = {2170--2191},
}