Finite-state Markov chain

Definition taught in Markov chains, part of Probability

Finite-state Markov chain

Left: the first 60 hops of a simulated frog, starting on stone 1. From Markov chains.
Type Definition
Taught in Markov chains
Part Probability
Properties 1
Worked examples 3
Questions using it 4

Let E be a finite set of states and let X_0,X_1,X_2,\ldots take values in E. The process is a Markov chain when, for every n and every choice of states,

\mathbb{P}(X_{n+1}=j\mid X_n=i, X_{n-1}=i_{n-1},\ldots,X_0=i_0)=\mathbb{P}(X_{n+1}=j\mid X_n=i).

It is time-homogeneous when the right-hand side does not depend on n. The transition matrix P then has entries P_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i).

Properties

Limiting distribution

Main article: Limiting distribution

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.

Two steps of a three-state chain

Question page: Two steps of a 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}.

Starting from state 1, find the distribution of X_2, and the probability that X_1=2 and X_2=3.

The distribution of X_2 is the first row of P^2:

(0.5\times0.5+0.5\times0.25,\ 0.5\times0.5+0.5\times0.5,\ 0.5\times0.25)=(0.375,\ 0.5,\ 0.125).

The path 1\to2\to3 has probability P_{12}P_{23}=0.5\times0.25=0.125. It is the only two-step path from 1 to 3, which is why it equals \mathbb{P}(X_2=3).

Where a random walk can be

Question page: Where a random walk can be

A random walk on the integers starts at 0 and steps +1 with probability p and -1 with probability q=1-p. Find \mathbb{P}(X_n=k). Why is \mathbb{P}(X_n=0)=0 when n is odd?

Let K\sim\operatorname{Bin}(n,p) be the number of steps up. Then X_n=K-(n-K)=2K-n, so X_n=k exactly when K=(n+k)/2:

\mathbb{P}(X_n=k)=\binom{n}{(n+k)/2}p^{(n+k)/2}q^{(n-k)/2},

for |k|\le n with n+k even, and 0 otherwise. X_n=2K-n has the same parity as n, so an odd number of steps can never end at 0.

Figures

A simulated symmetric random walk on the integers, p=q=1/2, for 500 steps. It wanders far from zero and returns, with no tendency to settle. On the integers the symmetric walk has no limiting distribution. From Markov chains.

Used in

See also

Detailed balance · Discrete-time Markov chain · Generator · Limiting distribution

Glossary and index