# Convergence of Markov Chains

I have stumbled upon Markov chains respectively finite stochastic matrices (gladly it didn't hurt too much). There is this theorem on the existence of stationary distributions which is standard:

Let P be a stochastic matrix of dimension $$N\times N$$. Assume that there is some power $$P^n$$ of P such that every entry of $$P^n$$ is (strictly) greater than zero. Then the stochastic process $$(P^n)_{n\geq0}$$ converges to a stochastic matrix $$Q$$ whose columns are identical.

Here, I follow the convention that a stochastic matrix has stochastic column vectors, i.e., the entries of any given column sum up to 1. This seems to be standard in german text books.

Now in a german schoolbook (Lambacher Schweizer, Mathematik Jahrgangsstufe), I found the following weaker version of the above theorem which looks like this:

Let P be a stochastic matrix of dimension $$N\times N$$. Assume that there is some power $$P^n$$ of P such there is some row of $$P^n$$ whose entries are all (strictly) greater than zero. Then the stochastic process $$(P^n)_{n\geq0}$$ converges to a stochastic matrix $$Q$$ whose columns are identical.

Can somebody give a (possibly elementary) proof of this of give a counterexample? I could neither prove nor disprove it to myself (actually I believe it's true) nor could I modify find it in the literature.

Thanks, Martin

• it's hard to guess your background knowledge. Do you know that a Perron root is semi-simple and that its multiplicity counts the number of recurrent classes? Oct 10, 2020 at 19:43
• @user8675309 no, I don't have any background knowledge at all w.r.t. markov chains. But honestly, there must be an elementary proof of the above weak version. At least, I know of an elementary one for the strong version and it would seem very strange to me if the weak version's proof is much different. At least, what I read from your comment is that the statement is true, isn't it? Oct 11, 2020 at 8:21
• The second statement is true and relatively straightforward if you already know about transient states. Oct 11, 2020 at 20:24
• "gladly it didn't hurt too much" - good to hear, if mathematics regularly causes you physical pain I suggest you consult a doctor however :) Oct 28, 2020 at 7:39

## 1 Answer

I'm not sure why you'd call the second theorem 'weaker' as it nominally seems stronger / more general. Clearly the first theorem can be seen as a special case of the second one. After dealing with/modding out transient states, we can see the first theorem also implies the second one. Unfortunately there are some book-keeping details associated with transient states that distract from the argument.

For the second theorem, we can assume WLOG that row $$1$$ is the positive row. What the condition tells you is that all states have paths to state 1. Now WLOG the first $$m$$ states are reachable from state 1. That is $$\{1,2,...,m\}$$ forms a recurrent class. Any state $$j\gt m$$ is transient since they visit state 1 with positive probability and have no probability of returning from there (you can upper bound the expected number of returns with a geometric series hence one doesn't return infinitely often and the state j is transient). The above implies a blocked structure

$$P= \left[ \begin{matrix} P_{m\times m} & * \\ \mathbf 0 & T\\ \end{matrix}\right]$$
and you are using column stochastic matrices so $$\mathbf 1^T P =\mathbf 1^T$$

by blocked multiplication
$$P^k= \left[ \begin{matrix} P_{m\times m}^k & * \\ \mathbf 0 & T^k\\ \end{matrix}\right]$$

and of course $$\mathbf 1^T \mathbf P^k = \mathbf 1^T$$.

Now as a basic property of transient states we know $$T^k\to \mathbf 0$$. (Alternatively for a spectral reason, apply Gerschgorin Discs to $$T^n$$ to see its max modulus eigenvalue is $$\lt 1$$ hence $$T$$ has max modulus eigenvalue $$\lt 1$$ and $$T$$ tends to zero.)

now selecting $$k:=n$$ we see
$$(P_{m\times m})^n$$
has all positive numbers on its first row. What this means is that in $$n$$ steps there is a path from any state $$j\in \{1,2,...,m\}$$ to state 1. Being a single communicating class, state 1 has a path to some other state $$i$$ in one step, i.e. $$\mathbf e_i^T P_{m\times m}\mathbf e_1\gt 0$$ for some $$i \in\{2,...,m\}$$

but this means there is a path $$1\to i \to 1$$ of length $$n+1$$, as well as a path of length $$n$$, hence the GCD of paths in this recurrent class is $$1$$.

2 standard exercises:
i.) the first $$m$$ states form a single communicating class, so prove that each may reach another in at most $$m$$ steps.
ii.) By calculation, prove that the GCD of 1 implies $$(P_{m\times m})^k$$ has all positive components for $$k\geq K$$.
(This can be avoided by exploiting special structure in the problem -- see the "addendum")

conclusion
now apply theorem (1) and you see $$\lim_{k\to \infty} (P_{m\times m})^k = \mathbf \pi\mathbf 1_m^T$$

more about transient states
You'll notice I ignored the $$*$$'d upper right quadrant in this proof as it is not really important and involves some book-keeping. Here are some of these less important details.

Since the characteristic polynomial of $$P$$ splits into
$$\det\big(xI-P) = \det\big(xI-P_{m\times m}\big)\cdot\det\big(xI- T\big)$$
what the above tells you is that $$P$$ has a single eigenvalue on the unit circle, $$\lambda =1$$ with algebraic multiplicity of one -- this is implicit e.g. in considering that the trace of $$\lim_{k\to \infty} P_{m\times m}^k$$ which is one which implicitly tells you that $$P_{m\times m}\mathbf \pi = \mathbf \pi$$ because if for $$\mathbf x \not \propto \mathbf \pi$$ satisfied $$P_{m\times m}\mathbf x = \mathbf x$$ then $$\mathbf x =\lim_{k\to \infty} P_{m\times m}^k\mathbf x = \mathbf \pi(\mathbf 1_m^T\mathbf x)$$ which is a contradiction.

