1
$\begingroup$

I am currently learning about the balance equations, mass equation, limit law, occupation law and stationary law in Markov models. The following example is presented:

Example 2:

$$\mathcal{P} = \begin{bmatrix} 0 & 1 & 0 \\ 0.1 & 0 & 0.9 \\ 0 & 1 & 0 \end{bmatrix}.$$

The balance equations are

$$\pi_1 = 0.1 \pi_2, \ \pi_2 = \pi_1 + \pi_3, \ \pi_3 = 0.9\pi_2$$

The mass equation is

$$\pi_1 + \pi_2 + \pi_3 = 1$$

The unique solution to this balance plus mass system is

$$\pi_1 = 0.05, \ \ \ \pi_2 = 0.5, \ \ \ \pi_3 = 0.45.$$

So once again: if there is a limit law, then this is it.

However, a calculation shows that

$$\mathcal{P}^2 = \begin{bmatrix} 0.1 & 0 & 0.9 \\ 0 & 1 & 0 \\ 0.1 & 0 & 0.9 \end{bmatrix},$$

and that $\mathcal{P}^3 = \mathcal{P}$.

It follows that $\mathcal{P}^{2m - 1} = \mathcal{P}$ and $\mathcal{P}^{2m} = \mathcal{P}^2$ for $m = 1, 2, \dots$.

Thus the powers of $\mathcal{P}$ oscillate and do not converge; there is no limit law.

The following is then said:

In example 2, counting the oscillating terms shows that

$$m_{ij}(n) = \begin{cases} \delta_{ij} + \dfrac{1}{2} n(p_{ij} + p^{(2)}_{ij}) & \text{if} \ n \ \text{is even,} \\ \delta_{ij} + \dfrac{1}{2} (n + 1)p_{ij} + \dfrac{1}{2}(n - 1) p^{(2)}_{ij} & \text{if} \ n \ \text{is odd.} \end{cases}$$

Dividing by $n$, you will see that the limit exists and

$$\pi^*_{ij} = \dfrac{1}{2} (p_{ij} + p^{(2)}_{ij}) = \dfrac{1}{2}(0.1, 1, 0.9)$$

So we have a unique stationary law which is an occupation law, but no limit law exists.

There are two points of this that I am unclear on:

  1. How did the author get

$$m_{ij}(n) = \begin{cases} \delta_{ij} + \dfrac{1}{2} n(p_{ij} + p^{(2)}_{ij}) & \text{if} \ n \ \text{is even,} \\ \delta_{ij} + \dfrac{1}{2} (n + 1)p_{ij} + \dfrac{1}{2}(n - 1) p^{(2)}_{ij} & \text{if} \ n \ \text{is odd.} \end{cases}$$

from example 2?

  1. My understanding is that $\pi^*_{ij} = \dfrac{1}{2} (p_{ij} + p^{(2)}_{ij}) = \dfrac{1}{2}(0.1, 1, 0.9)$ is for the first (even) case (after division by $n$ and then taking the limit), but what happened to the second (odd) case?

I would greatly appreciate it if people would please take the time to clarify these two points.


EDIT:

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.

$\endgroup$
  • $\begingroup$ This is a really neat little example. Could you post a definition for $m_{ij}$ and $n$? $\endgroup$ – eric_kernfeld Mar 19 at 14:45
  • $\begingroup$ @eric_kernfeld See my edit. For more, see this related question: stats.stackexchange.com/q/454380/163242 $\endgroup$ – The Pointer Mar 19 at 15:00
  • $\begingroup$ @eric_kernfeld So, any chance you have an answer to confusion here? $\endgroup$ – The Pointer Mar 19 at 15:00
0
+50
$\begingroup$

Your second question is easier. In the limit, $\frac{n\pm 1}{n} \rightarrow 1$, so $$\frac{\delta_{ij}}{n} + \dfrac{1}{2} \frac{(n + 1)p_{ij}}{n} + \dfrac{1}{2}\frac{(n - 1) p^{(2)}_{ij}}{n}$$ goes to $\frac{1}{2}p_{ij} + \frac{1}{2}p^{(2)}_{ij}$.

For the first question: every time you go through an odd-numbered state, you increment by $p_{ij}$. This is because of theorem 3 combined with $P^n = P$ for odd $n$. Every time you go through an even-numbered state, you increment by $p^2_{ij}$. This is because of theorem 3 combined with $P^n = P^2$ for even $n$. If you write out the first few cases, you will see that's all these formulas do. For example, for $n = 5$, it's

$$\delta_{ij} + 3p_{ij} + 2p^{(2)}_{ij}.$$ The $3$ accounts for $n = 1, 3, 5$ and the $2$ for $n = 2, 4$. The delta accounts for $n = 0$.

The intuitive explanation here is that, in terms of little cars traversing the state space, there is a continuous morning and evening rush hour between the suburbs (states $1$ and $3$) and the city (state $2$). Thus, there is no equilibrium reached at any time. But when you average over many time points, the pothole distribution does converge.

| cite | improve this answer | |
$\endgroup$

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.