Continuous-Time Markov Chain

A continuous-time Markov chain (CTMC) is a stochastic process whose time parameter ranges continuously over $t\geq 0$ , whose state space is finite or countable, and whose future evolution depends on its past only through its present state. It is the continuous-time counterpart of a discrete-time Markov chain. In the standard time-homogeneous formulation, the process remains in a state for an exponentially distributed holding time and then jumps to another state. “Continuous-time” describes the time parameter, not continuity of the sample paths: these paths are ordinarily piecewise constant, with discontinuities at jump times. (columbia.edu)

Definition and transition probabilities

Let $X=(X_t)_{t\geq0}$ take values in a finite or countable set $S$ . Its Markov property can be expressed as

\Pr(X_{s+t}=j\mid\mathcal F_s) = \Pr(X_{s+t}=j\mid X_s),

where $\mathcal F_s$ is the filtration representing the observed history through time $s$ . Thus knowledge of earlier states provides no additional predictive information once $X_s$ is known. For a time-homogeneous chain, the conditional probability on the right depends on elapsed time $t$ , but not on calendar time $s$ . Define

p_{ij}(t)=\Pr(X_t=j\mid X_0=i).

The transition matrices $P(t)=(p_{ij}(t))$ satisfy the Chapman–Kolmogorov equations

P(s+t)=P(s)P(t),\qquad P(0)=I.

Together with the initial probability distribution, these matrices determine all finite-dimensional distributions of the process. Time homogeneity does not mean that the distribution of $X_t$ is constant in time; that stronger property requires a stationary initial distribution. (columbia.edu)

Transition rates and the generator

A time-homogeneous CTMC is commonly specified by its infinitesimal generator, or rate matrix, $Q=(q_{ij})$ . For distinct states,

q_{ij}=\lim_{h\downarrow0}\frac{p_{ij}(h)}{h},

and

q_{ii}=-q_i,\qquad q_i=\sum_{j\neq i}q_{ij}.

In the standard conservative formulation, $q_{ij}\geq0$ for $i\neq j$ , every $q_i$ is finite, and each row sums to zero. For a small interval $h$ ,

p_{ij}(h)=q_{ij}h+o(h)\quad(i\neq j), \qquad p_{ii}(h)=1-q_i h+o(h).

Rates have units of inverse time; they are not probabilities and can exceed one numerically. (statslab.cam.ac.uk)

For a finite state space, every such matrix generates a unique chain, and

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

The matrix exponential solves the Kolmogorov backward and forward equations:

\frac{dP(t)}{dt}=QP(t), \qquad \frac{dP(t)}{dt}=P(t)Q.

If distributions are represented as row vectors, then

\mu(t)=\mu(0)P(t),\qquad \mu'(t)=\mu(t)Q.

For infinite state spaces, unbounded rates introduce additional convergence and domain issues; the finite-matrix exponential formula cannot simply be applied without qualification. (continuous-time-mcs.quantecon.org)

Holding times and the embedded jump chain

When the process enters state $i$ with $q_i>0$ , its holding time $H$ has the exponential distribution

\Pr(H>t)=e^{-q_it}, \qquad \mathbb E[H]=\frac1{q_i}.

Its next state is $j\neq i$ with probability

r_{ij}=\frac{q_{ij}}{q_i}.

Conditional on the current state, the holding time and destination are independent. The sequence of states visited at actual jumps is the embedded jump chain, with transition matrix $R=(r_{ij})$ . A state with $q_i=0$ is absorbing. These rules construct the CTMC successively, at least until a possible explosion time. (columbia.edu)

Exponential holding times are memoryless:

\Pr(H>s+t\mid H>s)=\Pr(H>t).

Consequently, the time already spent in a state does not alter the remaining holding-time distribution. This property explains why a time-homogeneous jump model with arbitrary non-exponential holding times is generally not Markov on its original state space. (ocw.mit.edu)

Explosion and existence

A chain is explosive if infinitely many jumps can occur in a finite amount of time with positive probability. Writing successive holding times as $H_0,H_1,\ldots$ , the explosion time is

\zeta=\sum_{n=0}^{\infty}H_n.

Non-explosion means $\zeta=\infty$ almost surely. Finite-state chains with finite rates are non-explosive. More generally, a uniform bound $\sup_i q_i<\infty$ is sufficient, although not necessary. Thus finite exit rates at individual states do not by themselves exclude explosion. (statslab.cam.ac.uk)

For a potentially explosive generator, the minimal process is terminated at explosion, usually by sending it to an additional cemetery state. Its transition probabilities on the original state space may then have row sums below one. Alternative continuations after explosion require further specification: in such cases, the generator alone does not determine post-explosion behavior. (statslab.cam.ac.uk)

