Fact-checked by Grok 2 weeks ago

Transition-rate matrix

A transition-rate matrix, also known as the infinitesimal generator or Q-matrix, is a square matrix that defines the instantaneous transition rates in a continuous-time Markov chain (CTMC), a stochastic process where the time spent in each state follows an exponential distribution and transitions depend only on the current state.^[1] In this matrix Q = (q_{ij}), the off-diagonal entries q_{ij} for i \neq j represent the rate of transition from state i to state j, while the diagonal entries satisfy q_{ii} = -\sum_{j \neq i} q_{ij}, indicating the total rate of departure from state i.^[2] The rows of the Q-matrix sum to zero, ensuring conservation of probability, with off-diagonal elements being non-negative and diagonal elements non-positive.^[1] It plays a central role in modeling the dynamics of CTMCs by governing the evolution of the transition probability matrix P(t), which satisfies the Kolmogorov backward equations P'(t) = Q P(t) (or the forward equations P'(t) = P(t) Q, depending on the convention), with the explicit solution P(t) = e^{tQ}.^[2] This matrix is constructed from the holding time parameters (exponential rates) in each state and the probabilities of the embedded discrete-time jump chain, linking continuous-time behavior to discrete transitions.^[3] Transition-rate matrices are essential in applications such as queueing theory, reliability analysis, population dynamics, and chemical kinetics, where they enable the computation of steady-state distributions via balance equations \pi Q = 0 (with \sum \pi_i = 1) for ergodic chains.^[1] Key properties include the requirement for the matrix to be conservative (row sums zero) and, for well-defined CTMCs, the off-diagonal entries to ensure finite jump rates.^[2] Unlike the transition probability matrix in discrete-time Markov chains, the Q-matrix captures rates rather than probabilities, allowing for arbitrary transition times.^[3]

Definition and Basics

Formal Definition

The transition-rate matrix, often denoted as Q = (q_{ij}), is a square matrix that specifies the instantaneous rates of transitions between states in a continuous-time stochastic process. For i \neq j, the off-diagonal element q_{ij} represents the non-negative transition rate from state i to state j, measured in transitions per unit time.^[4]^[1] The diagonal elements are defined such that q_{ii} = -\sum_{j \neq i} q_{ij} for each row i, which ensures that the entire row sums to zero and reflects the total rate of departure from state i.^[5]^[6] In probability theory, this matrix is also known as the infinitesimal generator or intensity matrix of the process.^[4]^[1] For a finite state space with n states, Q takes the form of an n \times n matrix, where the rates quantify the embedded jump process within a continuous-time Markov chain framework.^[5]^[6]

Context in Continuous-Time Markov Chains

A continuous-time Markov chain (CTMC) is defined as a stochastic process \{X(t): t \geq 0\} with a countable state space S, where the Markov property holds: for all t, s \geq 0 and states i, j \in S, the conditional probability P(X(t+s) = j \mid X(t) = i, \{X(u): u \leq t\}) equals P(X(t+s) = j \mid X(t) = i).^[7] This property ensures that the future evolution depends only on the current state, independent of the history prior to time t.^[7] Unlike discrete-time Markov chains, where transitions occur at fixed intervals and states change deterministically in time steps, CTMCs allow transitions at random times, with holding times in each state following an exponential distribution parameterized by rates -q_{ii}, where q_{ii} are the diagonal elements of the transition-rate matrix Q.^[7] The matrix Q thus governs both the embedded jump chain—a discrete-time Markov chain capturing the sequence of states visited—and the exponential holding times that determine the timing of jumps.^[7] CTMCs typically assume a finite or countable state space S, enabling analytical tractability for properties like steady-state distributions.^[7] For long-term behavior, such as convergence to equilibrium, the chain is often assumed to be irreducible, meaning every state is reachable from any other, preventing absorption or disconnection in the state space.^[7] The framework of CTMCs originated in the study of Poisson processes, which represent the simplest case of a pure birth process, and was generalized by Andrei Kolmogorov in the 1930s through his development of analytic methods for Markov processes.^[8]

Mathematical Properties

Matrix Structure and Constraints

