6.2 Infinitesimal generator matrix

Definition of the Infinitesimal Generator Matrix

The infinitesimal generator matrix, denoted $Q$, encodes all the information about how a continuous-time Markov chain (CTMC) evolves. Where a discrete-time chain uses a transition probability matrix to describe jumps at fixed time steps, the generator matrix captures instantaneous rates of transition between states.

Each entry $q_{ij}$ (with $i \neq j$) represents the rate at which the process transitions from state $i$ to state $j$ over an infinitesimal time interval. More precisely, for small $\Delta t$:

$P(X(t + \Delta t) = j \mid X(t) = i) \approx q_{ij} \, \Delta t, \quad i \neq j$

The diagonal entries $q_{ii}$ are defined so that each row sums to zero, which means $q_{ii} = -\sum_{j \neq i} q_{ij}$. This makes $|q_{ii}|$ the total rate at which the process leaves state $i$.

Properties of the Infinitesimal Generator Matrix

Non-negative off-diagonal elements

Off-diagonal entries $q_{ij}$ (for $i \neq j$) are always non-negative. They represent transition rates, and a negative rate has no physical meaning. If $q_{ij} = 0$, direct transitions from $i$ to $j$ simply don't occur.

Negative diagonal elements

Each diagonal entry $q_{ii}$ is non-positive (negative or zero). Its absolute value $|q_{ii}|$ gives the total departure rate from state $i$. The holding time in state $i$ is exponentially distributed with parameter $|q_{ii}|$, so the expected time spent in state $i$ before jumping is $1/|q_{ii}|$.

A diagonal entry of zero means the state is absorbing: once the process enters, it never leaves.

Row sums equal to zero

Every row of $Q$ sums to zero:

$\sum_{j} q_{ij} = 0 \quad \text{for all } i$

This is the continuous-time analogue of rows summing to one in a discrete-time transition matrix. It enforces conservation of probability: probability flowing out of state $i$ (captured by $q_{ii}$) exactly balances the total probability flowing into other states (captured by the off-diagonal entries).

Relationship to the Transition Rate Matrix

Some texts define a separate transition rate matrix $R$ whose entries $r_{ij}$ (for $i \neq j$) are the same transition rates, but whose diagonal entries are zero (or defined differently). The generator $Q$ and $R$ share the same off-diagonal entries:

$q_{ij} = r_{ij}, \quad i \neq j$

The diagonal of $Q$ is then constructed from $R$:

$q_{ii} = -\sum_{j \neq i} r_{ij}$

So $Q$ is fully determined by the off-diagonal rates. If you're given $R$, building $Q$ just means filling in the diagonal to make each row sum to zero.

Role in Continuous-Time Markov Chains

Evolution of state probabilities

Let $\mathbf{p}(t)$ be the row vector of state probabilities at time $t$. The generator matrix governs how $\mathbf{p}(t)$ changes over time through the relationship:

$\frac{d}{dt}\mathbf{p}(t) = \mathbf{p}(t) \, Q$

This single matrix equation encodes the entire dynamics of the CTMC. It also leads to the matrix exponential solution $P(t) = e^{Qt}$, where $P(t)$ is the transition probability matrix at time $t$.

Kolmogorov forward equations

The forward equations (also called master equations) describe how transition probabilities evolve forward in time:

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

Given an initial distribution $\mathbf{p}(0)$, you solve this system to find $\mathbf{p}(t) = \mathbf{p}(0) \, P(t)$. These equations are the workhorse for computing state probabilities at any future time.

Kolmogorov backward equations

The backward equations take a different perspective, conditioning on the starting state:

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

Notice $Q$ multiplies from the left here, not the right. The backward equations are particularly useful for computing hitting times and absorption probabilities, where you want to ask: "Starting from state $i$, what's the probability of reaching state $j$ by time $t$?"

Computation of the Infinitesimal Generator Matrix

From the transition rate matrix

1. Write down all off-diagonal rates $q_{ij} = r_{ij}$ directly from the rate matrix $R$.
2. For each row $i$, sum the off-diagonal entries: $\sum_{j \neq i} q_{ij}$.
3. Set the diagonal entry: $q_{ii} = -\sum_{j \neq i} q_{ij}$.
4. Verify every row sums to zero.

From a state transition diagram

1. Label each state as a node. Each directed arrow from state $i$ to state $j$ carries a rate $q_{ij}$.
2. Read off the arrow labels to fill in the off-diagonal entries of $Q$.
3. For each state $i$, sum all outgoing arrow rates and negate to get $q_{ii}$.

Example: Suppose you have three states with arrows: $1 \xrightarrow{2} 2$, $2 \xrightarrow{3} 1$, $2 \xrightarrow{1} 3$, and $3 \xrightarrow{4} 1$. The generator matrix is:

