Hubbry Logo
Transition-rate matrixTransition-rate matrixMain
Open search
Transition-rate matrix
Community hub
Transition-rate matrix
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Transition-rate matrix
Transition-rate matrix
Transition-rate matrix
View on Wikipedia
from Wikipedia

In probability theory, a transition-rate matrix (also known as a Q-matrix,[1] intensity matrix,[2] or infinitesimal generator matrix[3]) is an array of numbers describing the instantaneous rate at which a continuous-time Markov chain transitions between states.

In a transition-rate matrix (sometimes written [4]), element (for ) denotes the rate departing from and arriving in state . The rates , and the diagonal elements are defined such that

,

and therefore the rows of the matrix sum to zero.

Up to a global sign, a large class of examples of such matrices is provided by the Laplacian of a directed, weighted graph. The vertices of the graph correspond to the Markov chain's states.

Properties

[edit]

The transition-rate matrix has following properties:[5]

  • There is at least one eigenvector with a vanishing eigenvalue, exactly one if the graph of is strongly connected.
  • All other eigenvalues fulfill .
  • All eigenvectors with a non-zero eigenvalue fulfill .
  • The Transition-rate matrix satisfies the relation where P(t) is the continuous stochastic matrix.

Example

[edit]

An M/M/1 queue, a model which counts the number of jobs in a queueing system with arrivals at rate λ and services at rate μ, has transition-rate matrix

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Transition-rate matrix

View on Grokipedia
from Grokipedia
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 (CTMC), a where the time spent in each state follows an and transitions depend only on the current state. In this matrix Q=(qij)Q = (q_{ij}), the off-diagonal entries qijq_{ij} for i≠ji \neq j represent the rate of transition from state ii to state jj, while the diagonal entries satisfy qii=−∑j≠iqijq_{ii} = -\sum_{j \neq i} q_{ij}, indicating the total rate of departure from state ii. 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. It plays a central role in modeling the dynamics of CTMCs by governing the evolution of the transition probability matrix P(t)P(t), which satisfies the Kolmogorov backward equations P′(t)=QP(t)P'(t) = Q P(t) (or the forward equations P′(t)=P(t)QP'(t) = P(t) Q, depending on the convention), with the explicit solution P(t)=etQP(t) = e^{tQ}. 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. Transition-rate matrices are essential in applications such as , reliability analysis, , and , where they enable the computation of steady-state distributions via balance equations πQ=0\pi Q = 0 (with ∑πi=1\sum \pi_i = 1) for ergodic chains. 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. Unlike the transition probability matrix in discrete-time Markov chains, the Q-matrix captures rates rather than probabilities, allowing for arbitrary transition times.

Definition and Basics

Formal Definition

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

Context in Continuous-Time Markov Chains

A (CTMC) is defined as a {X(t):t≥0}\{X(t): t \geq 0\} with a countable state space SS, where the holds: for all t,s≥0t, s \geq 0 and states i,j∈Si, j \in S, the P(X(t+s)=j∣X(t)=i,{X(u):u≤t})P(X(t+s) = j \mid X(t) = i, \{X(u): u \leq t\}) equals P(X(t+s)=j∣X(t)=i)P(X(t+s) = j \mid X(t) = i). This property ensures that the future evolution depends only on the current state, independent of the history prior to time tt. 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 parameterized by rates −qii-q_{ii}, where qiiq_{ii} are the diagonal elements of the transition-rate matrix QQ. The matrix QQ thus governs both the embedded jump chain—a capturing the sequence of states visited—and the exponential holding times that determine the timing of jumps. CTMCs typically assume a finite or countable state space SS, enabling analytical tractability for properties like steady-state distributions. 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. 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 through his development of analytic methods for Markov processes.

Mathematical Properties

Matrix Structure and Constraints

