Limiting distribution
Theorem taught in Markov chains, part of Probability
Limiting distribution
| Type | Theorem |
| Taught in | Markov chains |
| Part | Probability |
| Worked examples | 6 |
| Questions using it | 2 |
Suppose P is the transition matrix of an irreducible aperiodic chain on a finite set. Then there is a unique probability row vector \boldsymbol\pi with \boldsymbol\pi=\boldsymbol\pi P, and for every start i and every state j,
\lim_{n\to\infty}(P^n)_{ij}=\pi_j.
Every row of P^n converges to \boldsymbol\pi. The equations \boldsymbol\pi=\boldsymbol\pi P together with \sum_j \pi_j=1 determine \boldsymbol\pi.
Examples
Six stepping stones
Worked example from Markov chains
A frog hops between six stepping stones. From each stone it jumps to one of the stones joined to it, choosing uniformly among them, except that from stone 4 it always goes to stone 6. The transition matrix, with rows and columns in the order of the stones, is
P=\begin{pmatrix} 0&1/3&0&1/3&1/3&0\\ 1/2&0&1/2&0&0&0\\ 1/2&0&0&1/2&0&0\\ 0&0&0&0&0&1\\ 0&0&0&1/2&0&1/2\\ 0&0&1/2&0&1/2&0 \end{pmatrix}.
Question. Starting on stone 1, find the distribution after two steps, and the long-run proportion of time spent on each stone.
Solution. The distribution after two steps is the first row of P^2:
(1/6,\ 0,\ 1/6,\ 1/6,\ 0,\ 1/2).
For example, stone 6 is reached in two steps through stone 4 or stone 5, with probability \tfrac13\cdot1+\tfrac13\cdot\tfrac12=\tfrac12. Stones 2 and 5 cannot be reached from stone 1 in exactly two steps. After ten steps the probability of being back on stone 1 is 0.1049, and by n=100 every row of P^n agrees to four decimal places.
The chain is irreducible, and it is aperiodic because it can return to stone 1 in both 2 and 3 steps, which have greatest common divisor 1. Solving \boldsymbol\pi=\boldsymbol\pi P with \sum_j\pi_j=1 gives
\boldsymbol\pi=\frac1{119}(12,\ 4,\ 20,\ 25,\ 22,\ 36)=(0.101,\ 0.034,\ 0.168,\ 0.210,\ 0.185,\ 0.303).
The first equation, \pi_2=\pi_1/3, says that stone 2 is entered only from stone 1, a third of the time. In the long run the frog spends 30% of its time on stone 6 and only 3% on stone 2, whichever stone it started from.
A two-state weather chain
Worked example from Markov chains
Each day is dry or wet. A dry day is followed by a dry day with probability 0.8, and a wet day by a wet day with probability 0.6.
Question. Find the limiting distribution, and the probability that it is dry two days after a wet day.
Solution. With the states in the order dry, wet,
P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}.
The balance equation for the dry state is \pi_1=0.8\pi_1+0.4\pi_2, so 0.2\pi_1=0.4\pi_2 and \pi_1=2\pi_2. With \pi_1+\pi_2=1, \boldsymbol\pi=(2/3,1/3): in the long run two days in three are dry. Two days after a wet day, the probability of a dry day is the (wet, dry) entry of P^2,
0.4\times0.8+0.6\times0.4=0.56.
For any two-state chain with switching probabilities a (dry to wet) and b (wet to dry), the limit is (b,a)/(a+b), and P^n approaches it geometrically fast, at rate (1-a-b)^n. Here 1-a-b=0.4, so after a week the starting state has almost no influence.
The limit of the three-state chain
Question page: The limit of the three-state chain
A chain on \{1,2,3\} has transition matrix
P=\begin{pmatrix}0.5&0.5&0\\0.25&0.5&0.25\\0&0.5&0.5\end{pmatrix}.
Show that it is irreducible and aperiodic, and find its limiting distribution.
State 2 can be reached from 1 and 3 and can reach both, so every pair of states communicates and the chain is irreducible. P_{11}=0.5>0, so state 1 can return in one step and has period 1; in an irreducible chain all states then have period 1.
The balance equations are \pi_1=0.5\pi_1+0.25\pi_2 and \pi_3=0.25\pi_2+0.5\pi_3, so \pi_1=\pi_3=\pi_2/2. With \pi_1+\pi_2+\pi_3=1,
\boldsymbol\pi=(1/4,\ 1/2,\ 1/4).
Any two-state chain
Question page: Any two-state chain
A chain on two states moves from state 1 to state 2 with probability a and from state 2 to state 1 with probability b, where 0<a,b<1. Show that its limiting distribution is (b,a)/(a+b).
P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}.
The first balance equation is \pi_1=(1-a)\pi_1+b\pi_2, that is a\pi_1=b\pi_2: in the long run, the flow from 1 to 2 equals the flow back. With \pi_1+\pi_2=1, \pi_1=b/(a+b) and \pi_2=a/(a+b). Because 0<a,b<1, the chain is irreducible and P_{11}>0 makes it aperiodic, so this stationary vector is the limit.
A chain that never settles
Question page: A chain that never settles
A chain on \{1,2\} moves to the other state at every step. Find P^n for every n, and a probability vector \boldsymbol\pi with \boldsymbol\pi=\boldsymbol\pi P. Explain why P^n has no limit.
P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad P^2=I,
so P^n=I for even n and P^n=P for odd n. The vector \boldsymbol\pi=(1/2,1/2) satisfies \boldsymbol\pi P=\boldsymbol\pi. But (P^n)_{11} alternates between 1 and 0, so it has no limit. The chain is irreducible but has period 2: returns to a state happen only at even times. A stationary distribution exists; a limiting one does not.
A walk with a floor
Question page: A walk with a floor
A walk on \{0,1,2,\ldots\} steps up with probability p=0.3 and down with probability q=0.7, except that from 0 it stays at 0 instead of stepping down. Find the limiting probability that the walk is at 0, and its long-run mean position.
With r=p/q=3/7<1, the balance equations give \pi_j=(1-r)r^j, a geometric distribution on \{0,1,2,\ldots\}. So
\pi_0=1-\tfrac37=\tfrac47=0.571,
and the long-run mean position is \sum_jj\pi_j=r/(1-r)=(3/7)/(4/7)=0.75.
Figures
Used in
- Taught in Markov chains, where the derivation and examples are.
- Questions that use it (2) — The limit of the three-state chain · Any two-state chain
- All 6 questions on Markov chains