Fundamental Theorem of Regular Markov Chains

Let $P$ be a transition matrix of a regular Markov chain. Then $lim_{n \to \infty} P^{n} = W$ exists and all rows of $W$ are the same. Further, this common row has all positive entries.

Proof

By construction, $P^{k}$ has strictly positive entries for some $k$ . For convenience, assume $P$ has strictly positive entries.
Let $\vec{y}$ be a vector with entries greater than or equal to zero.

Denote $P^{k} \vec{y}$ as ${\vec{y}}^{(k)}$ .
Let $M_{k}$ be the largest entry of ${\vec{y}}^{(k)}$ , and let $m_{k}$ be the smallest entry of ${\vec{y}}^{(k)}$ .

Since $P^{k} \vec{y} = P (P^{k - 1}) y$ ,
${\vec{y}}^{(k)} = P {\vec{y}}^{(k - 1)}$ .

From Markov chain contraction mapping (b),
$M_{i} \leq (1 - d) M_{i - 1} + d m_{i - 1}$
$m_{i} \geq (1 - d) m_{i - 1} + d M_{i - 1}$
where $d$ is the smallest entry of $P$ .
In particular, if $P \in (0, 1)^{μ \times μ}$ , i.e. a transition matrix of dimension $μ \times μ$ , then $d \in (0, \frac{1}{μ}]$ , i.e. $d$ is strictly positive.

So,

M_{i} \leq M_{i - 1} - d M_{i - 1} + d m_{i - 1}

M_{i} - M_{i - 1} \leq d (m_{i - 1} - M_{i - 1})

Then $M_{i} > M_{i - 1}$ if and only if $m_{i - 1} > M_{i - 1}$ , which contradicts choice of $M_{i}$ and $m_{i}$ .
Therefore, $M_{i} \leq M_{i - 1}$ .

Similarly,

m_{i} \geq m_{i - 1} - d m_{i - 1} + d M_{i - 1}

m_{i} - m_{i - 1} \geq d (M_{i - 1} - m_{i - 1})

Which shows $m_{i} < m_{i - 1}$ if and only if $M_{i - 1} < m_{i - 1}$ ;
therefore, $m_{i - 1} \geq m_{i}$ .

Thus,

m_{1} < m_{2} < \dots < m_{k - 1} < m_{k} \leq \dots \leq M_{k} < M_{k - 1} < \dots < M_{2} < M_{1}

By the monotone convergence theorem, these bounded sequences converge:

lim_{n \to \infty} (m_{n}) = m

lim_{n \to \infty} (M_{n}) = M

such that $m \leq M$ .

By Markov chain contraction mapping,

\begin{aligned} M_{k} - m_{k} & \leq (1 - 2 d) (M_{k - 1} - m_{k - 1}) \\ \leq (1 - 2 d)^{2} (M_{k - 2} - m_{k - 2}) \\ ⋮ \\ \leq (1 - 2 d)^{k} (M_{0} - m_{0}) \end{aligned}

Thus,

M - n = lim_{k \to \infty} M_{k} - m_{k} \leq lim_{k \to \infty} (1 - 2 d)^{k} (M_{0} - m_{0})

Since $0 < d \leq \frac{1}{2}$ (assuming matrix is at least $2 \times 2$ ),
$0 < (1 - 2 d) < 1$ ,
so $lim_{k \to \infty} (1 - 2 d)^{k} = 0$ .

Therefore, $M - n = 0$ ,
so $M = n$ .

Thus all entries of $lim_{k \to \infty} P^{k} \vec{y}$ are the same.

Without loss of generality, choose $\vec{y} = (\begin{matrix} 0 \\ ⋮ \\ 0 \\ 1 \\ 0 \\ ⋮ \\ 0 \end{matrix})$ , i.e. a zero vector with a 1 in the $j^{t h}$ position.
Then $P^{k} \vec{y}$ is the $j^{t h}$ column of $P^{k}$ .
Since $j$ an arbitrary index, $lim_{k \to \infty} P^{k}$ has constant columns,
and therefore all rows of $lim_{k \to \infty} P^{k}$ are the same.

QED