3.6 Limiting Probabilities
Definition 3.6.1. For a recurrent state \(i\) the first-return probabilities \(f_{ii}^{(n)}\) sum to \(1\), and the mean recurrence time is \(\mu _i = \sum _nnf_{ii}^{(n)}\). State \(i\) is positive recurrent if \(\mu _i<\infty \) and null recurrent if \(\mu _i = \infty \).
In a finite chain every recurrent state is positive recurrent. The symmetric random walk on the integers is null recurrent: it is sure to return, but the expected time to do so is infinite.
Definition 3.6.2. The period of state \(i\) is \(d(i) = \gcd \{n\geq 1 : P_{ii}^{(n)}>0\}\). The state is aperiodic if \(d(i) = 1\). A positive recurrent aperiodic state is ergodic.
Period, like recurrence, is a class property. For example, the chain \[\begin {pmatrix}0 & 0 & \frac 12 & \frac 12\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\end {pmatrix}\] is irreducible, and every return to state \(0\) goes \(0\to 2\to 1\to 0\) or \(0\to 3\to 1\to 0\), so it takes a multiple of \(3\) steps: every state has period \(3\).
Theorem 3.6.3. For an irreducible ergodic chain, \(\pi _j = \lim _{n\to \infty }P_{ij}^{(n)}\) exists and does not depend on \(i\). The limits are the unique solution of \[\pi _j = \sum _i\pi _iP_{ij}\quad \text {for all } j,\qquad \sum _j\pi _j = 1,\] that is, \(\pi = \pi P\) with \(\pi \) a probability vector. Moreover \(\pi _j = \frac {1}{\mu _j}\), the reciprocal of the mean recurrence time.
The equations \(\pi = \pi P\) say that if \(X_n\) has distribution \(\pi \) then so does \(X_{n + 1}\), so \(\pi \) is also called the stationary or equilibrium distribution. Since \(p^{(n)} = p^{(0)}P^n\), the distribution of \(X_n\) tends to \(\pi \) whatever the initial distribution, and \(\pi _j\) is also the long-run proportion of time the chain spends in state \(j\).
Example 3.6.4. A taxi works in three adjoining towns \(A\), \(B\) and \(C\), and its location from one hour to the next is a Markov chain with transition matrix \[P = \bordermatrix {~ & A & B & C\cr A & 0.4 & 0.1 & 0.5\cr B & 0.2 & 0.2 & 0.6\cr C & 0.3 & 0.4 & 0.3\cr } .\] Find the long-run proportion of time it spends in each town, and see how quickly the distribution of its position settles down from \(p^{(0)} = (0.3, 0.4, 0.3)\).
Solution. The chain is finite, irreducible and aperiodic (\(P_{AA}>0\)), so theorem 3.6.3 applies. The equations \(\pi = \pi P\) are \[\pi _A = 0.4\pi _A + 0.2\pi _B + 0.3\pi _C,\qquad \pi _B = 0.1\pi _A + 0.2\pi _B + 0.4\pi _C,\] with \(\pi _A + \pi _B + \pi _C = 1\) (the third equation of \(\pi = \pi P\) is redundant). Solving, \[\pi = \left (\frac {32}{105}, \frac {27}{105}, \frac {46}{105}\right ) = (0.3048, 0.2571, 0.4381).\] The convergence is fast: \[p^{(1)} = (0.29, 0.23, 0.48),\qquad p^{(2)} = (0.306, 0.267, 0.427),\qquad p^{(4)} = (0.3049, 0.2579, 0.4372),\] and every row of \(P^8\) already equals \(\pi \) to three decimal places. In the long run the taxi is in town \(C\) about \(44\%\) of the time, and the mean time between visits to \(A\) is \(\frac {105}{32} = 3.3\) hours.
Example 3.6.5. A chain on \(\{0, 1, 2, 3, 4\}\) has \(P_{04} = 1\), and from state \(i>0\) it moves to each of \(0, 1, \dots , i - 1\) with probability \(\frac 1i\). Find its limiting distribution.
Solution. \[P = \bordermatrix {~ & 0 & 1 & 2 & 3 & 4\cr 0 & 0 & 0 & 0 & 0 & 1\cr 1 & 1 & 0 & 0 & 0 & 0\cr 2 & \frac 12 & \frac 12 & 0 & 0 & 0\cr 3 & \frac 13 & \frac 13 & \frac 13 & 0 & 0\cr 4 & \frac 14 & \frac 14 & \frac 14 & \frac 14 & 0\cr } .\] The chain is irreducible. Returns to \(0\) are possible in \(2\) steps (\(0\to 4\to 0\)) and in \(3\) steps (\(0\to 4\to 1\to 0\)), so the period is \(\gcd (2, 3) = 1\) and the chain is ergodic. The equations \(\pi = \pi P\) read \[\pi _4 = \pi _0,\quad \pi _3 = \tfrac 14\pi _4,\quad \pi _2 = \tfrac 13\pi _3 + \tfrac 14\pi _4,\quad \pi _1 = \tfrac 12\pi _2 + \tfrac 13\pi _3 + \tfrac 14\pi _4 .\] Working upwards, \(\pi _4 = \pi _0\), \(\pi _3 = \frac 14\pi _0\), \(\pi _2 = \frac {1}{12}\pi _0 + \frac 14\pi _0 = \frac 13\pi _0\) and \(\pi _1 = \frac 16\pi _0 + \frac {1}{12}\pi _0 + \frac 14\pi _0 = \frac 12\pi _0\). The total is \(\pi _0\left (1 + \frac 12 + \frac 13 + \frac 14 + 1\right ) = \frac {37}{12}\pi _0 = 1\), so \[\pi = \left (\frac {12}{37}, \frac {6}{37}, \frac {4}{37}, \frac {3}{37}, \frac {12}{37}\right ).\] In the long run the chain is in state \(0\) about \(32\%\) of the time, whatever its starting state.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.