The transition-rate matrix, often denoted as Q = (q_{ij}), is structured such that its off-diagonal elements q_{ij} for i \neq j are non-negative real numbers, representing the instantaneous rates at which the process transitions from state i to state j. These rates quantify the intensity of direct jumps between distinct states in a continuous-time Markov chain (CTMC).^[7]^[9] A strict inequality q_{ij} > 0 indicates that a direct transition from i to j is possible with positive probability, whereas q_{ij} = 0 implies no direct transition occurs, though indirect paths may still exist through other states.^[7]^[10] A fundamental constraint on the matrix arises from the conservation of probability, requiring that the sum of each row equals zero: \sum_{j} q_{ij} = 0 for every state i. This condition ensures that the total probability mass remains preserved over time, as the rates of leaving and entering states balance exactly.^[7]^[9] Consequently, the diagonal elements are negative: q_{ii} = -\sum_{j \neq i} q_{ij} < 0 (unless the state is absorbing, in which case q_{ii} = 0), with the magnitude |q_{ii}| interpreted as the total exit rate from state i, or the inverse of the expected holding time in that state.^[7]^[11] The matrix is termed conservative if the row sums are exactly zero, upholding the stochastic nature of the embedded process without probability leakage.^[12]^[7] In non-conservative cases, where row sums are strictly negative, the matrix is defective, often modeling scenarios with killing or external probability loss, such as in processes with finite lifetimes or defective population models.^[12]^[13]

Eigenvalues and Eigenvectors

The transition-rate matrix Q, also known as the infinitesimal generator of a continuous-time Markov chain, always possesses 0 as an eigenvalue. The corresponding left eigenvector is the stationary distribution \pi (row vector), which satisfies \pi Q = 0 with \sum_i \pi_i = 1 in the case of irreducible chains. The right eigenvector associated with this eigenvalue 0 is the all-ones column vector \mathbf{1}, satisfying Q \mathbf{1} = 0, a consequence of the row-sum zero property of Q.^[14] All other eigenvalues \lambda of Q satisfy \operatorname{Re}(\lambda) \leq 0, with strict inequality \operatorname{Re}(\lambda) < 0 holding for ergodic (irreducible and positive recurrent) chains, ensuring a spectral gap that governs convergence to stationarity. By the Gershgorin circle theorem, the real parts are further bounded below by \operatorname{Re}(\lambda) \geq 2 \min_i q_{ii}, where q_{ii} < 0 are the diagonal entries. For any eigenvector v corresponding to a nonzero eigenvalue \lambda \neq 0, the components sum to zero, i.e., \sum_i v_i = 0, since \mathbf{1}^T Q v = \lambda \mathbf{1}^T v = 0 implies \mathbf{1}^T v = 0.^[14] In chains where the state space forms a strongly connected graph, the eigenvalue 0 has multiplicity one. More generally, the algebraic multiplicity of 0 equals the number of recurrent classes in the chain. The matrix Q is structurally akin to a weighted graph Laplacian, and in the context of random walks on undirected graphs, Q is similar to -L, where L is the Laplacian of the transition graph, facilitating spectral analysis via graph theory.^[15]

Formulation and Derivation

Relation to Transition Probability Matrix

The transition probability matrix P(t) for a continuous-time Markov chain is defined by its entries p_{ij}(t) = \Pr(X(t) = j \mid X(0) = i), where X denotes the state process.^[1] This matrix satisfies the Chapman-Kolmogorov equations, P(t + s) = P(t) P(s) for all t, s \geq 0, which express the semigroup property of the transition probabilities.^[1]^[16] The connection to the transition-rate matrix Q arises through the Kolmogorov differential equations. The forward equation is given by \frac{d}{dt} P(t) = P(t) Q with initial condition P(0) = I, the identity matrix.^[1]^[16] The backward equation is \frac{d}{dt} P(t) = Q P(t), also with P(0) = I.^[1]^[16] The unique solution to either equation is the matrix exponential P(t) = \exp(t Q), which encodes the time evolution of the probabilities driven by the rates in Q.^[1]^[16] The matrix P(t) inherits key properties from Q: it is row-stochastic for all t \geq 0, meaning each row sums to 1, ensuring valid probabilities.^[1] Additionally, \lim_{t \to 0} P(t) = I, reflecting the initial state, and for ergodic chains (those irreducible and positive recurrent), \lim_{t \to \infty} P(t) converges to the matrix with identical rows given by the stationary distribution.^[1]^[16] To compute \exp(t Q), one approach is the power series expansion \exp(t Q) = \sum_{k=0}^{\infty} \frac{(t Q)^k}{k!}, which converges for any finite state space due to the bounded spectral radius of Q (eigenvalues have nonpositive real parts).^[1] An alternative is the uniformization method, which approximates the continuous-time chain by a discrete-time chain with uniform jump rate \lambda = \max_i (-q_{ii}).^[10] Here, define the discrete transition matrix \tilde{P} = I + Q / \lambda, and then P(t) = \sum_{k=0}^{\infty} e^{-\lambda t} \frac{(\lambda t)^k}{k!} \tilde{P}^k, where the sum is over Poisson probabilities for the number of jumps.^[10] This representation leverages discrete-time computations while preserving the exact solution when truncated appropriately.^[10]

