Continuous-Time Chains & Jump Processes

a continuous-time Markov chain

A continuous-time Markov chain (CTMC) is a Markov process X_t taking values in a countable state space S, where time runs continuously but the state changes only by sudden jumps. It is the continuous-time analogue of the discrete-time Markov chain you met in Vol I, and the natural model for systems that wait a random amount of time and then jump: a queue length, the size of a population, the number of molecules of a species, a particle hopping on a graph. The question it answers is: how do we describe a Markovian process whose paths are constant in between jumps, when there is no smallest time step to advance by?

Markovianity in continuous time forces a specific structure. The memoryless property says that given the present state i, the future is independent of the past; in particular the remaining time until the next jump must be memoryless, which on the half-line means it is exponentially distributed. So when the chain enters state i it stays for an exponential holding time of some rate q_i = -q_ii, and then jumps to a new state j (with j not equal to i) chosen by a probability that does not depend on how long it waited. Equivalently, while in i the chain attempts a transition to each j at rate q_ij, and the first 'alarm' to ring sends it there. The numbers q_ij (off-diagonal nonnegative, with row sums q_ii = -sum_{j != i} q_ij) form the generator or Q-matrix, and the transition probabilities P_t(i,j) = P(X_t = j given X_0 = i) satisfy P_t = e^(tQ), the matrix exponential. The Markov property is encoded in the semigroup law P_{s+t} = P_s P_t (Chapman-Kolmogorov).

CTMCs are the workhorse model of applied probability — queueing, reliability, chemical reaction networks, population genetics, epidemics. The rigorous theory has a subtlety that does not arise for discrete chains: on a countable (infinite) state space the chain can take infinitely many jumps in finite time and 'explode'. One must then specify what happens — usually by taking the minimal process, which is killed at the explosion time. Be careful: continuous-time does NOT mean continuous paths. A CTMC has piecewise-constant, right-continuous (cadlag) paths; the only randomness in a path is the sequence of states visited and the holding times. Brownian motion is a different kind of continuous-time Markov process, with continuous paths and an uncountable state space.

A two-state chain with states {0,1}, jumping 0->1 at rate lambda and 1->0 at rate mu. Then Q has rows ( -lambda, lambda ) and ( mu, -mu ), and solving P_t = e^(tQ) gives P_t(0,0) = mu/(lambda+mu) + lambda/(lambda+mu) e^(-(lambda+mu)t), which decays to the stationary value mu/(lambda+mu).

The simplest CTMC: a single component flipping between 'up' and 'down', the basic reliability/on-off model.

Continuous-time does not mean continuous-path: a CTMC has piecewise-constant cadlag paths and jumps. The classic error is forgetting that an infinite-state CTMC can explode, so P_t need not even be a probability matrix (rows may sum to less than 1) unless the chain is non-explosive.

Also called
CTMCcontinuous-time chain連續時間鏈馬可夫跳躍過程