Markov property
Section of Markov chains, part of Probability
Markov property
| Type | Section |
| Taught in | Markov chains |
| Part | Probability |
| Questions using it | 1 |
Definition 1 (Finite-state Markov chain) 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).
Each row of P is a probability distribution: the entries are non-negative and sum to 1. If the row vector \boldsymbol\pi^{(0)} is the distribution of X_0, the distribution of X_n is \boldsymbol\pi^{(0)} P^n. The Chapman–Kolmogorov equations are the matrix product P^{m+n}=P^m P^n: the way to be at j after m+n steps is to be somewhere after m steps and then travel for n more.
A path of length n has probability equal to the product of the n transition probabilities along it, times the probability of the starting state. That product is the Markov property written out by the chain rule. A chain is conveniently drawn as a transition graph: one node per state, and an arrow from i to j, labelled P_{ij}, whenever P_{ij}>0.
Example 1 (Six stepping stones) 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 random walk on the integers, moving one step right with probability p and one step left with probability q=1-p, is the same definition on a countably infinite state space. The one-step matrix is no longer a finite array, but the n-step probabilities are binomial: after n steps the displacement is 2K-n if K\sim\operatorname{Bin}(n,p) is the number of steps to the right.
States i and j communicate when each can be reached from the other with positive probability in some number of steps. A chain on a finite set is irreducible when every pair communicates. A state is periodic with period d>1 when returns are possible only at multiples of d; otherwise it is aperiodic. In an irreducible chain every state has the same period.
Used in
- Taught in Markov chains
- Also used in Stochastic processes · Discrete-time Markov chains · Graphical models
- Questions that use it (1) — C12
- All 6 questions on Markov chains
See also
Markov chain · Finite-state Markov chain · Discrete-time Markov chain · Markov random field · Limiting distribution · Simulating a Markov chain · Chapman–Kolmogorov equations