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.

  • $\begingroup$ Did you understand Lemma 2 and/or (6) individually? $\endgroup$
    – gunes
    Mar 16, 2020 at 19:38
  • 1
    $\begingroup$ @gunes I think so. I think the way in which they come together is what is confusing me. Or it could indeed be that I am not understanding them sufficiently individually, and so that's what's causing me difficulty in understanding them together. $\endgroup$ Mar 16, 2020 at 20:01

1 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.

  • $\begingroup$ Is $m^n_{ij}$ supposed to be $m_{ij}(n)$? $\endgroup$ Mar 16, 2020 at 20:51
  • 1
    $\begingroup$ yes, just changed it. $\endgroup$
    – gunes
    Mar 16, 2020 at 20:59
  • $\begingroup$ So the conditional expected value of a sum is the sum of the conditional expected value? Is this just an application of "pulling out known factors" en.wikipedia.org/wiki/Conditional_expectation#Basic_properties ? $\endgroup$ Mar 16, 2020 at 21:59
  • 1
    $\begingroup$ it’s just linearity of the expectation $\endgroup$
    – gunes
    Mar 16, 2020 at 22:39
  • 1
    $\begingroup$ If $p_{ij}^{m}=1$, for all $m$, it means you're there every time, like absorbing state. So, you'll be there a total of $n+1$ times, including the initial which is for $m=0$. $\endgroup$
    – gunes
    Mar 17, 2020 at 7:47

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.