The Generator Matrix (Q-Matrix)

For continuous-time Markov chains, the generator matrix (also called the Q-matrix or infinitesimal generator) plays the role analogous to the transition matrix in discrete time. It encodes the instantaneous transition rates between states and governs the evolution of the process via the Kolmogorov forward and backward equations.

Definition

Definition2.1Continuous-time Markov chain

A stochastic process $(X_t)_{t \geq 0}$ on a countable state space $S$ is a continuous-time Markov chain (CTMC) if for all $s, t \geq 0$ and states $i, j \in S$ :

$\mathbb{P}(X_{t+s} = j \mid X_s = i, X_u \text{ for } u < s) = \mathbb{P}(X_{t+s} = j \mid X_s = i) = p_{ij}(t),$

where $p_{ij}(t) = \mathbb{P}(X_t = j \mid X_0 = i)$ is the transition probability over time $t$ .

Definition2.2Generator matrix

The generator matrix $Q = (q_{ij})_{i,j \in S}$ of a CTMC is defined by

$q_{ij} = \lim_{h \to 0^+} \frac{p_{ij}(h) - \delta_{ij}}{h}, \quad i, j \in S,$

where $\delta_{ij} = 1$ if $i = j$ and $0$ otherwise. Equivalently:

For $i \neq j$ : $q_{ij} \geq 0$ is the transition rate from $i$ to $j$ .
For $i = j$ : $q_{ii} = -\sum_{j \neq i} q_{ij}$ (so row sums are zero).

The matrix $Q$ satisfies $q_{ij} \geq 0$ for $i \neq j$ and $\sum_{j \in S} q_{ij} = 0$ for all $i$ .

The off-diagonal entries $q_{ij}$ ( $i \neq j$ ) are the rates at which the chain jumps from $i$ to $j$ . The diagonal entry $q_{ii} = -\lambda_i$ , where $\lambda_i = \sum_{j \neq i} q_{ij}$ is the total exit rate from state $i$ .

Kolmogorov equations

Theorem2.1Kolmogorov forward equation

The transition probabilities $P(t) = (p_{ij}(t))$ satisfy the forward equation:

$\frac{d}{dt} P(t) = P(t) Q.$

In component form, for each $i, j \in S$ :

$\frac{d}{dt} p_{ij}(t) = \sum_{k \in S} p_{ik}(t) q_{kj}.$

Theorem2.2Kolmogorov backward equation

The transition probabilities satisfy the backward equation:

$\frac{d}{dt} P(t) = Q P(t).$

In component form:

$\frac{d}{dt} p_{ij}(t) = \sum_{k \in S} q_{ik} p_{kj}(t).$

The forward equation describes how probabilities evolve "looking forward from the present," while the backward equation considers "looking backward from the future." For finite state spaces, both equations are equivalent and have the formal solution

$P(t) = e^{tQ} = \sum_{n=0}^\infty \frac{(tQ)^n}{n!}.$

ExampleTwo-state chain

Consider a two-state chain with $S = \{0, 1\}$ and generator

$Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}.$

The chain jumps from 0 to 1 at rate $\alpha$ and from 1 to 0 at rate $\beta$ . Solving $P'(t) = QP(t)$ with $P(0) = I$ gives

$P(t) = \frac{1}{\alpha+\beta} \begin{pmatrix} \beta & \alpha \\ \beta & \alpha \end{pmatrix} + \frac{e^{-(\alpha+\beta)t}}{\alpha+\beta} \begin{pmatrix} \alpha & -\alpha \\ -\beta & \beta \end{pmatrix}.$

As $t \to \infty$ , $P(t)$ converges to the matrix with rows $(\beta/(\alpha+\beta), \alpha/(\alpha+\beta))$ , the stationary distribution.

Jump chain and holding times

A CTMC can be constructed from two ingredients:

Jump chain: A discrete-time Markov chain $Y_n$ with transition matrix $R = (r_{ij})$ , where

$r_{ij} = \begin{cases} q_{ij}/\lambda_i & \text{if } i \neq j, \\ 0 & \text{if } i = j. \end{cases}$

Holding times: In state $i$ , the chain stays for a random time $\tau_i \sim \text{Exp}(\lambda_i)$ before jumping to a new state chosen according to the jump chain.

