Maths WorkshopMaths problems with full solutions
Exercise 2024Topology › Topology of Mn(ℝ) › Rank, spectrum and normsM1Added 6 Nov 2026

Dobrushin's contraction for positive stochastic matrices

#stochastic matrices#Dobrushin#oscillation#convergence of powers

Statement

Let PP be a row-stochastic n×nn\times n matrix with all entries Pij≥δ>0P_{ij}\ge\delta>0. Show that PkP^k converges, as k→∞k\to\infty, to a matrix 1πT\mathbf{1}\pi^T whose rows are all equal to the same probability vector π\pi, and that the convergence is geometric with ratio at most 1−nδ1-n\delta.

Hint

For a vector xx let osc⁡(x)=max⁡ixi−min⁡ixi\operatorname{osc}(x)=\max_ix_i-\min_ix_i. Show osc⁡(Px)≤(1−nδ)osc⁡(x)\operatorname{osc}(Px)\le(1-n\delta)\operatorname{osc}(x).

Show solutionHide solution

Solution

Step 1: rows are close. Let p,qp,q be two rows of PP, probability vectors with all entries ≥δ\ge\delta. The vector d=p−qd=p-q has zero sum, so ∑idi+=∑idi−=12∥d∥1\sum_id_i^+=\sum_id_i^-=\frac12\|d\|_1, where d±d^\pm are the positive/negative parts. Moreover
∑idi+=∑i(pi−qi)+=1−∑imin⁡(pi,qi)≤1−nδ.\sum_id_i^+=\sum_i(p_i-q_i)^+=1-\sum_i\min(p_i,q_i)\le1-n\delta.

Step 2: oscillation contracts. For x∈Rnx\in\mathbb{R}^n, (Px)r−(Px)s=d⋅x(Px)_r-(Px)_s=d\cdot x with d=pr−psd=p_r-p_s. Because ∑di=0\sum d_i=0,
d⋅x=∑di+xi−∑di−xi≤(∑di+)max⁡x−(∑di−)min⁡x=(∑di+)osc⁡(x).d\cdot x=\sum d_i^+x_i-\sum d_i^-x_i\le\Big(\sum d_i^+\Big)\max x-\Big(\sum d_i^-\Big)\min x=\Big(\sum d_i^+\Big)\operatorname{osc}(x).
Hence osc⁡(Px)≤(1−nδ)osc⁡(x)\operatorname{osc}(Px)\le(1-n\delta)\operatorname{osc}(x), and by induction osc⁡(Pkx)≤(1−nδ)kosc⁡(x)\operatorname{osc}(P^kx)\le(1-n\delta)^k\operatorname{osc}(x).

Step 3: PkxP^kx converges to a constant. Since PP is stochastic, each coordinate of PxPx is an average of the coordinates of xx: max⁡Pkx\max P^kx is nonincreasing, min⁡Pkx\min P^kx is nondecreasing, and both converge; as the oscillation tends to 00, they converge to the same limit c(x)c(x). So Pkx→c(x)1P^kx\to c(x)\mathbf{1}, with ∣Pkx−c(x)1∣∞≤(1−nδ)kosc⁡(x)|P^kx-c(x)\mathbf{1}|_\infty\le(1-n\delta)^k\operatorname{osc}(x).

Step 4: the limit matrix. cc is linear in xx (a limit of linear maps), so c(x)=π⋅xc(x)=\pi\cdot x for πi=c(ei)\pi_i=c(e_i). Taking x=eix=e_i with c(ei)≥0c(e_i)\ge0 (the entries of PkP^k are ≥0\ge0) and x=1x=\mathbf{1} with c(1)=1c(\mathbf{1})=1 shows that πi≥0\pi_i\ge0 and ∑πi=1\sum\pi_i=1. Therefore Pkx→1πTxP^kx\to\mathbf{1}\pi^Tx for each xx, i.e. Pk→1πTP^k\to\mathbf{1}\pi^T.

Example. P=(0.90.10.20.8)P=\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix} has δ=0.1\delta=0.1 and ratio ≤0.8\le0.8 (the actual second eigenvalue is 0.70.7); π=(23,13)\pi=(\frac23,\frac13).

Remark. The constant 1−nδ1-n\delta is the Dobrushin ergodicity coefficient. Also πP=π\pi P=\pi follows from 1πTP=lim⁡Pk+1=1πT\mathbf{1}\pi^TP=\lim P^{k+1}=\mathbf{1}\pi^T, and π\pi is unique, so the Markov chain forgets its initial state exponentially fast.