Markov property

Given current state, the past doesn't matter.

$$\begin{aligned} p_{ij} &= {\bf P}(X_{n+1} = j\,|\, X_n = i) \\ &= {\bf P}(X_{n+1} = j\,|\, X_n = i, X_{n-1}, \cdots, X_0) \\ \end{aligned}$$

N-step transition

$$\begin{aligned} {\bf P} (X_n = j\, |\, X_0 = i) = r_{ij}(n) &= \sum_{k=1}^m r_{ik}(n-1)\cdot p_{kj} & \text{backward recursion} \\ &= \sum_{k=1}^m p_{ik}\cdot r_{kj}(n-1) & \text{forward recursion} \\ \end{aligned}$$

Steady state convergence

Two conditions must be satisfied:

1. recurrent states are all in a single class; and
2. single recurrent class is not periodic

Starting from any initial conditions, the two copies will eventually meet in a given state at a given time with probability 1.

$$\begin{aligned} r_{ij}(n) &= \sum_{k=1}^m r_{ik}(n-1)\cdot p_{kj} \\ \lim_{n \to \infty} r_{ij}(n) &=\pi_j = \sum_k \pi_k \cdot p_{kj} \qquad \text{for }j = 1,\cdots,m & \text{balance equations} \\ \end{aligned}$$

which is $m$ equations with $m$ unknowns, but singular. A unique solution exists if:

$$\begin{aligned} \sum_{j=1}^m \pi_j &= 1 & \text{normalization equation} \\ \end{aligned}$$

Birth-death process

The number of upward transitions through a partitioning line cannot be very different from the number of downward transitions.

$$\begin{aligned} \pi_i p_i &= \pi_{i+1} q_{i+1} & p_i: \text{ frequency of upward transition at state }i \\ \therefore \pi_{i+1} &= \pi_i \frac{p_i}{q_{i+1}} & i = 0, 1, \cdots \\ \end{aligned}$$

In other words, if we knew $\pi_0$, we can compute $\pi_k$ for $k = 1, \cdots$. But

$$\begin{aligned} \sum \pi_j &= 1 \\ \therefore \pi_0 + \pi_0 \frac{p_0}{q_1} + \pi_0 \frac{p_0}{q_1}\frac{p_1}{q_2} + \cdots &= 1 & q_i: \text{ frequency of downward transition at state }i \\ \end{aligned}$$

Source: MITx 6.041x, Lecture 24-26.