Definition2.3Standard construction

Starting from $X_0 = i_0$ :

Hold in state $i_0$ for time $\tau_0 \sim \text{Exp}(\lambda_{i_0})$ .
Jump to state $i_1$ with probability $r_{i_0 i_1}$ .
Hold in state $i_1$ for time $\tau_1 \sim \text{Exp}(\lambda_{i_1})$ .
Continue indefinitely.

Then $X_t$ is the state at time $t$ , constructed from the sequence of jumps and holding times.

ExampleBirth-death process

A continuous-time birth-death process on $S = \{0, 1, 2, \ldots\}$ has rates:

$q_{i,i+1} = \lambda_i, \quad q_{i,i-1} = \mu_i, \quad q_{ij} = 0 \text{ if } |i-j| > 1.$

This models a population that increases (birth) at rate $\lambda_i$ and decreases (death) at rate $\mu_i$ when the population is $i$ .

For the $M/M/1$ queue: $\lambda_i = \lambda$ (constant arrival rate), $\mu_i = \mu$ for $i \geq 1$ , $\mu_0 = 0$ .

Stationary distribution

Definition2.4Stationary distribution

A probability distribution $\pi$ on $S$ is stationary for a CTMC with generator $Q$ if

$\pi Q = 0,$

i.e., $\sum_{i \in S} \pi_i q_{ij} = 0$ for all $j \in S$ .

If $X_0 \sim \pi$ , then $X_t \sim \pi$ for all $t \geq 0$ . The equation $\pi Q = 0$ is the continuous-time analogue of $\pi P = \pi$ for discrete-time chains.

ExampleStationary distribution for two-state chain

For the generator

$Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix},$

we solve $\pi Q = 0$ :

$\pi_0 (-\alpha) + \pi_1 \beta = 0, \quad \pi_0 \alpha + \pi_1 (-\beta) = 0.$

Both equations give $\pi_1 \beta = \pi_0 \alpha$ . With $\pi_0 + \pi_1 = 1$ :

$\pi_0 = \frac{\beta}{\alpha+\beta}, \quad \pi_1 = \frac{\alpha}{\alpha+\beta}.$

Detailed balance

Definition2.5Reversibility

A CTMC is reversible with respect to a distribution $\pi$ if

$\pi_i q_{ij} = \pi_j q_{ji} \quad \text{for all } i, j \in S.$

Reversibility (detailed balance) implies $\pi Q = 0$ . Many CTMCs arising in applications (e.g., queueing networks, chemical reaction networks) satisfy detailed balance.

ExampleM/M/1 queue

For the $M/M/1$ queue with arrival rate $\lambda$ and service rate $\mu$ , the stationary distribution (for $\rho = \lambda/\mu < 1$ ) is geometric: $\pi_n = (1-\rho)\rho^n$ . One can verify detailed balance:

$\pi_n \lambda = (1-\rho)\rho^n \lambda = (1-\rho)\rho^{n+1} \mu = \pi_{n+1} \mu.$

Explosion and regularity

RemarkExplosion

For countably infinite state spaces, the chain may explode: it performs infinitely many jumps in finite time. This happens if $\sum_{n=1}^\infty 1/\lambda_{i_n} < \infty$ for some sequence of states. A chain is regular (non-explosive) if a.s. it makes only finitely many jumps in any finite time interval.

For practical CTMCs (e.g., birth-death processes with bounded rates), regularity is automatic.

Summary

The generator matrix $Q$ encodes the dynamics of continuous-time Markov chains:

Off-diagonal entries: $q_{ij} \geq 0$ are transition rates ( $i \to j$ ).
Diagonal entries: $q_{ii} = -\lambda_i$ , where $\lambda_i$ is the exit rate from $i$ .
Kolmogorov equations: $P'(t) = QP(t) = P(t)Q$ .
Stationary distribution: $\pi Q = 0$ .
Detailed balance: $\pi_i q_{ij} = \pi_j q_{ji}$ for reversible chains.

The $Q$ -matrix framework unifies the theory of continuous-time Markov chains and connects to exponential holding times and discrete-time jump chains.