$Q = \begin{pmatrix} -2 & 2 & 0 \\ 3 & -4 & 1 \\ 4 & 0 & -4 \end{pmatrix}$

Check: each row sums to zero.

Eigenvalues and Eigenvectors

Interpretation of eigenvalues

The eigenvalues of $Q$ reveal how quickly the chain approaches equilibrium.

• One eigenvalue is always $\lambda_1 = 0$. This corresponds to the stationary distribution.
• All other eigenvalues have non-positive real parts (for an irreducible, finite-state chain, they have strictly negative real parts).
• The eigenvalue with the smallest nonzero magnitude (closest to zero) is called the spectral gap. It controls the rate of convergence to stationarity: a larger spectral gap means faster convergence.

Since $P(t) = e^{Qt}$, each eigenvalue $\lambda_k$ contributes a term proportional to $e^{\lambda_k t}$. The zero eigenvalue gives the steady-state component, while the negative eigenvalues produce transient terms that decay exponentially.

Stationary distribution and eigenvectors

The stationary distribution $\boldsymbol{\pi}$ is the row vector satisfying:

$\boldsymbol{\pi} Q = \mathbf{0}, \quad \sum_i \pi_i = 1$

This makes $\boldsymbol{\pi}$ the left eigenvector of $Q$ corresponding to eigenvalue zero. Meanwhile, the right eigenvector for eigenvalue zero is $\mathbf{1}$ (a column vector of ones), which is just a restatement of the row-sum-equals-zero property.

For an irreducible, positive-recurrent CTMC, this stationary distribution exists, is unique, and represents the long-run fraction of time spent in each state.

Applications of the Infinitesimal Generator Matrix

Queueing systems

In an M/M/1 queue with arrival rate $\lambda$ and service rate $\mu$, the states represent the number of customers in the system. The generator matrix has $\lambda$ on the superdiagonal (arrivals) and $\mu$ on the subdiagonal (departures). Solving $\boldsymbol{\pi} Q = \mathbf{0}$ yields performance measures like average queue length and utilization $\rho = \lambda / \mu$.

Birth-death processes

Birth-death processes are CTMCs where transitions only occur between neighboring states ($i \to i+1$ or $i \to i-1$). The generator matrix has a tridiagonal structure: birth rates $\lambda_i$ on the superdiagonal, death rates $\mu_i$ on the subdiagonal, and $q_{ii} = -(\lambda_i + \mu_i)$ on the diagonal. This structure makes the stationary distribution particularly tractable, with a product-form solution.

Reliability analysis

System components can be modeled as occupying operational or failed states, with failure rates and repair rates as the transition rates. The generator matrix captures all possible failure/repair transitions. From it, you can compute the mean time to failure (MTTF), system availability (long-run fraction of time the system is operational), and the probability of being in any particular degraded state.

Numerical Example

Consider a two-state CTMC (states 0 and 1) with transition rate $\alpha$ from 0 to 1 and rate $\beta$ from 1 to 0.

Step 1: Construct $Q$:

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

Step 2: Find the stationary distribution by solving $\boldsymbol{\pi} Q = \mathbf{0}$ with $\pi_0 + \pi_1 = 1$:

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

Step 3: The eigenvalues are $\lambda_1 = 0$ and $\lambda_2 = -(\alpha + \beta)$. The transient behavior decays at rate $\alpha + \beta$, so the chain reaches stationarity faster when both rates are large.

Step 4: The transition probability matrix is:

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

As $t \to \infty$, the exponential terms vanish and each row converges to $\boldsymbol{\pi}$.

Comparison to Discrete-Time Markov Chains

Extensions and Generalizations

Time-inhomogeneous Markov chains

When transition rates change over time, the generator becomes a function $Q(t)$ with time-dependent entries $q_{ij}(t)$. The Kolmogorov equations still hold but with $Q(t)$ replacing $Q$:

$\frac{d}{dt} P(s, t) = P(s, t) \, Q(t) \quad \text{(forward)}$

The solution is no longer a simple matrix exponential; instead it involves a time-ordered exponential (or product integral). This extension is useful for modeling systems with seasonal variation, aging components, or externally driven rate changes.

Absorbing states and absorption probabilities

An absorbing state $a$ has $q_{aj} = 0$ for all $j \neq a$ (and therefore $q_{aa} = 0$). To analyze absorption, partition the state space into transient states $T$ and absorbing states $A$, and write $Q$ in block form:

$Q = \begin{pmatrix} Q_T & Q_{TA} \\ 0 & 0 \end{pmatrix}$

Here $Q_T$ is the submatrix of rates among transient states. Two key quantities follow:

• Mean time to absorption from each transient state: $\mathbf{m} = -Q_T^{-1} \mathbf{1}$
• Absorption probabilities (probability of being absorbed into each absorbing state): $B = -Q_T^{-1} Q_{TA}$

These formulas are direct analogues of the discrete-time results using the fundamental matrix.