Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / d / Solution

Let $B=A^T$ and choose any column probability vector $q$, for example the first coordinate unit vector. Because $A$ has nonnegative entries and each row sums to one, $B$ maps the probability simplexinto itself: $Bv\ge 0$ and $1^{T}Bv=(A1{)}^{T}v=1^{T}v=1$.

The iterates $B^{j}q$ need not converge, so take their arithmetic averages,A telescoping sum givesBoth vectors on the right before subtraction have L1 norm one, so $\Vert B{x}_N-x_N{\Vert }_1\le 2/N\to 0$.

The probability simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by the Heine-Borel theorem. It follows that a subsequence $x_{N_j}$ converges to some $x\in \Delta$. Passing to the limit in the displayed identity, using continuity of the linear map $B$, gives $A^{T}x=Bx=x$, with $x\ge 0$ and ${\sum }_i{x}_i=1$.

This proves stationary distribution existence for a finite Markov chain without any Markov chain irreducibility or aperiodicity assumption. Those stronger hypotheses concern uniqueness and convergence, not the existence required here.