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

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

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?

  • $\begingroup$ @Taylor Yes, thank you. I've edited my post to reflect that. $\endgroup$
    – nguzman
    Commented Feb 16, 2018 at 5:06

1 Answer 1


$\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.

  • $\begingroup$ 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}$. $\endgroup$
    – nguzman
    Commented Feb 16, 2018 at 5:14
  • $\begingroup$ @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}. $$ $\endgroup$
    – Taylor
    Commented Feb 16, 2018 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.