Total variation and mixing times

For probability laws μ and ν on a finite or countable space, total variation is half the sum of absolute coordinate differences. It also equals the supremum of their difference over events, achieved by collecting coordinates where μ exceeds ν. Its values lie between zero and one under this convention. Some authors omit the factor one half when discussing an L¹ norm, so a claimed error should always identify its convention. On two states, the two coordinate discrepancies have equal magnitude, and total variation is simply the discrepancy in either single-state probability.

Applying a common Markov kernel cannot increase total variation. One proof writes an event probability after the kernel as an average of a function valued between zero and one, whose expectation discrepancy is bounded by the same event supremum. If π is stationary, this gives monotone distance to equilibrium for each fixed start and also for the worst-case maximum. Individual coordinates can still oscillate around equilibrium when an eigenvalue is negative. Monotonicity concerns the absolute distributional distance, not monotonicity of each probability bar in a diagram.

For a finite irreducible aperiodic kernel, define d(t) as the maximum over starting states of the distance between its t-step law and π. The ε-mixing time is the smallest nonnegative integer with d(t) at most ε. A mixture of starts cannot do worse than the worst point mass, by convexity, so this also controls arbitrary initial laws. The conventional unqualified mixing time often uses ε equal to one quarter, but a different tolerance must be stated explicitly rather than hidden in a numerical report.

The finite convergence theorem ensures this time is finite for every positive tolerance. Removing aperiodicity can make it infinite, and removing finiteness can leave the supremum over starts equal to one at every finite time even when each individual start converges. These qualifications matter when interpreting practical diagnostics. An observed average from one run can be accurate for a particular function while the entire distribution is still far in total variation. Conversely, a rigorous total-variation bound controls all bounded event questions simultaneously and therefore supplies a distributional guarantee rather than a visual convergence judgment.

Write p for the probability from zero to one and q for the probability back. When both are positive, the stationary masses are q/(p+q) and p/(p+q). Subtracting the stationary value from the one-state probability shows that each transition multiplies the discrepancy by 1−p−q. Therefore its absolute value contracts by the modulus of that number. The fixed start at zero has prefactor π(1), while the fixed start at one has prefactor π(0); taking the larger prefactor gives the worst-case profile.

When p+q is one, every row already equals π, so all initial laws reach stationarity in one transition. When p=q=1, the contraction modulus is one and a point-mass law never converges. Between these endpoints, solving a logarithmic inequality gives a real threshold that must be rounded upward, with a separate check when time zero already meets the tolerance. A negative multiplier creates alternating convergence but does not justify discarding every second transition or redefining the step count. The kernel, rather than the playback duration in seconds, determines the mathematical time.