Kolmogorov Equations

The Kolmogorov equations describe the time evolution of transition probabilities in continuous-time Markov chains governed by a transition-rate matrix Q. These differential equations, derived from the Chapman-Kolmogorov relations, provide the infinitesimal generator for the process's dynamics. The Kolmogorov forward equation, also known as the Chapman-Kolmogorov forward equation, governs the evolution of the probability distribution p(t), where p_j(t) is the probability of being in state j at time t. It states that the rate of change of p_j(t) is given by

\frac{d}{dt} p_j(t) = \sum_{i} p_i(t) q_{ij},

where the sum is over all states i, and q_{ij} are the entries of the transition-rate matrix Q. In vector-matrix form, this becomes \frac{d}{dt} \mathbf{p}(t) = \mathbf{p}(t) Q.^[2]^[1] In physics and chemistry, this forward equation is recognized as the master equation, which balances the rate of change in the probability of state j as the influx from other states minus the outflux from j, reflecting conservation of probability under the process's stochastic jumps.^[17]^[18] The Kolmogorov backward equation addresses the evolution of individual transition probabilities p_{ij}(t), the probability of transitioning from state i to j in time t. It is expressed as

\frac{d}{dt} p_{ij}(t) = \sum_{k} q_{ik} p_{kj}(t),

with the matrix form Q P(t) = \frac{d}{dt} P(t), where P(t) is the transition probability matrix.^[19]^[20] The initial conditions for these equations are \mathbf{p}(0) as the initial probability distribution and P(0) = I, the identity matrix, ensuring the process starts correctly.^[2]^[21] Under mild conditions on Q, such as bounded transition rates and a finite state space, solutions to the Kolmogorov equations exist and are unique, often established via the semigroup property of the transition matrix.^[1]^[18] The transition-rate matrix Q relates to the embedded discrete-time Markov chain, where jumps occur at holding times that are exponentially distributed with rates given by the diagonal entries of Q (negative off-diagonal sums), capturing the continuous-time embedding of discrete transitions.^[2]^[21] The solution to these equations yields the transition probability matrix P(t) = \exp(t Q).^[2]

Examples and Applications

Simple Two-State System

A simple two-state continuous-time Markov chain (CTMC) provides an illustrative example of the transition-rate matrix, often modeling binary systems such as on/off states or healthy/faulty conditions.^[22] Consider states labeled {0, 1}, where the transition-rate matrix Q is given by

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

with \alpha > 0 and \beta > 0 denoting the transition rates from state 0 to 1 and from 1 to 0, respectively.^[22] The off-diagonal entries represent the instantaneous rates of transition, while the diagonal entries ensure that each row sums to zero, reflecting the conservation of probability.^[22] The holding time in state 0 follows an exponential distribution with rate \alpha, yielding a mean holding time of $1/\alpha; similarly, the holding time in state 1 is exponential with rate \beta and mean $1/\beta.^[22] These holding times capture the duration spent in each state before a transition occurs, independent of prior history due to the Markov property.^[22] The transition probabilities p_{ij}(t) = \Pr(X(t) = j \mid X(0) = i) for this CTMC satisfy the Kolmogorov forward equations \frac{d}{dt} P(t) = P(t) Q, with initial condition P(0) = I, where P(t) = (p_{ij}(t)).^[22] The solution is P(t) = \exp(t Q), and for the two-state case, explicit forms can be obtained by solving the differential equations. In particular,

p_{00}(t) = \frac{\beta + \alpha e^{-(\alpha + \beta) t}}{\alpha + \beta},

