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 '20 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$ – The Pointer Mar 16 '20 at 20:01

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$ – The Pointer Mar 16 '20 at 20:51
  • 1
    $\begingroup$ yes, just changed it. $\endgroup$ – gunes Mar 16 '20 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$ – The Pointer Mar 16 '20 at 21:59
  • 1
    $\begingroup$ it’s just linearity of the expectation $\endgroup$ – gunes Mar 16 '20 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 '20 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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