Revisiting the characteristic polynomial of $$P$$, we know that up to re-scaling there is a single vector that satisfies $$\mathbf y^T P = \mathbf y^T$$, and we already know this is $$\mathbf 1$$. And up to re-scaling we know there is a single vector that satisfies $$P\mathbf z = \mathbf z$$, and
$$P= \left[ \begin{matrix} P_{m\times m} & * \\ \mathbf 0 & T\\ \end{matrix}\right]\left[ \begin{matrix} \mathbf z' \\ \mathbf z'' \\ \end{matrix}\right]= \left[ \begin{matrix} * \\ T\mathbf z'' \\ \end{matrix}\right]=\mathbf z = \left[ \begin{matrix} \mathbf z' \\ \mathbf z'' \\ \end{matrix}\right]$$

but $$T\mathbf z'' = \mathbf z''\implies \mathbf z''=\mathbf 0$$ since $$T$$ cannot have an eigenvalue of $$1$$. Which implies $$\mathbf z' =\mathbf \pi$$ or
$$\mathbf z =\left[ \begin{matrix} \mathbf \pi \\ \mathbf 0 \\ \end{matrix}\right]$$

Finally $$B:=\big(P-\mathbf z\mathbf 1^T\big)$$ and confirm $$B^k=\big(P^k-\mathbf z\mathbf 1^T\big)$$, and all of $$B$$'s eigenvalues have modulus $$\lt 1$$ thus $$\mathbf 0 = \lim_{k\to \infty} B^k=\lim_{k\to \infty} \big(P-\mathbf z\mathbf 1^T\big)^k=\lim_{k\to \infty} P^k-\mathbf z\mathbf 1^T$$
or $$\lim_{k\to \infty} P^k=\mathbf z\mathbf 1^T$$

Addendum
An easier way to show that $$(P_{m\times m})^k$$ has all positive components for all $$k\geq K$$ is as follows.
First note that

$$(P_{m\times m})^{2n}=(P_{m\times m})^{n}(P_{m\times m})^{n}$$
has all positive components in row 1 (why?) and by induction
$$(P_{m\times m})^{n\cdot k'}$$
has all positive components in row 1 and for any natural number $$k'$$

Now we adapt this to the other states and since this is a communicating class, for each state $$j\in\{2,3,...,m\}$$ there exists some $$k_j \in \{1,...,m\}$$ such that there is a path from state 1 to state $$j$$. in other words there exists

$$\mathbf e_j^T (P_{m\times m})^{k_j}\mathbf e_1 \gt 0$$
Thus $$(P_{m\times m})^{k_j\cdot n} = P_{m\times m}^{k_j}P_{m\times m}^{k_j\cdot(n-1)}$$
has all positive components in row $$j$$. (It's probably easier to work with the transpose to confirm this.)

set $$k' := \prod_{j=2}^r k_j$$ and it follows that
$$(P_{m\times m})^{k'\cdot n}$$
has strictly positive components (is a positive matrix). It immediately follows that
$$(P_{m\times m})^{k'\cdot n+1}=(P_{m\times m})^{k'\cdot n}(P_{m\times m})$$ is a positive matrix and by induction it follows that
$$(P_{m\times m})^{k}$$
is a positive matrix for all $$k\geq K:= n\cdot\big(\prod_{j=2}^r k_j\big)$$
which now allows for application of theorem 1.

• Sorry, of course the second version is indeed stronger; I referred to the assumptions which are weaker for the second version (and which is why the strength is the other way round)... well, I must admit that I just haven't expected such a much more difficult proof as I had learned for the first (weaker!) version. And, to be honest, what you'd called less important details were important details to me because it isn't obvious to me at all how you would deduce from the left upper quadrant to the upper right one. One last question: can you recommend some further (elementary) reading on this? Oct 15, 2020 at 15:30
• Oh sorry, I almost forgot the most important thing to say here: thank you for giving the proof user8675309! Oct 15, 2020 at 15:32
• It's a very broad topic with many different approaches. Broadly speaking for finite state chains the tools come from (1) countable state chains, (2) renewal theory, or (3) linear algebra. I don't find many people on this site that use (2). I mostly used (3) in the above. Recommendations: the 2nd to last chapter of Grinstead & Snell's free book math.dartmouth.edu/~prob/prob/prob.pdf which is a peculiar blend of lin alg and probabilistic arguments. If you want something that uses more lin alg and develops Perron-Frobenius Theory, then Meyer's Matrix Analysis's chapter is nice. Oct 15, 2020 at 16:18
• ok thank's so far. I have checked your answer, although it will probably take me a while to fully understand all the details. Oct 16, 2020 at 19:35
• @MartinMonath -- My proof should be understandable if you know a little about blocked matrices and that $\lim_{k\to \infty} M^k =\mathbf 0$ iff $\max \big\vert \lambda_k\big \vert \lt 1$ which is conceptually simple but takes a bit of work /machinery to prove. There may be something simpler than my posting in Grinstead and Snell's book-- they use matrices extensively but for some reason eschew using eigenvalues and eigenvectors. There are also some nice probabilistic arguments in there using coupling and martingales and many other things. Oct 16, 2020 at 22:54