Grinstead-Snell-Probability · Problem 11.4.9

Markov Chains

Mathematics · coupling-convergence-exponential-rate

Problem

(Suggested by Peter Doyle) In the proof of Theorem 11.14, we assumed the existence of a fixed vector w\mathbf{w}. To avoid this assumption, beef up the coupling argument to show (without assuming the existence of a stationary distribution w\mathbf{w}) that for appropriate constants CC and r<1r < 1, the distance between αPn\alpha P^n and βPn\beta P^n is at most CrnCr^n for any starting distributions α\alpha and β\beta. Apply this in the case where β=αP\beta = \alpha P to conclude that the sequence αPn\alpha P^n is a Cauchy sequence, and that its limit is a matrix WW whose rows are all equal to a probability vector ww with wP=wwP = w. Note that the distance between αPn\alpha P^n and ww is at most CrnCr^n, so in freeing ourselves from the assumption about having a fixed vector we've proved that the convergence to equilibrium takes place exponentially fast.

Related theory

Browse the problem library