Mixing Profiles and Accuracy Thresholds

The Profile Behind a Mixing Time

A mixing time is a single number attached to a chosen accuracy level. The full sequence of distances from stationarity contains more information: it shows how quickly the chain approaches equilibrium and how that rate changes as the required accuracy becomes stricter. This sequence is called the worst-case mixing profile. Reading it carefully also prevents a common mistake: measuring convergence from one convenient initial distribution and treating that result as a worst-case guarantee.

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 row-stochastic transition matrix \(P=(p_{ij})\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Assume throughout that the chain is irreducible and aperiodic, and let \(\pi\) be its stationary distribution, written as a row vector, so \(\pi P=\pi\). The standard finite-state convergence theorem says that under these hypotheses \(\pi\) is unique and \(P^n(i,\cdot)\) converges to \(\pi\) for every \(i\); that theorem was established in the earlier material on finite-state convergence.

For probability distributions \(\nu\) and \(\eta\) on \(S\), their total variation distance is \(\|\nu-\eta\|_{\mathrm{TV}}=\tfrac12\sum_{j\in S}|\nu(j)-\eta(j)|\). It lies between \(0\) and \(1\). For each integer \(n\ge0\), define the worst-case distance from stationarity by

Thus \(d(n)\) asks how far the chain can still be from equilibrium after \(n\) steps, when the starting state is chosen as unfavourably as possible. For an accuracy threshold \(\varepsilon>0\), define the mixing time

If the set in this definition is empty, its minimum is taken to be \(\infty\). Under the finite, irreducible, aperiodic assumptions above, \(d(n)\to0\), so the mixing time is finite for every \(\varepsilon>0\). In the one-state case, \(d(n)=0\) for all \(n\), and \(t_{\mathrm{mix}}(\varepsilon)=0\) for every positive \(\varepsilon\).

Why the Profile Cannot Increase

The Markov transition itself cannot increase total variation distance between two distributions. Here is the finite-state calculation. For row distributions \(\nu,\eta\), the \(j\)th coordinate of \((\nu-\eta)P\) is \(\sum_i(\nu(i)-\eta(i))p_{ij}\). Since \(p_{ij}\ge0\), the triangle inequality and the row sums of \(P\) give

Proof. Fix any state \(i\). Since \(\pi P=\pi\), we have \(P^{n+1}(i,\cdot)=P^n(i,\cdot)P\) and \(\pi=\pi P\). Apply the total variation contraction just calculated with \(\nu=P^n(i,\cdot)\) and \(\eta=\pi\). This gives \(\|P^{n+1}(i,\cdot)-\pi\|_{\mathrm{TV}}\le\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\). Taking the maximum over \(i\) on the left and using the defining maximum on the right proves \(d(n+1)\le d(n)\). If \(\varepsilon_1\le\varepsilon_2\), every \(n\) satisfying \(d(n)\le\varepsilon_1\) also satisfies \(d(n)\le\varepsilon_2\). The first such time for the stricter threshold cannot be earlier, proving the mixing-time comparison. \(\square\)

Monotonicity gives a precise way to interpret a reported mixing time. If \(t_{\mathrm{mix}}(\varepsilon)=m\ge1\), then \(d(m)\le\varepsilon\), while \(d(m-1)>\varepsilon\); otherwise the threshold would have been reached earlier. Equivalently, the thresholds for which the mixing time is exactly \(m\) are those satisfying \(d(m)\le\varepsilon<d(m-1)\). For \(m=0\), the condition is simply \(d(0)\le\varepsilon\). Equality at the first time counts as having met the threshold.

Proof. Suppose first that \(t_{\mathrm{mix}}(\varepsilon)=m\). The definition gives \(d(m)\le\varepsilon\); if \(d(m-1)\le\varepsilon\), then \(m-1\) would be an earlier time satisfying the defining condition, a contradiction. Hence \(d(m-1)>\varepsilon\). Conversely, if \(d(m)\le\varepsilon<d(m-1)\), time \(m\) satisfies the condition and time \(m-1\) does not. Since \(d(n)\) is nonincreasing, every \(n<m\) has \(d(n)\ge d(m-1)>\varepsilon\). Thus \(m\) is the first qualifying time. \(\square\)

Exact Profiles and Threshold Comparisons

Worst-Case Starts and a Common Error

The maximum over starting states is essential. More generally, allowing any initial distribution \(\mu\) does not change the worst-case value: \(\sup_\mu\|\mu P^n-\pi\|_{\mathrm{TV}}=d(n)\). To see this, write \(\mu=\sum_i\mu(i)\delta_i\). The triangle inequality gives \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le\sum_i\mu(i)\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\le d(n)\). In the other direction, each point mass \(\delta_i\) is itself an allowed initial distribution, so the supremum is at least the maximum over states. The two quantities are equal.

Common pitfall. A mixing-time statement must specify both the distance and the worst-case convention. Averaging distances over starting states is not the same as taking their maximum. In the last example, an average or a favourable starting distribution can lie below a threshold while another starting state remains above it. A second error is to use \(d(n)<\varepsilon\) instead of the defined condition \(d(n)\le\varepsilon\): exact equality counts as having reached the threshold, as the first example at \(n=2\) demonstrates.

The profile and the threshold answer related but distinct questions. The profile compares distances at each fixed time; the threshold mixing time asks for the first time that a selected accuracy is reached. Monotonicity guarantees that once the threshold is reached it remains satisfied, and the interval characterization tells exactly which thresholds correspond to each integer mixing time. The explicit examples show why it is useful to retain the profile rather than report only one mixing-time value.