Worst-Case Mixing Time

From Convergence to a Worst-Case Time

For a finite Markov chain that converges to stationarity, the convergence rate can depend on where the chain starts. A state whose transition probabilities initially point away from equilibrium may take longer to become representative than another state. The worst-case mixing time records the slowest of these starting-state behaviors, giving a single accuracy guarantee that applies regardless of the initial state.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with row-stochastic transition matrix \(P=(p_{ij})\). Thus each entry is nonnegative and each row sums to \(1\). Assume throughout that the chain is irreducible and aperiodic, and let \(\pi\) be its stationary distribution, so \(\pi P=\pi\). For a finite irreducible chain, \(\pi\) is unique; for an aperiodic one, the distribution from each starting state converges to \(\pi\) in total variation. These are standard finite-chain results from the earlier material on convergence.

Here \(P^n(i,\cdot)\) is the \(i\)th row of \(P^n\), and time is an integer. The threshold is non-strict: a distance equal to \(\varepsilon\) meets the criterion. At time \(0\), the chain started at \(i\) has distribution concentrated at \(i\), so \(d_i(0)=\|\delta_i-\pi\|_{\mathrm{TV}}\). The maximum in \(d(n)\) is attained because \(S\) is finite.

Why the Worst-Case Distance Is the Right Quantity

The maximum over states gives a guarantee for any initial distribution, not just a point mass. If the initial distribution is a row vector \(\mu\), then its time-\(n\) distribution is \(\mu P^n\). Since \(\pi P^n=\pi\), convexity of total variation gives

In fact, \(d(n)\) is exactly the largest distance over all possible initial distributions: point-mass initial distributions are among those choices, and the inequality above bounds every other choice by \(d(n)\). Thus the maximum does not mean that the chain begins in a specially chosen average state. It means that we ask how slowly it could converge if its initial state is chosen adversarially.

Proof. Fix \(i\in S\). The distribution at time \(n+1\) from \(i\) is \(\sum_{j\in S}p_{ij}P^n(j,\cdot)\), and stationarity gives \(\pi=\sum_{j\in S}\pi(j)P^n(j,\cdot)\), or, more directly, \(\pi P^n=\pi\). Use the Markov property to write \(P^{n+1}(i,\cdot)=\sum_j p_{ij}P^n(j,\cdot)\). Since \(\pi=\sum_j p_{ij}\pi\) is not generally true for a fixed \(i\), instead apply the one-step transition kernel to the pair \(P^n(i,\cdot)\) and \(\pi\): \(P^{n+1}(i,\cdot)=P^n(i,\cdot)P\) and \(\pi=\pi P\). A stochastic matrix contracts total variation, so \(\|P^n(i,\cdot)P-\pi P\|_{\mathrm{TV}}\le\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\). To verify this contraction, for distributions \(\alpha,\beta\), the triangle inequality gives \(\tfrac12\sum_j|\sum_k(\alpha(k)-\beta(k))p_{kj}|\le\tfrac12\sum_k|\alpha(k)-\beta(k)|\sum_jp_{kj}=\|\alpha-\beta\|_{\mathrm{TV}}\). Therefore \(d_i(n+1)\le d_i(n)\le d(n)\). Taking the maximum over \(i\) proves \(d(n+1)\le d(n)\), and repeated application proves the consequence. \(\square\)

The finite-chain convergence result also ensures that \(t_{\mathrm{mix}}(\varepsilon)\) exists for every \(\varepsilon>0\): each \(d_i(n)\) tends to \(0\), and because there are finitely many states, their maximum tends to \(0\) as well. A quantitative reason for this finiteness comes from the positive-power criterion for finite irreducible aperiodic chains, established in the earlier material on finite-state convergence.

For the contraction claim when \(c<1\), subtract the common component for any two initial distributions \(\alpha,\beta\): \(\alpha P^r-\beta P^r=(1-c)(\alpha R-\beta R)\), where \(R\) is the stochastic matrix with rows \(R_i\). The stochastic-matrix contraction just proved bounds the resulting distance by \((1-c)\|\alpha-\beta\|_{\mathrm{TV}}\). Apply this repeatedly to distributions at times \(0,r,2r,\ldots\). The monotonicity proposition handles times between these multiples. This argument explains why a positive transition power makes the worst-case mixing time finite, without requiring a separate convergence-rate calculation for each starting state.

Worked Calculations

Common Mistakes and a Periodic Counterexample

Common mistake: average the starting-state distances instead of taking their maximum. In the two-state example, at time \(1\) the two distances are \(\tfrac1{12}\) and \(\tfrac16\). Their average is \(\tfrac12(\tfrac1{12}+\tfrac16)=\tfrac18\). Treating that average as the worst-case distance would incorrectly say the chain has mixed to accuracy \(\tfrac18\) by time \(1\). But the definition uses the maximum, which is \(\tfrac16>\tfrac18\), and the correct mixing time is \(2\). Averages can describe a chosen randomization over initial states; they do not provide a guarantee for every starting state.

Aperiodicity matters to the existence of a finite mixing time. For the chain on \(\{1,2\}\) with \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), every row sums to \(1\), the chain is irreducible, and \(\pi=(\tfrac12,\tfrac12)\) is stationary. But from state \(1\), the distribution alternates between \((1,0)\) at even times and \((0,1)\) at odd times. Its total variation distance from \(\pi\) is \(\tfrac12\) at every time, so \(d(n)=\tfrac12\) for all \(n\). For any \(\varepsilon<\tfrac12\), no finite mixing time exists. This is why the definition alone does not guarantee that the minimum is attained: convergence assumptions are needed.

In using the definition, keep three choices explicit: the stationary distribution being used, whether the initial state is fixed or maximized over, and the accuracy threshold with its non-strict comparison. For a finite irreducible aperiodic chain, the worst-case definition supplies a common time bound for every initial state; it does not claim that every state takes equally long to reach that bound.