From Continuous Time to Discrete Steps
A finite-state continuous-time Markov chain can change state at irregular times, which can make its transition probabilities harder to interpret or compute. Uniformization gives another viewpoint: imagine a Poisson clock that rings at a fixed rate, and let a discrete-time chain decide what happens at each ring. The discrete chain may stay in its current state at a ring. Those self-transitions are essential: they allow a single clock rate to represent states whose actual rates of leaving differ.
Let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its generator is \(Q=(q_{ij})\), where \(q_{ij}\ge0\) for \(i\ne j\) and \(\sum_{j\in S}q_{ij}=0\) for every \(i\). Write \(q_i=-q_{ii}=\sum_{j\ne i}q_{ij}\) for the rate of leaving state \(i\), and \(P(t)=e^{tQ}\) for the transition matrix at time \(t\).
The condition on \(\lambda\) guarantees nonnegative diagonal entries. The off-diagonal entries are \(r_{ij}=q_{ij}/\lambda\), so the chain uses the relative rates of the original process when it changes state. If \(\lambda=q_i\), it cannot stay in state \(i\) at a tick; if \(\lambda>q_i\), it does so with positive probability. When every \(q_i=0\), any \(\lambda>0\) is allowed and the uniformized chain stays in its state at every tick.
Each \(R^n\) describes the distribution after \(n\) steps of the uniformized chain. The formula averages those distributions over the random number of clock rings by time \(t\). A Poisson ring does not always correspond to a change of state: a self-transition uses one ring but leaves the state unchanged. Consequently, the number of rings is not generally the number of actual jumps.
Why the Discrete Matrix Is Valid
The stochasticity of \(R\) follows directly from the generator conditions. For each state \(i\), its off-diagonal entries are nonnegative, and its diagonal entry is nonnegative because \(q_i\le\lambda\). Its row sum is $$ \sum_j r_{ij}=\sum_j\left(\mathbf{1}_{\{i=j\}}+\frac{q_{ij}}{\lambda}\right)=1+\frac{1}{\lambda}\sum_jq_{ij}=1. $$ Thus \(R\) is a transition matrix. This check matters: the Poisson mixture combines probability distributions only when the matrices \(R^n\) are themselves stochastic.
The formula also makes the role of the rate condition visible. Since a Poisson distribution has nonnegative weights summing to one, a mixture of stochastic matrices is stochastic. For completeness, if \(R\) is row-stochastic, then \(R^n\) is row-stochastic for every integer \(n\ge0\): the identity matrix is stochastic, and if \(R^n\) is stochastic, then \(\sum_j(R^{n+1})_{ij}=\sum_k(R^n)_{ik}\sum_jr_{kj}=\sum_k(R^n)_{ik}=1\), with nonnegative entries. Therefore each partial mixture has nonnegative entries, and the full mixture has row sums one because the Poisson weights sum to one.
Worked Mixtures
Worked Example: An Absorbing Two-State Chain
Consider \(S=\{1,2\}\) and the generator $$ Q=\begin{bmatrix}-2&2\\0&0\end{bmatrix}. $$ The first row sums to \(-2+2=0\), the second to \(0+0=0\), and the exit rates are \(q_1=2\) and \(q_2=0\). Choose \(\lambda=2\). Then $$ R=I+\frac{Q}{2}=\begin{bmatrix}0&1\\0&1\end{bmatrix}. $$ Both rows sum to \(1\). State \(1\) moves to \(2\) at a ring, and state \(2\) stays at \(2\). Direct multiplication gives \(R^2=R\), so \(R^n=R\) for all \(n\ge1\).
The \(n=0\) term of the mixture is \(e^{-2t}I\). The sum of the weights for \(n\ge1\) is \(1-e^{-2t}\), since the full Poisson weight sum is \(1\) and the \(n=0\) weight is \(e^{-2t}\). Hence $$ P(t)=e^{-2t}I+(1-e^{-2t})R =\begin{bmatrix}e^{-2t}&1-e^{-2t}\\0&1\end{bmatrix}. $$ The first row sums to \(e^{-2t}+1-e^{-2t}=1\), and the second row sums to \(1\). At \(t=0\), this is \(I\); as \(t\) increases, the probability of remaining in state \(1\) is \(e^{-2t}\), as expected for a state with exit rate \(2\).
Worked Example: Self-Transitions at Clock Ticks
Take the two-state generator $$ Q=\begin{bmatrix}-1&1\\1&-1\end{bmatrix}. $$ Each row sums to zero, and both exit rates equal \(1\). Choose \(\lambda=2\), which is larger than either exit rate. The uniformized matrix is $$ R=I+\frac{Q}{2}=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac12&\tfrac12\end{bmatrix}. $$ Each row sums to \(\tfrac12+\tfrac12=1\). At each clock ring, either state is selected with probability \(\tfrac12\); in particular, the chain has probability \(\tfrac12\) of staying where it is. Multiplying the matrix by itself gives \(R^2=R\), so again \(R^n=R\) for \(n\ge1\).
Separate the zero-ring term from all positive-ring terms: $$ P(t)=e^{-2t}I+(1-e^{-2t})R =\begin{bmatrix} \tfrac{1+e^{-2t}}{2}&\tfrac{1-e^{-2t}}{2}\\ \tfrac{1-e^{-2t}}{2}&\tfrac{1+e^{-2t}}{2} \end{bmatrix}. $$ For example, the first row sums to \(\tfrac{1+e^{-2t}+1-e^{-2t}}{2}=1\). The self-transitions do not add extra movement to the original process; they let the rate-\(2\) clock include rings that leave the state unchanged. As a check at short times, differentiating the first off-diagonal entry at \(t=0\) gives \(\left.\frac{d}{dt}\tfrac{1-e^{-2t}}2\right|_{t=0}=1\), matching \(q_{12}=1\).
Worked Example: Truncating a Three-State Poisson Mixture
Let the chain move around the directed cycle \(1\to2\to3\to1\), with rate \(1\) at each state. Its generator and row checks are $$ Q=\begin{bmatrix}-1&1&0\\0&-1&1\\1&0&-1\end{bmatrix}, \qquad (-1+1,\ 0-1+1,\ 1+0-1)=(0,0,0). $$ Choose \(\lambda=1\). Then $$ R=I+Q=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}. $$ Every row sums to \(1\), and direct multiplication gives \(R^2=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}\) and \(R^3=I\).
At \(t=1\), the Poisson mean is \(\lambda t=1\). Keeping the terms for \(n=0,1,2,3\) gives $$ e^{-1}\left(I+R+\frac{1}{2}R^2+\frac{1}{6}R^3\right) =e^{-1}\begin{bmatrix}\tfrac76&1&\tfrac12\\\tfrac12&\tfrac76&1\\1&\tfrac12&\tfrac76\end{bmatrix}. $$ For the first row, the retained entries sum to \(e^{-1}(\tfrac76+1+\tfrac12)=\tfrac83e^{-1}\). The omitted Poisson weight is \(1-\tfrac83e^{-1}\), because the four retained weights are \(e^{-1}\), \(e^{-1}\), \(\tfrac12e^{-1}\), and \(\tfrac16e^{-1}\), whose sum is \(\tfrac83e^{-1}\). Since every omitted matrix \(R^n\) is stochastic, each entry of the omitted matrix contribution is between \(0\) and \(1-\tfrac83e^{-1}\). This gives a valid entrywise error bound without pretending the truncated matrix is the exact transition matrix.
Rate Choice and a Common Mistake
A larger allowable \(\lambda\) increases the frequency of clock ticks and usually increases the self-transition probabilities. The representation still describes the same continuous-time chain: extra ticks that leave the state unchanged do not constitute extra jumps of \(X_t\). For calculation, \(\lambda\) must satisfy \(\lambda\ge\max_iq_i\); choosing a smaller value can make a diagonal entry of \(R\) negative.
Common mistake: using \(Q/\lambda\) as the transition matrix. In the absorbing-chain example, \(Q/2=\begin{bmatrix}-1&1\\0&0\end{bmatrix}\). Its first row sums to \(0\), and its first diagonal entry is negative. It is not a transition matrix and cannot be used as the matrix of a discrete-time chain. The correction is to include the identity: \(R=I+Q/2=\begin{bmatrix}0&1\\0&1\end{bmatrix}\), whose rows sum to \(1\) and whose entries are nonnegative. The identity supplies the probability of no state change at a clock tick.
Uniformization is useful both conceptually and computationally. It replaces a continuous-time transition calculation by powers of one discrete transition matrix, weighted by a Poisson distribution. In exact examples the powers may simplify, as above. In numerical work, a finite number of terms can be calculated and the omitted Poisson probability used to control the remaining contribution. The stochasticity checks remain important in either setting: first check the generator rows, then check the uniformized rows, and only then form the mixture.
Check Your Understanding
Use the definitions and computations above to test whether you can set up and interpret a uniformization.
- For \(Q=\begin{bmatrix}-3&3\\0&0\end{bmatrix}\), choose \(\lambda=3\) and compute \(R\). Check both row sums.
- For the same generator, what fails if \(\lambda=2\)? Identify the entry of \(R\) that violates the transition-matrix conditions.
- In the symmetric two-state example, explain why a clock ring can occur without a change in the state of the original continuous-time chain.
- For the three-state cycle, write the \(n=0,1,2\) terms of the mixture at \(t=1\), and calculate their total Poisson weight.
- Explain why the omitted contribution in a truncated mixture has nonnegative entries and why its row sum equals the omitted Poisson probability.