Mixing time of a Markov chain ($t_{\mathrm{mix}}(\epsilon )$)

The $\epsilon$-mixing time is the least $t$ for which every initial state has total variation distance at most $\epsilon$ from the invariant distribution after $t$ steps.

If $r={\max }_{j\ge 2}|{\lambda }_j|$ for a finite irreducible Markov chain with at least two states, then its worst-case total variation distance from its stationary distribution satisfies $d(t)\ge r^t/2$. Choose a possibly complex eigenfunction $f$ for an eigenvalue of modulus $r$, normalize ${\max }_x|f(x)|=1$, and start where the maximum is attained. Since $\pi (f)=0$, $|P^{t}f(x)-\pi (f)|=r^t$; the defining sum for total variation distance bounds this difference by $2d(t)$. For $0<r<1$, this yields $t_{\mathrm{mix}}(\epsilon )\ge (r/(1-r))\log (1/(2\epsilon ))$ for $0<\epsilon <1/2$, because $-r\log r\le 1-r$.

For a finite Markov chain with transition matrix $P$, define $\bar{d}(t)={\max }_{x,y}\Vert P^t(x,\cdot )-P^t(y,\cdot ){\Vert }_{\mathrm{TV}}$. If $\pi$ is a stationary distribution and $d(t)={\max }_x\Vert P^t(x,\cdot )-\pi {\Vert }_{\mathrm{TV}}$, then $d(t)\le \bar{d}(t)\le 2d(t)$. The first bound follows by writing $\pi ={\sum }_y\pi (y)P^t(y,\cdot )$ and using the triangle inequality; the second uses the triangle inequality through $\pi$.

A randomized stopping time $\tau$ is a strong stationary time for a Markov chain with stationary distribution $\pi$ when $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$. Equivalently,

For a finite Markov chain with stationary distribution $\pi$, the separation distance from an initial state $x$ isIf $\tau$ is a strong stationary time, then $s_x(t)\le {\mathbb{P}}_x(\tau >t)$, and total variation distance is at most separation distance.

For a finite transitive reversible chain with nontrivial eigenvalues ${\lambda }_i$,

A sequence of chains exhibits cutoff when its distance from stationarity drops from near one to near zero in a time window negligible compared with its mixing-time scale.

The ratio convention for cutoff for Markov chains requires $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for every fixed $0<\epsilon <1/2$, with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph $K_n$, every fixed-level mixing time is eventually one.

For finite irreducible Markov chains that are aperiodic Markov chains and reversible Markov chains, the ratio definition of cutoff and $T_n=t_{\mathrm{mix}}^{(n)}(1/4)\to \infty$ imply the Peres product condition, with ${\gamma }_n=1-{\lambda }_{2,n}$. If ${\gamma }_n{T}_n\le B$ on a subsequence, then ${\gamma }_{\ast ,n}\le {\gamma }_n$ and the eigenvalue lower bound for total variation mixing giveFor sufficiently small fixed $\epsilon$, this contradicts the limit one forced by cutoff for Markov chains. The same argument proves the stronger conclusion ${\gamma }_{\ast ,n}{T}_n\to \infty$.

The random-to-top shuffle chooses one uniformly random card and moves it to the top of the deck. The time at which every card has been chosen is a strong stationary time, yielding cutoff at $n\log n$ with a window of order $n$.

The top-to-random shuffle removes the top card and inserts it in a uniformly random position. Under the uniform measure on permutations it is the time reversal of the random-to-top card shuffle, so the two shuffles have the same total-variation mixing profile.

A sequence of chains exhibits pre-cutoff if there are constants $0<A<B<\infty$ and times $t_n$ such that the worst-case distance tends to one at $A{t}_n$ and to zero at $B{t}_n$. For reversible chains, the product condition $t_{\mathrm{rel}}=o(t_{\mathrm{mix}})$ is necessary for pre-cutoff.

For $\tilde{P}=(1-a)P+a\Pi$, where every row of $\Pi$ equals the stationary distribution $\pi$,The perturbation superposes gradual exponential mixing on the original profile and can destroy pre-cutoff.

A shift-refresh chain cyclically moves a pointer through the coordinates of a bit vector and replaces the visited bit by an independent fair bit. Once the pointer walk has visited every residue, all coordinates have been refreshed, giving a strong stationary time.

If adjacent states admit one-step couplings that contract a path metric by a common factor, then the induced Wasserstein distance contracts by the same factor for arbitrary starting distributions.