Markov models and occupation time

Question

I'm presented with the following explanation and proof:

Let $(X_n)$ be a Markov chain, and fix a state $j \in S$.

Define indicator variables: For $n = 0, 1, \dots$, let

$$I_n(j) = \begin{cases} 1 & \text{if} \ X_n = j, \\ 0 & \text{if} \ X_n \not= j. \end{cases}$$

$I_n(j) = 1$ says that the MC occupies state $j$ at time $n$.

The probability $I_n(j) = 1$ is $p^{(n)}_{ij}$ if $X_0 = i$.

$I_n (j)$ has a Bernoulli law with parameter $p^{(n)}_{ij}$.

Lemma 2. $E(I_n (j) \vert X_0 = i) = p^{(n)}_{ij}$.

Let $N_n (j) = \sum_{m = 0}^n I_m (j), \tag{6}$

$N_n (j)$ is called the occupation time of the state $j$ (up to time $n$).

Note that $\sum_{j \in S} N_n (j) = n + 1$.

The mean occupation time of state $j$, given the initial state $i$, is

$$m_{ij}(n) = E(N_n(j) \vert X_0 = i), \ \text{for all} \ i, j \in S.$$

Then $M(n) = (m_{ij}(n))_{ij}$ is called the mean occupation time matrix.

Theorem 3. The mean occupation time matrix is given by

$$M(n) = \sum_{m = 0}^n \mathcal{P}^m \tag{7}$$

Proof: It follows from Lemma 2 and (6) that

$$m_{ij}(n) = \sum_{m = 0}^n E[I_m (j) \vert X_0 = i] = \sum_{m = 0}^n p^{(m)}_{ij}.$$

$\mathcal{P}^n$ is the $n$-step transition matrix.

I am having difficulty understanding the above proof. Specifically, I'm having difficulty understanding how $m_{ij}(n) = \sum_{m = 0}^n E[I_m (j) \vert X_0 = i] = \sum_{m = 0}^n p^{(m)}_{ij}$ follows from Lemma 2 and (6). I would greatly appreciate it if people would please take the time to clarify this.

Answer 1

If you understand Lemma 2 and Equation (6), the rest is just linearity of expectation:

$$\begin{align}m_{ij}(n)&=E[N_n(j)|X_0=i]=E\left[\sum_{m=0}^n I_m(j)\bigg\vert X_0=i\right]=\sum_{m=0}^n E[I_m(j)|X_0=i]\\&=\sum_{m=0}^np_{ij}^{(m)}\end{align}$$

Intuitively, $p_{ij}^{(m)}$ represents how certain we're at $j$-th state at our $m$-th step. If it's $0.1$, we'll be at $j$-th state $0.1$ of the time if we do an experiment, i.e. run the markov chain multiple times. So, summing these expected occupation numbers will yield the mean occupation.

For the simplest case, take all $p_{ij}^{m}=1$, which means the mean occupation is $n+1$ because at every step (out of $n+1$ steps) we're guaranteed to be there.