Continuous-time Markov chain
A continuous-time Markov chain (CTMC) is a stochastic process \{X(t): t \geq 0\} taking values in a discrete state space S, typically finite or countable, that satisfies the Markov property: the conditional distribution of the process at any future time depends only on the current state and is independent of the past history.[1] Formally, for states x_0, x_1, \dots, x_{n+1} \in S and times $0 \leq t_0 < t_1 < \dots < t_{n+1}, P(X(t_{n+1}) = x_{n+1} \mid X(t_i) = x_i \text{ for } i = 0, \dots, n) = P(X(t_{n+1}) = x_{n+1} \mid X(t_n) = x_n). This memoryless property extends the discrete-time Markov chain framework to continuous time, where state changes occur at random, exponentially distributed holding times rather than fixed intervals.[2] The behavior of a CTMC is fully specified by its infinitesimal generator matrix Q = (q_{ij})_{i,j \in S}, also known as the rate matrix, where q_{ij} for i \neq j represents the instantaneous transition rate from state i to state j, and the diagonal entries satisfy q_{ii} = -\sum_{j \neq i} q_{ij} to ensure the rows sum to zero.[3] The holding time in state i is exponentially distributed with parameter -\ q_{ii}, reflecting the memoryless nature of exponential distributions, and upon departure, the next state is chosen according to the embedded discrete-time Markov chain with transition probabilities proportional to the off-diagonal rates.[1] The transition probability matrix P(t) = (p_{ij}(t)), where p_{ij}(t) = P(X(t+s) = j \mid X(s) = i), evolves according to the Kolmogorov forward and backward equations: \frac{d}{dt} P(t) = P(t) Q = Q P(t), with P(0) = I.[2] CTMCs also satisfy the Chapman-Kolmogorov equations P(t+s) = P(t) P(s) for t, s > 0, enabling the semigroup structure of transition probabilities and facilitating long-term analysis.[1] For irreducible, positive recurrent chains, a unique stationary distribution \pi exists satisfying \pi Q = 0 and \sum_i \pi_i = 1, to which the distribution converges as t \to \infty regardless of the initial state.[2] Special cases include the Poisson process, a CTMC on the non-negative integers with constant upward transition rate, modeling event arrivals.[2] CTMCs are foundational in modeling systems with continuous-time dynamics and discrete states, such as birth-death processes, where transitions are restricted to increments or decrements by one unit, characterized by birth rates \lambda_i and death rates \mu_i.[4] These processes underpin queueing theory, including the M/M/1 queue, where customer arrivals follow a Poisson process (births) and service times are exponential (deaths), allowing computation of steady-state queue lengths and waiting times via balance equations.[5] Beyond queueing, CTMCs apply to reliability analysis of repairable systems, population dynamics in ecology, and chemical reaction networks, where states represent system configurations and rates capture event frequencies.[4]Introduction
Overview
A continuous-time Markov chain is a stochastic process \{X(t), t \geq 0\} taking values in a countable state space S, where the future evolution depends only on the current state, satisfying the Markov property: P(X(t+s) = j \mid X(u) \text{ for all } u \leq t) = P(X(t+s) = j \mid X(t) = i) for all t, s \geq 0 and i, j \in S.[6] This property ensures that the process is memoryless, with the probability distribution of future states conditional on the present state alone. Continuous-time Markov chains extend the framework of discrete-time Markov chains, which operate over fixed time steps, to scenarios where transitions occur at arbitrary times in a continuous timeline.[6] The foundational theory was developed by Andrey Kolmogorov in his 1931 paper, where he formalized analytical methods for such processes, building on earlier discrete-time concepts to handle continuous parameterizations.[7] At their core, these chains model systems where the system remains in a state for a random duration governed by exponential holding times, after which it jumps to another state according to specified probabilities, preserving the memoryless nature of exponential distributions.[6] They find broad applications in modeling phenomena such as customer flows in queueing systems, component failure patterns in reliability engineering, and species interactions in population dynamics.Prerequisites and notation
To understand continuous-time Markov chains (CTMCs), readers should have a foundational knowledge of probability theory, including conditional probability and the properties of the exponential distribution, along with basic concepts in stochastic processes and discrete-time Markov chains.[8][9] These prerequisites enable comprehension of how CTMCs extend discrete-time models to continuous time while preserving the Markov property.[10] The state space S of a CTMC is a countable set, which can be finite or countably infinite, such as the set of non-negative integers.[11] The process is denoted by \{X(t) : t \geq 0\}, where X(t) represents the state at time t. Paths of the process are right-continuous with left limits, known as càdlàg paths.[12] Conditional probabilities and expectations starting from an initial state i \in S are denoted P_i and E_i, respectively.[13] CTMCs are generally assumed to be time-homogeneous, with transition rates independent of absolute time, though more general time-inhomogeneous cases exist.[14] Specific assumptions, such as irreducibility (where every state is reachable from every other), may apply in certain analyses but are not universal.[9] The paths of a CTMC almost surely feature only finitely many jumps over any finite time interval, reflecting the process's piecewise constant nature.[11] Holding times between jumps follow exponential distributions, underpinning the memoryless transitions central to CTMCs./16%3A_Markov_Processes/16.15%3A_Introduction_to_Continuous-Time_Markov_Chains)Definitions
Transition probability approach
A continuous-time Markov chain (CTMC) can be defined through its transition probability matrix P(t), where the entry P_{ij}(t) = \mathbb{P}(X(t) = j \mid X(0) = i) represents the probability of being in state j at time t \geq 0, given the initial state i at time 0, for a stochastic process \{X(t): t \geq 0\} with countable state space.[1] The Markov property in continuous time states that for any $0 \leq t_0 < t_1 < \cdots < t_n, the conditional distribution of X(t_n) given the history up to t_{n-1} depends only on X(t_{n-1}), formally:\mathbb{P}(X(t_n) = j \mid X(t_k) = x_k, \, k = 0, \dots, n-1) = \mathbb{P}(X(t_n) = j \mid X(t_{n-1}) = x_{n-1}) = P_{x_{n-1} j}(t_n - t_{n-1}).
This implies that future states are independent of the past given the present, enabling the use of time-homogeneous transition probabilities.[15][1] The transition matrices satisfy the semigroup property: for all s, t \geq 0, P(s + t) = P(s) P(t), where matrix multiplication is used, reflecting the composition of probabilities over disjoint time intervals.[1][16] The Chapman-Kolmogorov equations follow from the semigroup property and provide a way to compute transitions over longer intervals via summation: for $0 \leq s < u < t,
P_{ij}(t - s) = \sum_k P_{ik}(u - s) P_{kj}(t - u),
or in matrix form, P(t) = P(s) P(t - s) for t > s \geq 0. These equations ensure consistency in probability calculations across intermediate times.[17][16] The family \{P(t): t \geq 0\} is uniquely determined by the initial condition P(0) = I, the identity matrix, and right-continuity at t = 0, meaning \lim_{t \to 0^+} P(t) = I, which guarantees the process starts correctly and evolves continuously in probability.[1][18] As an example, consider a simple pure death process on states \{0, 1, \dots, N\}, where from state i, the process moves to i-1 at rate i \mu for constant \mu > 0, modeling independent deaths of i individuals each dying at rate \mu. The transition probabilities are explicitly solvable as binomial probabilities: for j \leq i,
P_{ij}(t) = \binom{i}{j} (e^{-\mu t})^j (1 - e^{-\mu t})^{i - j},
reflecting the number of survivors following independent exponential waiting times, with P_{ij}(t) = 0 for j > i. This satisfies the semigroup property since the product of two such matrices yields the distribution after combined time.[19][20] The infinitesimal generator arises as the right-derivative of P(t) at t = 0, connecting to rate-based descriptions.[1]