derived by integrating the system starting from state 0.^[22] The other entries follow symmetrically: p_{01}(t) = 1 - p_{00}(t), p_{10}(t) = 1 - p_{11}(t), and p_{11}(t) = \frac{\alpha + \beta e^{-(\alpha + \beta) t}}{\alpha + \beta}.^[22] As t \to \infty, the chain converges to its stationary distribution \pi = \left( \frac{\beta}{\alpha + \beta}, \frac{\alpha}{\alpha + \beta} \right), satisfying \pi Q = 0 and \sum \pi_i = 1, which balances the flow between states.^[22] This distribution represents the long-run proportion of time spent in each state.^[22] The eigenvalues of Q are 0 and -(\alpha + \beta), with the zero eigenvalue corresponding to the stationary behavior.^[22] These allow explicit diagonalization: Q = P D P^{-1}, where D = \operatorname{diag}(0, -(\alpha + \beta)), leading to \exp(t Q) = P \exp(t D) P^{-1}, which simplifies computation of P(t).^[22] The general eigenvalue properties of transition-rate matrices, such as non-positive real parts, underpin this decomposition.^[22] Graphically, the two-state system is represented as two nodes connected by bidirectional edges weighted by \alpha (from 0 to 1) and \beta (from 1 to 0), visualizing the transition dynamics.^[22]

Queueing Theory Example

In queueing theory, the M/M/1 queue serves as a foundational example of a continuous-time Markov chain (CTMC) modeled using a transition-rate matrix, where the state space represents the number of customers in the system, denoted as {0, 1, 2, \dots}.^[23] Arrivals follow a Poisson process with rate \lambda, and service times are exponentially distributed with rate \mu, requiring \mu > \lambda for system stability to ensure a finite steady-state distribution.^[24] This model is a birth-death process, a special case of CTMC with transitions only to adjacent states.^[25] The transition-rate matrix Q for the M/M/1 queue is infinite-dimensional and tridiagonal, reflecting the birth-death structure.^[26] Specifically, the off-diagonal entries are q_{i,i+1} = \lambda for all i \geq 0 (representing arrival "births"), and q_{i,i-1} = \mu for i \geq 1 (representing service completions or "deaths"). The diagonal elements are q_{0,0} = -\lambda and q_{i,i} = -(\lambda + \mu) for i \geq 1, ensuring the rows sum to zero as required for a rate matrix.^[27] This structure features a constant superdiagonal of \lambda, a subdiagonal of \mu (starting from the second row), and a diagonal of -(\lambda + \mu) except for the first entry, which captures the absence of departures from the empty state.^[25] For steady-state analysis, the stationary distribution \pi satisfies \pi Q = 0 with \sum_{i=0}^\infty \pi_i = 1.^[24] Under the stability condition \rho = \lambda / \mu < 1, the solution is the geometric distribution \pi_i = (1 - \rho) \rho^i for i \geq 0.^[23] From this, key performance measures follow, such as the mean number of customers in the system, L = \rho / (1 - \rho), obtained by summing i \pi_i over the states.^[28] Transient behavior in the M/M/1 queue, which tracks the time-dependent state probabilities, is analytically challenging due to the infinite state space and requires solving the Kolmogorov forward equations.^[27] Exact solutions are rarely feasible, so approximations like uniformization are commonly employed, converting the CTMC to a discrete-time Markov chain with a uniform transition rate for computational tractability.^[29]

References