The transition-rate matrix, often denoted as Q=(qij)Q = (q_{ij}), is structured such that its off-diagonal elements qijq_{ij} for i≠ji \neq j are non-negative real numbers, representing the instantaneous rates at which the process transitions from state ii to state jj. These rates quantify the intensity of direct jumps between distinct states in a (CTMC). A strict inequality qij>0q_{ij} > 0 indicates that a direct transition from ii to jj is possible with positive probability, whereas qij=0q_{ij} = 0 implies no direct transition occurs, though indirect paths may still exist through other states. A fundamental constraint on the matrix arises from the conservation of probability, requiring that the sum of each row equals zero: ∑jqij=0\sum_{j} q_{ij} = 0 for every state ii. This condition ensures that the total probability mass remains preserved over time, as the rates of leaving and entering states balance exactly. Consequently, the diagonal elements are negative: qii=−∑j≠iqij<0q_{ii} = -\sum_{j \neq i} q_{ij} < 0 (unless the state is absorbing, in which case qii=0q_{ii} = 0), with the magnitude ∣qii∣|q_{ii}| interpreted as the total exit rate from state ii, or the inverse of the expected holding time in that state. The matrix is termed conservative if the row sums are exactly zero, upholding the stochastic nature of the embedded process without probability leakage. 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.

Eigenvalues and Eigenvectors

The transition-rate matrix QQ, 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 πQ=0\pi Q = 0 with ∑iπi=1\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 1\mathbf{1}, satisfying Q1=0Q \mathbf{1} = 0, a consequence of the row-sum zero property of QQ. All other eigenvalues λ\lambda of QQ satisfy Re⁡(λ)≤0\operatorname{Re}(\lambda) \leq 0, with strict inequality Re⁡(λ)<0\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 Re⁡(λ)≥2min⁡iqii\operatorname{Re}(\lambda) \geq 2 \min_i q_{ii}, where qii<0q_{ii} < 0 are the diagonal entries. For any eigenvector vv corresponding to a nonzero eigenvalue λ≠0\lambda \neq 0, the components sum to zero, i.e., ∑ivi=0\sum_i v_i = 0, since 1TQv=λ1Tv=0\mathbf{1}^T Q v = \lambda \mathbf{1}^T v = 0 implies 1Tv=0\mathbf{1}^T v = 0. 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 QQ is structurally akin to a weighted graph Laplacian, and in the context of random walks on undirected graphs, QQ is similar to −L-L, where LL is the Laplacian of the transition graph, facilitating spectral analysis via graph theory.

Formulation and Derivation

Relation to Transition Probability Matrix

