Lower Bounds from Slow Escape and Bottleneck Sets

Slow Escape as a Test for Mixing

A chain can have a stationary distribution and still take a long time to resemble it when started from an unfavorable state. One way to detect this delay is to find a set that holds substantial stationary probability but has little probability flow across its boundary. A chain started in that set is unlikely to leave quickly, so its distribution remains concentrated there while stationarity assigns positive mass outside. This discrepancy gives a lower bound on total variation distance.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Let \(\pi\) be a stationary distribution, so \(\pi P=\pi\). For probability distributions \(\nu,\eta\) on \(S\), use the total variation distance \(\|\nu-\eta\|_{\mathrm{TV}}=\sup_{B\subseteq S}|\nu(B)-\eta(B)|\). Define \(d(n)=\max_{i\in S}\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\), and for \(0<\varepsilon<1\) define \(t_{\mathrm{mix}}(\varepsilon)=\inf\{n\ge0:d(n)\le\varepsilon\}\), with the infimum set to \(\infty\) if no such integer exists.

The key comparison starts the chain from the conditional distribution \(\pi_A(i)=\pi_i\mathbf{1}_{\{i\in A\}}/\pi(A)\). If escape by time \(n\) is unlikely under this initial distribution, then the probability of being in \(A\) at time \(n\) remains much larger than \(\pi(A)\). Although this start is a distribution rather than a single state, it still gives a lower bound on the worst-case distance: a mixture of starting states cannot be farther from stationarity than the largest distance among its components.

Proof. Write \(\mu=\pi_A\), and start the chain with distribution \(\mu\). For each \(k\ge1\), consider the event that the first exit from \(A\) occurs on step \(k\). The distribution at time \(k-1\), without imposing any restriction on the path, is \(\mu P^{k-1}\). Since \(\mu(i)\le\pi_i/\pi(A)\) for each \(i\), multiplying by the nonnegative matrix \(P^{k-1}\) gives \((\mu P^{k-1})(i)\le(\pi P^{k-1})(i)/\pi(A)=\pi_i/\pi(A)\). The first-exit event is contained in the event \(X_{k-1}\in A,\ X_k\notin A\). Therefore its probability is at most \[ \sum_{i\in A}\sum_{j\notin A}(\mu P^{k-1})(i)p_{ij} \le \frac{Q(A,A^c)}{\pi(A)} =\Phi(A). \] The events that the first exit occurs on steps \(1,\ldots,n\) are disjoint. Adding their probability bounds shows that the probability of any exit by time \(n\) is at most \(n\Phi(A)\). Consequently \((\mu P^n)(A)\ge1-n\Phi(A)\), including \(n=0\), when the chain starts in \(A\) with probability one. By the definition of total variation, \[ \|\mu P^n-\pi\|_{\mathrm{TV}}\ge(\mu P^n)(A)-\pi(A)\ge1-\pi(A)-n\Phi(A). \] Finally, \(\mu P^n=\sum_{i\in A}\mu(i)P^n(i,\cdot)\). The triangle inequality for total variation gives \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le\sum_{i\in A}\mu(i)\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\le d(n)\). This proves the bound. If \(\Phi(A)>0\), the stated strict inequality on \(n\) makes the bound strictly greater than \(\varepsilon\). If \(\Phi(A)=0\), the bound reduces to \(d(n)\ge1-\pi(A)\) for every \(n\). \(\square\)

The theorem requires stationarity of \(\pi\) and positive mass \(\pi(A)\), but it does not require irreducibility, aperiodicity, or reversibility. It is a lower bound, not a convergence theorem: a positive escape ratio does not by itself guarantee that the chain mixes. The bound is most informative when \(A\) has substantial stationary mass and a small escape ratio.

Checking the Bound on a Two-State Chain

A small example helps distinguish the stationary mass of a set from its escape ratio. The mass determines how much probability must eventually be found outside the set under stationarity; the ratio controls how quickly a start conditioned to be inside can lose that concentration.

Zero Flow and a Necessary Qualification

When \(\Phi(A)=0\), the theorem is useful without dividing by the escape ratio. The zero-flow case can occur even when \(A\) and \(A^c\) both have positive stationary mass. It says that a chain started according to \(\pi\) conditioned on \(A\) never crosses from \(A\) to \(A^c\) at a step sampled under that distribution. The theorem then prevents the worst-case distance from falling below \(1-\pi(A)\).

Common mistake. It is invalid to use the positive-flow threshold when \(\Phi(A)=0\). For the identity chain just computed, choosing, for example, \(\varepsilon=\tfrac14\) gives \(1-\pi(A)-\varepsilon=\tfrac14>0\). Writing \(n<(\tfrac14)/0\) is undefined, not a mixing-time conclusion. The correct argument is the separate zero-flow conclusion: \(d(n)\ge1-\pi(A)=\tfrac12>\tfrac14\) for every \(n\), so no finite time achieves that accuracy.

More generally, to use a bottleneck set effectively, check the quantities in order: \(\pi(A)>0\) so the conditional start is defined; \(\pi(A)<1\) so there is stationary mass outside; and then whether \(\Phi(A)\) is positive or zero. In the positive case, compare members of the family \(n\) at the same threshold using the strict inequality in the theorem. In the zero case, use the separate all-times bound. This turns a structural observation about a set into a quantitative obstruction to rapid mixing.