Generator matrices
A generator matrix organises the transition rates of a continuous-time Markov chain (CTMC). It plays a role in continuous time similar to the role played by a transition matrix in discrete time, but its entries are rates rather than one-step probabilities.
Why do we need a generator?
In a DTMC, time advances in fixed steps, so it is natural to specify the probability of each transition during one step.
In a CTMC, events can occur at any time. There is no fixed next time step. We therefore describe each possible transition by an instantaneous rate.
The generator matrix
\[\boxed{Q=(q_{ij})}\]collects all these rates into one object.
What does an off-diagonal entry mean?
For two different states \(i\ne j\),
\[\boxed{q_{ij}=\text{rate of transition from state }i\text{ to state }j}.\]Therefore
\[q_{ij}\ge0\qquad(i\ne j).\]If a transition is impossible directly, its rate is zero.
A simple three-state example
Suppose the possible transitions are
\[0\longrightarrow1\text{ at rate }2,\]\[1\longrightarrow0\text{ at rate }1,\qquad1\longrightarrow2\text{ at rate }3,\]\[2\longrightarrow1\text{ at rate }4.\]The off-diagonal entries can therefore be placed immediately:
| Current \ Next | 0 | 1 | 2 |
|---|---|---|---|
| 0 | diagonal | 2 | 0 |
| 1 | 1 | diagonal | 3 |
| 2 | 0 | 4 | diagonal |
What goes on the diagonal?
The diagonal entry is not a transition rate from a state to itself. It is defined as the negative of the total rate of leaving that state:
\[\boxed{q_{ii}=-\sum_{j\ne i}q_{ij}}.\]For state 1, the process can leave at rate 1 toward state 0 or at rate 3 toward state 2. The total leaving rate is
\[1+3=4.\]Therefore
\[q_{11}=-4.\]Applying the same rule to every state gives
\[\boxed{Q=\begin{pmatrix}-2&2&0\\1&-4&3\\0&4&-4\end{pmatrix}}.\]Why are the diagonal entries negative?
This often looks strange at first because probabilities cannot be negative. But the generator does not contain probabilities.
The positive off-diagonal entries describe probability flowing into other states. The negative diagonal entry represents the corresponding rate at which probability leaves the current state.
Why does every row sum to zero?
Because
\[q_{ii}=-\sum_{j\ne i}q_{ij},\]we have
\[\boxed{\sum_jq_{ij}=0}.\]For row 1 in the example,
\[1-4+3=0.\]This zero-sum structure is closely related to conservation of total probability.
From rates to short-time probabilities
Suppose the CTMC is currently in state \(i\). During a sufficiently short interval \(\Delta t\),
\[\boxed{P(i\to j)\approx q_{ij}\Delta t\qquad(i\ne j)}.\]The probability of remaining in state \(i\) is approximately
\[P(i\to i)\approx1+q_{ii}\Delta t.\]Because \(q_{ii}\) is negative, this is
\[P(i\to i)\approx1-\left(\sum_{j\ne i}q_{ij}\right)\Delta t.\]So the generator contains exactly the rates needed to construct the short-time transition probabilities.
A numerical short-time example
For state 1 in our example,
\[q_{10}=1,\qquad q_{12}=3,\qquad q_{11}=-4.\]Take \(\Delta t=0.01\). Then approximately
\[P(1\to0)=1(0.01)=0.01,\]\[P(1\to2)=3(0.01)=0.03,\]\[P(1\to1)=1-4(0.01)=0.96.\]These add to 1:
\[0.01+0.03+0.96=1.\]The compact matrix form
For a small time \(h\), the transition-probability matrix satisfies
\[\boxed{P(h)=I+hQ+o(h)}.\]Here \(I\) is the identity matrix and \(o(h)\) represents terms that become negligible compared with \(h\) as \(h\to0\).
Ignoring these smaller terms for intuition gives
\[P(h)\approx I+hQ.\]The identity matrix supplies the initial “stay where you are” probability 1, while \(hQ\) adjusts those probabilities according to the continuous-time transition rates.
Why is \(Q\) called the generator?
The generator describes how the transition-probability matrix begins to change at time zero:
\[\boxed{Q=\lim_{h\to0}\frac{P(h)-I}{h}}.\]Equivalently,
\[Q=P'(0).\]So \(Q\) gives the instantaneous rate of change of the transition probabilities at the starting moment.
From the generator to transition probabilities at time \(t\)
For a finite time-homogeneous CTMC,
\[\boxed{P(t)=e^{tQ}}.\]The matrix exponential is defined by the series
\[e^{tQ}=I+tQ+\frac{t^2Q^2}{2!}+\frac{t^3Q^3}{3!}+\cdots.\]For very small \(t\), the higher powers of \(t\) are much smaller, giving
\[e^{tQ}\approx I+tQ,\]which agrees with the short-time formula above.
Generator matrix versus transition matrix
| Transition matrix \(P\) | Generator matrix \(Q\) |
|---|---|
| contains probabilities | contains instantaneous rates off the diagonal |
| naturally used for DTMCs | naturally used for CTMCs |
| off-diagonal entries lie between 0 and 1 | off-diagonal entries can exceed 1 because they are rates |
| rows sum to 1 in this convention | rows sum to 0 |
| \(P^n\) gives \(n\)-step probabilities | \(e^{tQ}\) gives transition probabilities after continuous time \(t\) |
The generator also determines waiting times
If the process is currently in state \(i\), the total rate of leaving that state is
\[a(i)=\sum_{j\ne i}q_{ij}.\]Because
\[q_{ii}=-a(i),\]we can also write
\[\boxed{a(i)=-q_{ii}}.\]The waiting time until the next jump is therefore
\[\boxed{T\sim\operatorname{Exp}(-q_{ii})}.\]Its mean is
\[E[T]=\frac{1}{-q_{ii}}.\]The generator also determines which jump occurs
Once a jump occurs from state \(i\), the probability that it goes specifically to state \(j\) is
\[\boxed{P(i\to j\mid\text{a jump occurs})=\frac{q_{ij}}{-q_{ii}}},\qquad j\ne i.\]For state 1 in our example, the total leaving rate is 4. Therefore
\[P(1\to0\mid\text{jump})=\frac14,\qquad P(1\to2\mid\text{jump})=\frac34.\]Thus one row of \(Q\) determines both when the process leaves and where it goes.
Birth–death generator
For a birth–death process, state \(i\) can move only to its neighbours:
\[i\to i+1\text{ at rate }b(i),\qquad i\to i-1\text{ at rate }d(i).\]Therefore the non-zero entries of row \(i\) are
\[\boxed{q_{i,i+1}=b(i)},\]\[\boxed{q_{i,i-1}=d(i)},\]\[\boxed{q_{ii}=-[b(i)+d(i)]}.\]All other entries in that row are zero.
SIS epidemic generator
Let state \(i\) be the number of infectious individuals in an SIS epidemic with total population \(N\). Use
\[b(i)=\beta\frac{(N-i)i}{N},\qquad d(i)=\gamma i.\]Then
\[q_{i,i+1}=\beta\frac{(N-i)i}{N},\]\[q_{i,i-1}=\gamma i,\]\[q_{ii}=-\left[\beta\frac{(N-i)i}{N}+\gamma i\right].\]This single row translates the biological mechanisms of infection and recovery into the CTMC generator.
A small SIS generator written out
Suppose the infectious count can take states \(0,1,2,3\). Write
\[b_i=b(i),\qquad d_i=d(i).\]If state 0 is absorbing, the generator has the structure
\[Q=\begin{pmatrix}0&0&0&0\\d_1&-(b_1+d_1)&b_1&0\\0&d_2&-(b_2+d_2)&b_2\\0&0&d_3&-d_3\end{pmatrix}.\]The last state cannot move upward in this finite SIS example, so its only possible event is recovery.
How to build a generator from a biological model
This procedure is often more useful than memorising a particular matrix.
Absorbing states
If state \(i\) is absorbing, there are no transitions out of it. Therefore
\[q_{ij}=0\quad\text{for every }j.\]The entire row is zero, including
\[q_{ii}=0.\]For an epidemic without imported infection, \(I=0\) is often absorbing because no new infection can occur once there are no infectious individuals.
What does the generator tell us biologically?
The generator is more than a matrix of numbers. Each row describes the local stochastic behaviour of the biological system in one state.
| Part of row \(i\) | Biological interpretation |
|---|---|
| \(q_{ij}>0\) | a biological event can move the system from \(i\) to \(j\) |
| \(-q_{ii}\) | total rate at which any event occurs in state \(i\) |
| \(1/(-q_{ii})\) | mean time spent in state \(i\) before the next jump |
| \(q_{ij}/(-q_{ii})\) | probability that the next jump is specifically to \(j\) |
Probability distributions evolve using \(Q\)
Let
\[\boldsymbol\pi(t)=(P(X(t)=0),P(X(t)=1),\ldots)\]be the row probability vector. Its evolution satisfies
\[\boxed{\frac{d\boldsymbol\pi(t)}{dt}=\boldsymbol\pi(t)Q}.\]This is the Kolmogorov forward equation. It shows that the generator determines how probability flows between states through time.
The next page develops these Kolmogorov equations carefully and explains where they come from.