The transition probability matrix P(t)P(t) for a continuous-time Markov chain is defined by its entries pij(t)=Pr⁡(X(t)=j∣X(0)=i)p_{ij}(t) = \Pr(X(t) = j \mid X(0) = i), where XX denotes the state process. This matrix satisfies the Chapman-Kolmogorov equations, P(t+s)=P(t)P(s)P(t + s) = P(t) P(s) for all t,s≥0t, s \geq 0, which express the semigroup property of the transition probabilities. The connection to the transition-rate matrix QQ arises through the Kolmogorov differential equations. The forward equation is given by ddtP(t)=P(t)Q\frac{d}{dt} P(t) = P(t) Q with initial condition P(0)=IP(0) = I, the identity matrix. The backward equation is ddtP(t)=QP(t)\frac{d}{dt} P(t) = Q P(t), also with P(0)=IP(0) = I. The unique solution to either equation is the matrix exponential P(t)=exp⁡(tQ)P(t) = \exp(t Q), which encodes the time evolution of the probabilities driven by the rates in QQ. The matrix P(t)P(t) inherits key properties from QQ: it is row-stochastic for all t≥0t \geq 0, meaning each row sums to 1, ensuring valid probabilities. Additionally, lim⁡t→0P(t)=I\lim_{t \to 0} P(t) = I, reflecting the initial state, and for ergodic chains (those irreducible and positive recurrent), lim⁡t→∞P(t)\lim_{t \to \infty} P(t) converges to the matrix with identical rows given by the stationary distribution. To compute exp⁡(tQ)\exp(t Q), one approach is the power series expansion exp⁡(tQ)=∑k=0∞(tQ)kk!\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 QQ (eigenvalues have nonpositive real parts). An alternative is the uniformization method, which approximates the continuous-time chain by a discrete-time chain with uniform jump rate λ=max⁡i(−qii)\lambda = \max_i (-q_{ii}). Here, define the discrete transition matrix P~=I+Q/λ\tilde{P} = I + Q / \lambda, and then P(t)=∑k=0∞e−λt(λt)kk!P~kP(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. This representation leverages discrete-time computations while preserving the exact solution when truncated appropriately.

Kolmogorov Equations

The Kolmogorov equations describe the time evolution of transition probabilities in continuous-time Markov chains governed by a transition-rate matrix QQ. 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)p(t), where pj(t)p_j(t) is the probability of being in state jj at time tt. It states that the rate of change of pj(t)p_j(t) is given by ddtpj(t)=∑ipi(t)qij,\frac{d}{dt} p_j(t) = \sum_{i} p_i(t) q_{ij}, where the sum is over all states ii, and qijq_{ij} are the entries of the transition-rate matrix QQ. In vector-matrix form, this becomes ddtp(t)=p(t)Q\frac{d}{dt} \mathbf{p}(t) = \mathbf{p}(t) Q. In physics and chemistry, this forward equation is recognized as the master equation, which balances the rate of change in the probability of state jj as the influx from other states minus the outflux from jj, reflecting conservation of probability under the process's stochastic jumps. The Kolmogorov backward equation addresses the evolution of individual transition probabilities pij(t)p_{ij}(t), the probability of transitioning from state ii to jj in time tt. It is expressed as ddtpij(t)=∑kqikpkj(t),\frac{d}{dt} p_{ij}(t) = \sum_{k} q_{ik} p_{kj}(t), with the matrix form QP(t)=ddtP(t)Q P(t) = \frac{d}{dt} P(t), where P(t)P(t) is the transition probability matrix. The initial conditions for these equations are p(0)\mathbf{p}(0) as the initial probability distribution and P(0)=IP(0) = I, the identity matrix, ensuring the process starts correctly. Under mild conditions on QQ, 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. The transition-rate matrix QQ 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 QQ (negative off-diagonal sums), capturing the continuous-time embedding of discrete transitions. The solution to these equations yields the transition probability matrix P(t)=exp⁡(tQ)P(t) = \exp(t Q).

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. Consider states labeled {0, 1}, where the transition-rate matrix QQ is given by Q=(−ααβ−β),Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}, with α>0\alpha > 0 and β>0\beta > 0 denoting the transition rates from state 0 to 1 and from 1 to 0, respectively. 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. The holding time in state 0 follows an with rate α\alpha, yielding a mean holding time of 1/α1/\alpha; similarly, the holding time in state 1 is exponential with rate β\beta and mean 1/β1/\beta. These holding times capture the duration spent in each state before a transition occurs, independent of prior history due to the . The transition probabilities pij(t)=Pr⁡(X(t)=j∣X(0)=i)p_{ij}(t) = \Pr(X(t) = j \mid X(0) = i) for this CTMC satisfy the Kolmogorov forward equations ddtP(t)=P(t)Q\frac{d}{dt} P(t) = P(t) Q, with P(0)=IP(0) = I, where P(t)=(pij(t))P(t) = (p_{ij}(t)). The solution is P(t)=exp⁡(tQ)P(t) = \exp(t Q), and for the two-state case, explicit forms can be obtained by solving the differential equations. In particular, p00(t)=β+αe−(α+β)tα+β,p_{00}(t) = \frac{\beta + \alpha e^{-(\alpha + \beta) t}}{\alpha + \beta}, derived by integrating the system starting from state 0. The other entries follow symmetrically: p01(t)=1−p00(t)p_{01}(t) = 1 - p_{00}(t), p10(t)=1−p11(t)p_{10}(t) = 1 - p_{11}(t), and p11(t)=α+βe−(α+β)tα+βp_{11}(t) = \frac{\alpha + \beta e^{-(\alpha + \beta) t}}{\alpha + \beta}. As t→∞t \to \infty, the chain converges to its π=(βα+β,αα+β)\pi = \left( \frac{\beta}{\alpha + \beta}, \frac{\alpha}{\alpha + \beta} \right), satisfying πQ=0\pi Q = 0 and ∑πi=1\sum \pi_i = 1, which balances the flow between states. This distribution represents the long-run proportion of time spent in each state. The eigenvalues of QQ are 0 and −(α+β)-(\alpha + \beta), with the zero eigenvalue corresponding to the stationary behavior. These allow explicit diagonalization: Q=PDP−1Q = P D P^{-1}, where D=diag⁡(0,−(α+β))D = \operatorname{diag}(0, -(\alpha + \beta)), leading to exp⁡(tQ)=Pexp⁡(tD)P−1\exp(t Q) = P \exp(t D) P^{-1}, which simplifies computation of P(t)P(t). The general eigenvalue properties of transition-rate matrices, such as non-positive real parts, underpin this decomposition. 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.

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}. 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. This model is a birth-death process, a special case of CTMC with transitions only to adjacent states. The transition-rate matrix Q for the M/M/1 queue is infinite-dimensional and tridiagonal, reflecting the birth-death structure. Specifically, the off-diagonal entries are for all i \geq 0 (representing arrival "births"), and for i \geq 1 (representing service completions or "deaths"). The diagonal elements are and for i \geq 1, ensuring the rows sum to zero as required for a rate matrix. 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. For steady-state analysis, the \pi satisfies \pi Q = 0 with \sum_{i=0}^\infty \pi_i = 1. Under the stability condition \rho = \lambda / \mu < 1, the solution is the \pi_i = (1 - \rho) \rho^i for i \geq 0. From this, key performance measures follow, such as the mean number of customers in the , L = \rho / (1 - \rho), obtained by summing i \pi_i over the states. Transient behavior in the M/M/1 queue, which tracks the time-dependent state probabilities, is analytically challenging due to the infinite state and requires solving the Kolmogorov forward equations. Exact solutions are rarely feasible, so approximations like uniformization are commonly employed, converting the CTMC to a with a uniform transition rate for computational tractability.