Stationary distributions and reversibility

A stationary distribution is a probability vector $\pi$ satisfying

\pi P(t)=\pi\qquad(t\geq0).

For finite-state chains—and for countable-state chains under appropriate regularity conditions—it can be found from

\pi Q=0,\qquad \sum_i\pi_i=1.

These are global balance equations: stationary probability flow into each state equals flow out. An irreducible finite-state CTMC has a unique stationary distribution, and $p_{ij}(t)\to\pi_j$ . For irreducible, non-explosive countable-state chains, a stationary probability distribution exists precisely when the chain is positive recurrent. Infinite chains can therefore lack a stationary probability distribution. (arxiv.org)

The stronger detailed balance equations are

\pi_iq_{ij}=\pi_jq_{ji}.

For a finite-state chain, these imply stationarity and reversibility: a stationary trajectory has the same probability law when time is reversed. Stationarity alone does not require detailed balance. (columbia.edu)

The embedded jump chain generally has different stationary probabilities. If all $q_i>0$ , its stationary vector $\alpha$ yields the CTMC stationary vector, when normalization is finite, through

\pi_i= \frac{\alpha_i/q_i}{\sum_k\alpha_k/q_k}.

This weights visit frequencies by mean holding times: states with slower exits occupy more clock time per visit. (columbia.edu)

Examples and applications

A two-state chain with transition rates $a>0$ from $0$ to $1$ and $b>0$ from $1$ to $0$ has

Q= \begin{pmatrix} -a&a\\ b&-b \end{pmatrix}.

Solving the balance equations gives

\pi_0=\frac{b}{a+b},\qquad \pi_1=\frac{a}{a+b},

while the transition probability from $0$ to $1$ is

p_{01}(t)=\frac{a}{a+b}\left(1-e^{-(a+b)t}\right).

These formulas illustrate separately the long-run occupancy and the approach to equilibrium. (continuous-time-mcs.quantecon.org)

A Poisson process is a CTMC on the nonnegative integers with $q_{n,n+1}=\lambda$ and no other off-diagonal transitions. Its count at time $t$ , starting from zero, has the Poisson distribution with mean $\lambda t$ . A birth–death process generalizes this structure by allowing transitions from $n$ to $n+1$ at rate $\lambda_n$ and from $n$ to $n-1$ at rate $\mu_n$ . Such processes model population counts and queues. (statslab.cam.ac.uk)

In chemical kinetics, states can record molecule counts, with reactions producing jumps between count vectors. CTMCs also model reliability, maintenance, telecommunications, and computer-system performance. Their suitability depends on whether the chosen state captures the information needed to determine future transition rates. (arxiv.org)

Simulation, computation, and limitations

Exact path simulation follows the holding-time construction: sample an exponential waiting time, select the destination using $q_{ij}/q_i$ , and repeat. This avoids introducing an artificial fixed time step. (columbia.edu)

For bounded exit rates, uniformization provides another construction. Choose $\nu>0$ with $\nu\geq\sup_iq_i$ , and set

B=I+\frac{Q}{\nu}.

Then

P(t)=e^{-\nu t} \sum_{n=0}^{\infty}\frac{(\nu t)^n}{n!}B^n.

The process can be represented by a discrete-time chain with matrix $B$ , updated at Poisson event times of rate $\nu$ . Some updates leave the state unchanged. Uniformization is therefore neither the embedded chain of actual jumps nor sampling at equally spaced times. It also gives a numerical method whose series-truncation error is controlled by the omitted Poisson tail. (sciencedirect.com)

Large or infinite state spaces make direct probability calculations expensive. Finite-state truncations can help, but their boundary treatment and approximation errors must be examined rather than assumed negligible. (arxiv.org)

Time-dependent environments require an inhomogeneous model with rates $Q(t)$ ; a single constant-generator exponential then generally does not describe its evolution. Non-exponential residence times or omitted historical information likewise require a different model or an enlarged state description. These are limitations of a particular CTMC representation, not evidence that all stochastic systems are memoryless. (sciencedirect.com)

References

Continuous-Time Markov Chains — Karl Sigmancolumbia.edu
Continuous-Time Markov Chainscolumbia.edu
Introduction to Probability, Selected Textbook Summary Materialocw.mit.edu
Semigroups and Generators — Continuous Time Markov Chainscontinuous-time-mcs.quantecon.org
Stationary distributions of continuous-time Markov chains: a review of theory and truncation-based approximationsarxiv.org