[1]
[PDF] 1 IEOR 6711: Continuous-Time Markov Chains
Thus a CTMC can simply be described by a transition matrix P = (Pij), describing how the chain changes state step-by-step at transition epochs, together with a ...
[2]
[PDF] CONTINUOUS-TIME MARKOV CHAINS Definition 1. Acontinuous ...
Definition 1. Acontinuous-time Markov chainon a finite or countable state spaceX is a family of X valued random variables Xt = X (t ) indexed by t 2 R+.
[3]
[PDF] Continuous-time Markov Chains - San Jose State University
A continuous-time Markov chain has time in a state exponentially distributed, and the next state depends only on the current state, not the past.
[4]
The Generator Matrix - Probability Course
The generator matrix, usually shown by G, gives us an alternative way of analyzing continuous-time Markov chains. Consider a continuous-time Markov chain X(t).
[5]
16.16: Transition Matrices and Generators of Continuous-Time Chains
Aug 10, 2020 · As with any matrix on S , the transition matrices define left and right operations on functions which are generalizations of matrix ...
[6]
Rate Matrix - an overview | ScienceDirect Topics
A rate matrix is defined as an instantaneous rate matrix that describes the transition rates of a random process, where the elements indicate the rates of ...
[7]
[PDF] Markov Chains - CAPE
Here is the definition of a continuous-time Markov chain in terms of its jump chain and holding times. Recall that a minimal process is one which is set ...
[8]
[PDF] Chapter 6 Continuous Time Markov Chains
The elements off the main diagonal are non-negative. 3. Each row sums to zero. We also point out that given a state space S, the infinitesimal generator A ...
[9]
[PDF] CONTINUOUS-TIME MARKOV CHAINS - Columbia University
Dec 4, 2013 · When specifying the transition-rate matrix Q, it suffices to specify the off-diagonal elements. Qi,j for i 6= j, because the diagonal elements ...
[10]
[PDF] Tutorial on Structured Continuous-Time Markov Processes
The rows of Q sum to 0 (thus the diagonal elements are the negative row sums, if the diagonal element is excluded from the sum).
[11]
[PDF] Invariant measures and the q-matrix - University of Cambridge
Suppose that we are given a stable, conservative q-matrix, that is a collection of real numbers i,j ¢ S) where S is a countable set and. (91). (Ã¡ ¡ ‚± ‚ Í j ...
[12]
[PDF] Countable state Markov processes: non-explosiveness and moment ...
May 17, 2014 · ... Markov process with right-continuous sample paths (with respect to the discrete topology), and with conservative q-matrix, in other words Q ...
[13]
[PDF] Matrix Analysis for Continuous-Time Markov Chains
Aug 27, 2021 · Abstract: Continuous-time Markov chains have transition matrices that vary continuously in time. Classi- cal theory of nonnegative matrices, ...
[14]
[PDF] Reversible Markov Chains and Random Walks on Graphs
Page 1. Reversible Markov Chains and Random Walks on Graphs. David Aldous and James Allen Fill. Unfinished monograph, 2002 (this is recompiled version, 2014) ...
[15]
16. Transition Matrices and Generators of Continuous-Time Chains
In this section, we sill study the Markov chain in terms of the transition matrices in continuous time and a fundamentally important matrix known as the ...
[16]
Stochastic Processes in Physics and Chemistry - ScienceDirect.com
Chapter X - THE EXPANSION OF THE MASTER EQUATION. Pages 244 ... Description. The third edition of Van Kampen's standard work has been revised and updated.
[17]
[PDF] Chapter 1 CONTINUOUS TIME MARKOV CHAIN MODELS FOR ...
A reaction network is modeled as a continuous time Markov chain where the state is the number of molecules of each species, and reactions are transitions.
[18]
[PDF] 1 Continuous Time Processes - 1.1 Continuous Time Markov Chains
May 1, 2011 · The exponential nature of the transition time is compatible with the requirement (1.1.8). With this assumption one can rigorously establish.
[19]
[PDF] Continuous time Markov chains - Penn Engineering
Oct 16, 2017 · Continuous time Markov chains involve transition probability functions and limit probabilities. Exponential random variables are memoryless and ...
[20]
[PDF] 5 Continuous-Time Markov Chains - TTU Math
A Continuous-Time Markov Chain (CTMC) is a stochastic process where jumps can occur at any time t ≥ 0, with discrete random variables.
[21]
https://www.math.ttu.edu/~anpeace/files/Math5355Papers/Chp5CTMC.pdf
[22]
[PDF] Markov Processes and Queues - MIT OpenCourseWare
The time of the transition from 1 to 0 is said to be exponentially distributed with rate µ. The expected transition time is 1/µ. (Prove it!) Markov ...
[23]
[PDF] markov chains and queueing theory - UChicago Math
Aug 12, 2011 · In this paper, we introduce queueing processes and find the steady- state solution to the M/M/1 queue. A brief background in Markov chains,.
[24]
[PDF] 6.436J Lecture 26: Birth-death processes - DSpace@MIT
One of the immediate applications of birth-death processes is queueing theory. Consider the following system, known broadly as M/M/1 queueing system (M/M ...<|control11|><|separator|>
[25]
[PDF] 5 Examples of M/M/1 type models - No home page
where λ is the arrival rate and µ the service rate (with λ < µ). The corresponding transition-rate diagram of the M/M/1 model is shown in figure 1.
[26]
[PDF] 1 Continuous-Time Markov Chains
The embedded Markov chain for a FIFO M/M/1 queue is a simple ran- dom walk ... where Q = P0(0) is the transition rate matrix from Section 1.10. From ...
[27]
[PDF] 4 The M/M/1 queue - No home page
The exponential distribution allows for a very simple description of the state of the system at time t, namely the number of customers in the system (i.e. the ...
[28]
[PDF] Control of M/M/1 queues
Individual nodes behave as if they are M/M/1 queues with rate and service time per visit is . Control of M/M/1 queues: Recall uniformization of a CTMC j k i.