Spectral gaps and relaxation times

Assume a finite irreducible reversible chain on at least two states, with stationary law π. List its real eigenvalues in decreasing order, beginning with the simple eigenvalue one. The ordinary gap is one minus the second largest eigenvalue. The absolute gap instead subtracts the largest modulus among all nonconstant eigenvalues. The ordinary gap is positive under irreducibility; the absolute gap is positive exactly when the chain is also aperiodic. A near-minus-one eigenvalue barely affects the ordinary gap but can dominate the actual discrete-time decay.

Here relaxation time means the reciprocal absolute gap, following the convention used by the cited text; for lazy chains it also equals the reciprocal ordinary gap. Naming this convention matters because some literature uses ordinary-gap relaxation time without the absolute qualifier. Weighted variance contracts by the square of the largest nonconstant eigenvalue modulus at each transition. An eigenfunction attaining that modulus achieves equality, so this rate is not merely a convenient estimate: it detects the slowest reversible L² mode.

Reversibility makes the density of a t-step law relative to π evolve by the same self-adjoint operator. Subtract its constant component and apply the spectral contraction. The initial point-mass density at x has squared weighted norm one divided by π(x), minus one. Cauchy–Schwarz converts its weighted L² error into an L¹ error, introducing the total-variation factor one half. Taking the smallest stationary mass gives a bound uniform over starting states. This prefactor records the cost of concentrating initially on an improbable state.

The resulting inequality is a general upper bound and can exceed one at early times, in which case the trivial bound one is better. Replacing the geometric factor by an exponential gives a convenient logarithmic mixing estimate involving the inverse absolute gap and the smallest stationary mass. A gap estimate alone is not an exact mixing time, because different modes and prefactors contribute. The finite-state assumptions also avoid unbounded point-mass densities and continuous spectral complications that require separate arguments on countable or general spaces.

Replacing P by its average with the identity changes an eigenvalue λ to (1+λ)/2. All new eigenvalues lie between zero and one. A mode near minus one then moves near zero and loses its oscillatory obstruction, while a positive eigenvalue near one moves even closer to one and decays more slowly per transition. Thus the blanket claim that laziness always halves speed, or always accelerates mixing, is false. Its effect depends on which end of the original spectrum controls convergence.

For the two-state chain, the only nonconstant eigenvalue is 1−p−q, so the distinction is completely visible. A large sum of transition probabilities produces alternating convergence; a small sum produces slow monotone convergence. The same stationary law can coexist with very different decay rates if p and q are scaled together. This observation links spectral analysis back to actual transition design: preserving the target distribution is necessary for sampling, but the chosen dynamics determine how long one must wait to obtain an approximately stationary draw.