Transition matrix
Section of Discrete-time Markov chains, part of Stochastic processes
Transition matrix
| Type | Section |
| Taught in | Discrete-time Markov chains |
| Part | Stochastic processes |
| Questions using it | 4 |
Definition 1 (Discrete-time Markov chain) A process X_0,X_1,\ldots on a finite or countable state space S is a discrete-time Markov chain when
\mathbb{P}(X_{n+1}=j\mid X_n=i,X_{n-1},\ldots,X_0)=\mathbb{P}(X_{n+1}=j\mid X_n=i)=p_{ij}
for every n and every choice of states. The chain is time-homogeneous when p_{ij} does not depend on n. The transition matrix P=(p_{ij}) has non-negative entries, and every row sums to 1.
The finite-state case of this definition is the one on Markov chains. Countable S is included here so that a branching process and an unbounded walk fit the same sentence.
If the row vector \mu_0 is the law of X_0, then \mu_n=\mu_0 P^n. The n-step probability is p_{ij}^{(n)}=(P^n)_{ij}. Conditioning on the state at time m splits a trip of length m+n into a trip of length m and a trip of length n:
p_{ij}^{(m+n)}=\sum_{k\in S} p_{ik}^{(m)} p_{kj}^{(n)}.
These are the Chapman–Kolmogorov equations. Matrix multiplication is the sum over every possible intermediate state.
Example 1 (Rain after two days) A two-state weather chain has states sunny and rainy, in that order, and
P=\begin{pmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{pmatrix}.
Question. Starting from sun, find the probability of rain two days later. Also find the probability of sun two days after rain.
Solution. The sunny-to-rainy entry of P^2 sums the two routes through the intermediate day:
(P^2)_{12}=0.8\cdot 0.2+0.2\cdot 0.7=0.30.
The rainy-to-sunny entry is
(P^2)_{21}=0.3\cdot 0.8+0.7\cdot 0.3=0.45.
The two numbers differ. A row-stochastic matrix need not be symmetric, and it need not be column-stochastic. Rows are the current state and columns are the next state. That orientation is the one used with row vectors \mu_n=\mu_0 P^n.
A diagram makes impossible moves visible. The chain
P=\begin{pmatrix} 0.7 & 0.3 & 0 \\ 0.2 & 0.5 & 0.3 \\ 0 & 0.4 & 0.6 \end{pmatrix}
moves only between neighbours, or stays. The one-step probability from state 1 to state 3 is 0. The two-step probability is (P^2)_{13}=0.3\cdot 0.3=0.09, through state 2. Reachability is a property of the powers of P, not only of the positive entries of P itself.
Used in
- Taught in Discrete-time Markov chains
- Also used in Markov chains · Classes, recurrence, and reversibility · Continuous-time Markov chains · Markov chains, Gibbs sampling, and Metropolis–Hastings
- Questions that use it (4) — Two steps of a three-state chain · The limit of the three-state chain · A doubly stochastic matrix · One closed class (answer)
- All 3 questions on Discrete-time Markov chains
See also
Detailed balance · Discrete-time Markov chain · Doubly stochastic matrix · Finite-state Markov chain · Limiting distribution · Stationary distribution · Hitting probabilities · Spectral view for two states