Continuous-Time Markov Chains

A continuous-time Markov chain (CTMC) is the continuous-time analog of a discrete-time Markov chain: the state takes values in a finite set $\cX$, but transitions can occur at any real-valued time rather than at discrete steps. CTMCs appear across scientific modeling — in queueing theory, population genetics, chemical reaction networks, and, more recently, as the noising processes in discrete diffusion models.

Definition¶

A CTMC is a stochastic process $\{x_t : t \in [0, T]\}$ taking values on a finite state space $\cX$ such that:

1. Right-continuity: sample paths $t \mapsto x_t$ are right-continuous with finitely many jumps on any bounded interval.

2. Markov property: for all $t > s$,

   $$\Pr(x_t = j \mid \{x_u : u \leq s\}) = \Pr(x_t = j \mid x_s).$$

   (1)

The Markov property says the future depends on the past only through the present state — exactly as in a discrete-time chain, but now holding at any continuous time $s$.

Transition Probabilities¶

A CTMC is uniquely characterized by its transition probabilities $q_{t|s}(j \mid i) = \Pr(x_t = j \mid x_s = i)$ for $t \geq s$. These satisfy the Chapman–Kolmogorov equations: for all $s \leq u \leq t$,

Writing $Q_{t|s}$ for the $|\cX| \times |\cX|$ matrix with $(i, j)$ entry $q_{t|s}(j \mid i)$, this is the matrix product $Q_{t|s} = Q_{u|s}\, Q_{t|u}$. The marginal distribution $\pi_t(j) = \Pr(x_t = j)$ evolves according to $\pi_t^\top = \pi_s^\top Q_{t|s}$.

Rate Matrices¶

The local behavior of a CTMC is captured by its rate matrix (also called the generator):

Intuitively, $R_s(i \to j)$ is the instantaneous probability flow from state $i$ to state $j$ at time $s$. Every rate matrix satisfies:

1. $R_s(i \to j) \geq 0$ for $i \neq j$ — probability flow between distinct states is non-negative.

2. $\sum_j R_s(i \to j) = 0$ — probability is conserved, so $R_s(i \to i) = -\sum_{j \neq i} R_s(i \to j)$.

Define $R_s(i) = \sum_{j \neq i} R_s(i \to j)$ as the total outward rate from state $i$ at time $s$. A homogeneous CTMC has a time-invariant rate matrix $R_s \equiv R$.

Given $R$, the transition matrix satisfies the Kolmogorov forward equation $\partial_t Q_{t|s} = Q_{t|s} R$, which for a homogeneous chain has the matrix exponential solution $Q_{t|s} = e^{(t-s)R}$.

Simulation: Gillespie’s Algorithm¶

A homogeneous CTMC can be simulated exactly using Gillespie’s algorithm Gillespie, 1977.

Initialize $x_0 \sim \pi_0$, set $t_0 = 0$, $i = 0$.

While $t_i < T$:

• Draw the waiting time $\Delta_i \sim \mathrm{Exp}(R(x_i))$.

• If $t_i + \Delta_i > T$, return $\{(t_j, x_j)\}_{j=0}^i$.

• Otherwise, set $t_{i+1} \leftarrow t_i + \Delta_i$ and draw the next state,

  $$x_{i+1} \sim \mathrm{Cat}\!\left(\left[\frac{R(x_i \to j)}{R(x_i)}\right]_{j \neq x_i}\right).$$

  (4)

• Increment $i \leftarrow i + 1$.

The exponential waiting time follows from the Markov property: given the current state, the time until the next jump must be memoryless, and the exponential distribution is the unique continuous memoryless distribution.

Connection to Poisson Processes¶

A CTMC can be recast as a marked Poisson process with event times $\{t_i\}$ and marks $\{x_i\} \subseteq \cX$. Given the history $\cH_t$ (which includes the current state $x_t$ via right-continuity), the conditional intensity for a jump to state $j$ is

Gillespie’s algorithm is then a direct application of two Poisson process properties:

• Superposition: the total rate $\lambda(t \mid \cH_t) = \sum_{j \neq x_t} R(x_t \to j) = R(x_t)$ gives the intensity of the next-event process, whose inter-arrival times are exponential.

• Thinning: given a jump occurs at time $t_{i+1}$, the destination state is sampled proportionally to the individual rates $R(x_i \to j)$, recovering the categorical draw.

Rao & Teh (2013) exploited this Poisson representation to develop an efficient Gibbs sampler for CTMCs.

Conclusion¶

A CTMC is fully specified by its rate matrix, which governs instantaneous probability flow between states. The Chapman–Kolmogorov equations, Kolmogorov forward equation, and matrix exponential carry over from the discrete-time theory with minimal modification. Gillespie’s algorithm provides exact simulation by drawing exponential holding times and categorical jumps — a construction that is transparent once the Poisson process connection is made.