Transition matrices
A transition matrix is a compact way to store all one-step transition probabilities of a finite discrete-time Markov chain (DTMC).
Why do we need a matrix?
Suppose a model has several possible states. From each current state there may be several possible next states, each with its own probability.
Writing every probability separately quickly becomes inconvenient. A matrix organises them into one mathematical object.
If the states are
\[0,1,2,\ldots,N,\]we write
\[\boxed{P=(p_{ij})},\]where
\[\boxed{p_{ij}=P(X_{n+1}=j\mid X_n=i)}.\]What do the two indices mean?
| Symbol | Meaning |
|---|---|
| \(i\) | current state |
| \(j\) | next state |
| \(p_{ij}\) | probability of moving from state \(i\) to state \(j\) in one step |
How the matrix is arranged
For three states \(0,1,2\),
| Current \ Next | 0 | 1 | 2 |
|---|---|---|---|
| 0 | \(p_{00}\) | \(p_{01}\) | \(p_{02}\) |
| 1 | \(p_{10}\) | \(p_{11}\) | \(p_{12}\) |
| 2 | \(p_{20}\) | \(p_{21}\) | \(p_{22}\) |
The same information is written mathematically as
\[P=\begin{pmatrix}p_{00}&p_{01}&p_{02}\\p_{10}&p_{11}&p_{12}\\p_{20}&p_{21}&p_{22}\end{pmatrix}.\]Rows represent where the process is now. Columns represent where it goes next.
A concrete three-state example
Consider
\[\boxed{P=\begin{pmatrix}1&0&0\\0.2&0.5&0.3\\0&0.4&0.6\end{pmatrix}}.\]The second row is
\[(0.2,0.5,0.3).\]Therefore, if the current state is 1,
| Transition | Probability |
|---|---|
| \(1\to0\) | 0.2 |
| \(1\to1\) | 0.5 |
| \(1\to2\) | 0.3 |
So the process may move down, stay where it is, or move up.
The same information as a transition diagram
Every arrow corresponds directly to an entry in the matrix. Missing arrows have transition probability zero.
Why must every row sum to 1?
If the process is currently in state \(i\), it must be in some allowed state at the next step. The row contains all mutually exclusive possibilities.
Therefore
\[\boxed{\sum_j p_{ij}=1}.\]For state 1 in the example,
\[0.2+0.5+0.3=1.\]Every matrix entry must also satisfy
\[0\le p_{ij}\le1.\]Why can a diagonal entry be non-zero?
An entry such as \(p_{11}\) means
\[P(X_{n+1}=1\mid X_n=1).\]This is the probability that the process remains in the same state during one step.
In the example, \(p_{11}=0.5\), so there is a 50% chance of remaining in state 1.
Absorbing states
The first row of the example is
\[(1,0,0).\]This means
\[P(0\to0)=1.\]Once the chain reaches state 0, it can never leave. State 0 is therefore an absorbing state.
In an epidemic model without imported infections, state 0 may represent extinction of infection.
From a known state to a probability vector
Suppose the process starts with certainty in state 1. Its initial probability distribution is
\[\boldsymbol\pi_0=(0,1,0).\]The entries mean
\[P(X_0=0)=0,\qquad P(X_0=1)=1,\qquad P(X_0=2)=0.\]The probabilities sum to 1.
One matrix multiplication gives the next distribution
Using the row-vector convention,
\[\boxed{\boldsymbol\pi_{n+1}=\boldsymbol\pi_nP}.\]Therefore
\[\boldsymbol\pi_1=(0,1,0)\begin{pmatrix}1&0&0\\0.2&0.5&0.3\\0&0.4&0.6\end{pmatrix}.\]The result is
\[\boxed{\boldsymbol\pi_1=(0.2,0.5,0.3)}.\]This is exactly the second row of \(P\), because we started with certainty in state 1.
What does matrix multiplication mean here?
Suppose the current distribution is not concentrated in one state:
\[\boldsymbol\pi_n=(\pi_0,\pi_1,\pi_2).\]Then the probability of being in state 2 at the next step is
\[\boxed{\pi_0p_{02}+\pi_1p_{12}+\pi_2p_{22}}.\]Each term has a simple interpretation:
| Term | Meaning |
|---|---|
| \(\pi_0p_{02}\) | probability of currently being in 0 and then moving to 2 |
| \(\pi_1p_{12}\) | probability of currently being in 1 and then moving to 2 |
| \(\pi_2p_{22}\) | probability of currently being in 2 and then staying in 2 |
Adding them accounts for all possible ways of arriving at state 2. This is the probabilistic meaning of the matrix multiplication.
Two steps: why do we use \(P^2\)?
After one step,
\[\boldsymbol\pi_1=\boldsymbol\pi_0P.\]After another step,
\[\boldsymbol\pi_2=\boldsymbol\pi_1P.\]Substituting the first equation into the second gives
\[\boldsymbol\pi_2=(\boldsymbol\pi_0P)P=\boldsymbol\pi_0P^2.\]Thus \(P^2\) contains two-step transition probabilities.
What does an entry of \(P^2\) mean?
The \((i,j)\) entry of \(P^2\) is
\[(P^2)_{ij}=\sum_k p_{ik}p_{kj}.\]This says: to travel from state \(i\) to state \(j\) in two steps, the process may pass through any intermediate state \(k\).
For each possible intermediate state, we multiply the probability of the first transition by the probability of the second, then add across all possible intermediate states.
A numerical two-step calculation
What is the probability of going from state 1 to state 0 in two steps?
There are three possible intermediate states:
\[(P^2)_{10}=p_{10}p_{00}+p_{11}p_{10}+p_{12}p_{20}.\]Using the example matrix,
\[(P^2)_{10}=(0.2)(1)+(0.5)(0.2)+(0.3)(0).\]Therefore
\[\boxed{(P^2)_{10}=0.30}.\]So, starting in state 1, the probability of being in state 0 after two steps is 30%.
Many steps
Repeating the same reasoning gives
\[\boxed{\boldsymbol\pi_n=\boldsymbol\pi_0P^n}.\]The entry
\[(P^n)_{ij}\]is the probability that the chain is in state \(j\) after \(n\) steps, given that it started in state \(i\).
One trajectory is different from the probability distribution
The transition matrix gives probabilities. It does not by itself choose which state actually occurs in one simulated realisation.
| Distribution calculation | Single simulation |
|---|---|
| multiply \(\boldsymbol\pi_nP\) | draw a random number |
| keeps probabilities for all states | selects one next state |
| gives the exact model distribution | gives one random trajectory |
Repeating many simulated trajectories allows their empirical frequencies to approximate the probabilities encoded by the matrix.
How a row is used to simulate one transition
Suppose the current state is 1, so the relevant row is
\[(0.2,0.5,0.3).\]Divide the interval \([0,1]\) according to the cumulative probabilities:
| Uniform random number \(U\) | Next state |
|---|---|
| \(0\le U<0.2\) | 0 |
| \(0.2\le U<0.7\) | 1 |
| \(0.7\le U\le1\) | 2 |
If \(U=0.81\), the next state is 2. A new random number is then generated for the following step using the row corresponding to state 2.
Transition matrices in an epidemic model
Suppose the state \(i\) is the number of infectious individuals in a discrete-time SIS model. For an interior state, possible one-step transitions may be
\[i\to i-1,\qquad i\to i,\qquad i\to i+1.\]The corresponding row of the matrix therefore contains non-zero probabilities only in the columns for \(i-1\), \(i\), and \(i+1\), under the simple one-event-per-step construction.
If infection and recovery rates are \(b(i)\) and \(d(i)\), then for sufficiently small \(\Delta t\),
\[p_{i,i+1}\approx b(i)\Delta t,\]\[p_{i,i-1}\approx d(i)\Delta t,\]\[p_{i,i}\approx1-[b(i)+d(i)]\Delta t.\]This shows how biological assumptions become entries in a transition matrix.
Boundary rows must reflect biology
At a boundary, some transitions are impossible. For example, if \(i=0\) represents no infectious individuals and infection cannot be imported, then
\[p_{00}=1\]and all other entries in row 0 are zero.
Likewise, if \(N\) is the maximum possible infectious count, the model cannot assign positive probability to state \(N+1\).
Time-homogeneous and time-dependent matrices
If the same matrix is used at every step,
\[P_0=P_1=P_2=\cdots=P,\]the DTMC is time-homogeneous.
If interventions, seasonality or changing environmental conditions alter the transition probabilities, the matrix may depend on time:
\[P_0,P_1,P_2,\ldots\]and then
\[\boldsymbol\pi_{n+1}=\boldsymbol\pi_nP_n.\]In that case, simply using \(P^n\) is no longer generally correct because the transition rule changes between steps.
Row-vector versus column-vector conventions
This page uses probability distributions as row vectors, so
\[\boldsymbol\pi_{n+1}=\boldsymbol\pi_nP\]and rows of \(P\) sum to 1.
Some books instead use column probability vectors. Their matrices may be written with the opposite orientation, leading to a formula such as
\[\mathbf p_{n+1}=P\mathbf p_n.\]Transition matrix versus generator matrix
A transition matrix belongs naturally to a DTMC. A continuous-time Markov chain is instead described locally by a generator matrix.
| Transition matrix \(P\) | Generator matrix \(Q\) |
|---|---|
| contains probabilities | contains transition rates off the diagonal |
| used for discrete-time steps | used for continuous-time dynamics |
| entries are non-negative | diagonal entries are non-positive |
| rows sum to 1 in this convention | rows sum to 0 in the corresponding convention |
The next section develops generator matrices carefully.