References

  1. http://www.columbia.edu/~ks20/stochastic-I/stochastic-I-CTMC.pdf
  2. https://galton.uchicago.edu/~lalley/Courses/312/ContinuousTime.pdf
  3. https://www.sjsu.edu/faculty/guangliang.chen/Math263/lec9ContinuousTimeMC.pdf
  4. https://www.probabilitycourse.com/chapter11/11_3_3_the_generator_matrix.php
  5. https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/16%253A_Markov_Processes/16.16%253A_Transition_Matrices_and_Generators_of_Continuous-Time_Chains
  6. https://www.sciencedirect.com/topics/mathematics/rate-matrix
  7. https://cape.fcfm.buap.mx/jdzf/cursos/procesos/libros/norris.pdf
  8. https://mathshistory.st-andrews.ac.uk/Biographies/Kolmogorov/
  9. https://u.math.biu.ac.il/~amirgi/CTMCnotes.pdf
  10. http://www.columbia.edu/~ww2040/6711F13/CTMCnotes120413.pdf
  11. https://www.cs.ucr.edu/~cshelton/papers/docs/ctmp-tut.pdf
  12. http://www.statslab.cam.ac.uk/~frank/PAPERS/qmatrix.pdf
  13. https://www.math.leidenuniv.nl/~spieksma/papers/Explosiveness.pdf
  14. https://d-nb.info/1262750423/34
  15. https://www.stat.berkeley.edu/~aldous/RWG/book.pdf
  16. https://www.randomservices.org/random/markov/Transition.html
  17. https://www.sciencedirect.com/book/9780444529657/stochastic-processes-in-physics-and-chemistry
  18. https://people.math.wisc.edu/~dfanderson/papers/SURVEY_AndKurtz.pdf
  19. https://web.stanford.edu/class/stat217/Chapter3.pdf
  20. https://www.seas.upenn.edu/~ese3030/block_3_continuous_time_markov_chains/slides/300_continuous_time_markov_chains.pdf
  21. https://www.math.ttu.edu/~anpeace/files/Math5355Papers/Chp5CTMC.pdf
  22. https://doi.org/10.1017/CBO9780511810633
  23. https://ocw.mit.edu/courses/2-854-introduction-to-manufacturing-systems-fall-2016/5d3e9532c2ff6e156d48e41f9bd9576f_MIT2_854F16_Queueing.pdf
  24. https://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Constantin.pdf
  25. https://dspace.mit.edu/bitstream/handle/1721.1/121170/6-436j-fall-2008/contents/lecture-notes/MIT6_436JF08_lec26.pdf
  26. http://www.cs.emory.edu/~cheung/Courses/MyInterests/QueueingTheory/IvoAdan/h5.pdf
  27. http://www.columbia.edu/~ks20/4106-18-Fall/Notes-CTMC.pdf
  28. http://www.cs.emory.edu/~cheung/Courses/MyInterests/QueueingTheory/IvoAdan/h4.pdf
  29. https://cyberlab.engr.uconn.edu/wp-content/uploads/sites/2576/2018/09/ECE6433_Lecture5_extra.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.