Discrete-time Markov chains
A discrete-time Markov chain (DTMC) is a stochastic process that moves between states at fixed time steps and satisfies the Markov property.
Why “discrete time”?
Time is considered at separate steps
\[n=0,1,2,3,\ldots\]rather than allowing events to occur at arbitrary times. For example, we might update an epidemic once per day:
\[t_0,\ t_1,\ t_2,\ldots\]with a fixed time interval \(\Delta t\) between updates.
Step 1: define the state
Let \(X_n\) denote the state of the system at step \(n\).
For a simple SIS epidemic, we can choose
\[X_n=I_n,\]where \(I_n\) is the number of infectious individuals at step \(n\).
If the population size is \(N\), the possible states are
\[\mathcal S=\{0,1,2,\ldots,N\}.\]State \(i\) simply means that there are \(i\) infectious individuals at that step.
Step 2: identify the possible next states
Suppose the current state is \(i\). In a simple one-event-per-step SIS approximation, three next states are possible:
| Event during the step | Next state |
|---|---|
| one infection | \(i+1\) |
| one recovery | \(i-1\) |
| no change | \(i\) |
The DTMC therefore does not say exactly which event will happen. It gives a probability to each possibility.
Step 3: assign transition probabilities
The probability of moving from current state \(i\) to next state \(j\) is written
\[\boxed{p_{ij}=P(X_{n+1}=j\mid X_n=i)}.\]| Symbol | Meaning |
|---|---|
| \(i\) | current state |
| \(j\) | next state |
| \(p_{ij}\) | probability of moving from \(i\) to \(j\) in one time step |
For every current state \(i\), the probabilities of all possible next states must add to 1.
A simple transition diagram
For an interior state \(i\), the three possible one-step moves can be shown visually:
The self-loop represents staying in the same state during that time step.
Step 4: connect biological rates to step probabilities
Suppose the SIS infection and recovery rates in state \(i\) are
\[b(i)=\beta\frac{(N-i)i}{N},\qquad d(i)=\gamma i.\]If the time step \(\Delta t\) is sufficiently small, a common approximation is
\[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.\]The three probabilities add approximately to 1.
A worked SIS example
Suppose
\[N=100,\qquad i=10,\qquad \beta=0.30,\qquad \gamma=0.10,\qquad \Delta t=0.1\text{ day}.\]The infection rate is
\[b(10)=0.30\frac{(100-10)(10)}{100}=2.7\text{ day}^{-1}.\]The recovery rate is
\[d(10)=0.10(10)=1.0\text{ day}^{-1}.\]Therefore
\[p_{10,11}\approx2.7(0.1)=0.27,\]\[p_{10,9}\approx1.0(0.1)=0.10,\]\[p_{10,10}\approx1-(2.7+1.0)(0.1)=0.63.\]So, from state 10, the next step has a 27% chance of moving to 11, a 10% chance of moving to 9, and a 63% chance of remaining at 10.
Step 5: arrange all probabilities into a transition matrix
The transition matrix \(P\) contains every one-step transition probability.
For a three-state example with states 0, 1 and 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}\) |
Each row corresponds to a current state. Each column corresponds to a possible next state. Therefore every row sums to 1.
A numerical transition matrix
Consider
\[P=\begin{pmatrix}1&0&0\\0.2&0.5&0.3\\0&0.4&0.6\end{pmatrix}.\]Read the second row as follows:
| From state 1 | Probability |
|---|---|
| move to 0 | 0.2 |
| stay at 1 | 0.5 |
| move to 2 | 0.3 |
The row sum is
\[0.2+0.5+0.3=1.\]The first row \((1,0,0)\) means that state 0 is absorbing: once the chain enters state 0, it remains there.
Step 6: distinguish one trajectory from the probability distribution
Suppose the chain is currently in state 1. The second row gives the probabilities 0.2, 0.5 and 0.3.
To generate one trajectory, we draw one random number \(U\) from the uniform distribution on \([0,1]\) and divide the interval according to these probabilities:
| Random number \(U\) | Next state |
|---|---|
| \(0\le U<0.2\) | 0 |
| \(0.2\le U<0.7\) | 1 |
| \(0.7\le U\le1\) | 2 |
Probability vector: where might the chain be?
Instead of following one random trajectory, we can describe the probability of being in every state.
With row-vector convention, write
\[\boldsymbol\pi_n=(\pi_0(n),\pi_1(n),\ldots,\pi_N(n)).\]Here \(\pi_i(n)=P(X_n=i)\), and
\[\sum_i\pi_i(n)=1.\]If we know with certainty that the process starts in state 1, then for a three-state chain
\[\boldsymbol\pi_0=(0,1,0).\]Step 7: propagate the distribution
With the row-vector convention used here,
\[\boxed{\boldsymbol\pi_{n+1}=\boldsymbol\pi_nP}.\]Using
\[\boldsymbol\pi_0=(0,1,0)\]and the numerical matrix above,
\[\boldsymbol\pi_1=(0,1,0)P=(0.2,0.5,0.3).\]This means that after one step,
| State | Probability |
|---|---|
| 0 | 0.2 |
| 1 | 0.5 |
| 2 | 0.3 |
No random number was needed for this calculation because we were propagating the entire probability distribution, not selecting one realised state.
One trajectory and the distribution answer different questions
| One simulated trajectory | Probability distribution |
|---|---|
| shows one possible sequence of states | shows probabilities across all states |
| uses random draws | uses matrix propagation |
| can differ each simulation | is fixed once the model and initial distribution are fixed |
| useful for sample-path behaviour | useful for exact state probabilities |
Multi-step transition probabilities
One application of matrix multiplication is to obtain transitions over several steps. For a time-homogeneous DTMC,
\[P^2\]contains two-step transition probabilities, and more generally
\[P^n\]contains \(n\)-step transition probabilities.
Therefore
\[\boldsymbol\pi_n=\boldsymbol\pi_0P^n.\]Time-homogeneous versus time-dependent DTMCs
If the same transition matrix \(P\) is used at every step, the chain is called time-homogeneous.
If interventions, seasonality or other effects change the transition probabilities through time, we may instead use matrices
\[P_0,P_1,P_2,\ldots\]with
\[\boldsymbol\pi_{n+1}=\boldsymbol\pi_nP_n.\]The process can still be Markovian because the next-step probabilities depend on the current state and the current time, rather than the full past history.
Absorbing states
An absorbing state is one that cannot be left once entered.
In many epidemic models, state 0 is absorbing:
\[P(0\to0)=1.\]Biologically, once there are no infectious individuals and there is no external introduction of infection, the epidemic cannot restart.
Boundary states need special treatment
The interior-state rules cannot always be copied directly to the boundaries.
At \(i=0\), recovery to \(-1\) is impossible. At \(i=N\), infection to \(N+1\) is impossible. The transition probabilities must respect the biologically allowed state space.
What a DTMC assumes
A DTMC makes three important modelling choices:
| Choice | Meaning |
|---|---|
| discrete time | state is updated at fixed steps |
| Markov property | next-step probabilities are determined by the present state |
| specified transition probabilities | biology is translated into probabilities of moving between states |
When is a DTMC useful?
A DTMC is useful when observations or decisions naturally occur at fixed intervals, or when a discrete-time approximation is sufficient. It can also provide an intuitive introduction to stochastic epidemic modelling before moving to continuous-time event models.
However, when biological events occur at irregular random times and the exact timing matters, a continuous-time Markov chain is often more natural.