# Long Run Proportion of Time in State of a Markov Chain

While reviewing for a stochastic processes exam, I came across the following proof in Introduction to Stochastic Processes with R by Dobrow.

The proof is for the theorem that the expected number of times an irreducible Markov chain visits a state $j$ starting from a state $i$ is given by the Markov chain's invariant distribution.

Here is the proof:

Let $(X_n)_{n\in\mathbb{N}}$ be a Markov chain with transition matrix $P$ and limiting distribution $\mathbf{\pi}$. For state $j$, define the indicator function

$$\mathbb{1}_k = 1, \quad \text{if} \ X_k = j, \quad k \in \mathbb{N}$$

Then $\sum_{k=0}^{n-1}\mathbb{1}_k$ is the number of times the chain visits $j$ in the first $n$ steps (counting $X_0$ as the first step). From initial state $i$, the long term expected proportion of time that the chain visits $j$ is

\begin{align} \lim_{n\to\infty} \mathbb{E}\left [ \frac{1}{n}\sum_{k=0}^{n-1}\mathbb{1}_k |X_0 = i\right ] &= \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}\mathbb{E}[\mathbb{1}_k |X_0 = i] \\ &= \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1} \mathbb{P}[X_k=j|X_0=i] \\ &= \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1} P^{k}_{ij} \\ &= \lim_{n\to\infty}P^n_{ij} = \mathbf{\pi}_j \end{align}

where the factor of $1/n$ disappears in the last equality due to Cesaro's lemma. My point of confusion is the last equality. To my mind,

$\sum_{k=0}^{n-1} P^{k}_{ij} = (I + P + P^2 +... + P^{n-1})_{ij}$

where $I$ is the identity matrix. So I cannot understand how Dobrow arrives at

$\sum_{k=0}^{n-1} P^{k}_{ij} = P^n_{ij}$

Could someone help me to understand this?

• @Taylor Yes, thank you. I've edited my post to reflect that. Feb 16, 2018 at 5:06

$\sum_{k=0}^{n-1} P^{k}_{ij}$ is a sum of constants. For each $k$, $P_{ij}^k$ is a scalar element (the $ij$th element of the $k$th step transition matrix. This follows directly from Cesaro's Lemma, as you say.
• Thank you for your reply. I see what you're saying, but I still don't understand why $\sum_{k=0}^{n-1} P^k_{ij}$ converges to $P^n_{ij}$ since it seems to me that we must have $\sum_{k=0}^{n-1} P^k_{ij} > P^n_{ij}$. Feb 16, 2018 at 5:14
• @nguzman Cesaro's Lemma says that if $(b_n)$ is a sequence of positive real numbers monotonically increasing to $\infty$, and $(v_n)$ is a convergent sequence of real numbers such that $v_n \to v_{\infty}$, then $$\frac{1}{b_n}\sum_{k=1}^n (b_k - b_{k-1})v_k \to v_{\infty}.$$ Feb 16, 2018 at 5:20