From a Generator to a Discrete-Time Matrix
Uniformization expresses the transition probabilities of a continuous-time Markov chain as a weighted sum of powers of one discrete-time transition matrix. The weights are Poisson probabilities; the matrices describe the chain after a specified number of potential transitions. Here the main task is to prove that this series gives the same transition semigroup as the generator, and to identify precisely why the rate bound matters.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_t)_{t\ge0}\) be a time-homogeneous continuous-time Markov chain with finite state space \(S\). Its generator is \(Q=(q_{ij})\): for \(i\ne j\), \(q_{ij}\ge0\), and each row sums to zero. The exit rate from \(i\) is \(q_i=-q_{ii}=\sum_{j\ne i}q_{ij}\). Write \(P(t)=(p_{ij}(t))\) for its transition matrix, where \(p_{ij}(t)=\mathbb{P}(X_t=j\mid X_0=i)\). In this finite-state setting, the forward Kolmogorov equation is \(P'(t)=P(t)Q\), with \(P(0)=I\).
The rate condition is chosen so that \(R\) is a transition matrix. For \(i\ne j\), \(R_{ij}=q_{ij}/\nu\ge0\), and on the diagonal \(R_{ii}=1-q_i/\nu\ge0\). Its row sum at state \(i\) is \(1+\sum_jq_{ij}/\nu=1\). Thus every entry is nonnegative and every row sums to one. In particular, every power \(R^n\) is also row-stochastic, including \(R^0=I\).
Proof. The rate condition gives \(R=I+Q/\nu\), so \(Q=\nu(R-I)\). Since \(I\) commutes with \(R\), the matrix exponential identity \(e^{A+B}=e^Ae^B\) for commuting finite matrices gives $$ e^{tQ}=e^{\nu t(R-I)}=e^{-\nu tI}e^{\nu tR} =e^{-\nu t}\sum_{n=0}^{\infty}\frac{(\nu t)^n}{n!}R^n. $$ The exponential series converges absolutely in any matrix norm in finite dimensions, so this expansion is well-defined. To identify it with the transition matrix, let \(E(t)=e^{tQ}\). Differentiating its power series gives \(E'(t)=E(t)Q\) and \(E(0)=I\). The transition matrix satisfies the same forward equation and initial condition. For uniqueness, if \(D(t)\) is the difference of two solutions, then \(D'(t)=D(t)Q\) and \(D(0)=0\). Differentiating \(D(t)e^{-tQ}\) gives \(D(t)Qe^{-tQ}-D(t)Qe^{-tQ}=0\). Hence \(D(t)e^{-tQ}\) is constant and equals zero at \(t=0\); multiplying by \(e^{tQ}\) yields \(D(t)=0\). Therefore \(P(t)=E(t)\), which proves the formula. \(\square\)
The formula is also a mixture of stochastic matrices with nonnegative weights. For \(t\ge0\), the weights \(e^{-\nu t}(\nu t)^n/n!\) sum to one by the scalar exponential series. Since each \(R^n\) is row-stochastic, the formula makes \(P(t)\) row-stochastic as well. This gives a direct check on the probability interpretation, in addition to the generator-equation proof.
Worked Derivations
Worked Example: Two-State Switching
Consider \(S=\{1,2\}\), where the chain switches from either state to the other at rate \(2\). Its generator is $$ Q=\begin{bmatrix}-2&2\\2&-2\end{bmatrix}. $$ Both generator rows sum to \(-2+2=0\), and both exit rates equal \(2\). Choose \(\nu=2\), which meets the rate condition. Then $$ R=I+\frac{Q}{2} =\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Both rows of \(R\) sum to \(1\). Since \(R^2=I\), its powers alternate: \(R^{2k}=I\) and \(R^{2k+1}=R\) for each integer \(k\ge0\).
Separate the even and odd terms in the uniformization series. The diagonal entries receive the even terms and the off-diagonal entries receive the odd terms: $$ P(t)=e^{-2t} \begin{bmatrix} \displaystyle\sum_{k=0}^{\infty}\frac{(2t)^{2k}}{(2k)!} & \displaystyle\sum_{k=0}^{\infty}\frac{(2t)^{2k+1}}{(2k+1)!} \\[6pt] \displaystyle\sum_{k=0}^{\infty}\frac{(2t)^{2k+1}}{(2k+1)!} & \displaystyle\sum_{k=0}^{\infty}\frac{(2t)^{2k}}{(2k)!} \end{bmatrix} = \begin{bmatrix} \tfrac12(1+e^{-4t})&\tfrac12(1-e^{-4t})\\ \tfrac12(1-e^{-4t})&\tfrac12(1+e^{-4t}) \end{bmatrix}. $$ For the last equality, the even and odd sums are \(\cosh(2t)\) and \(\sinh(2t)\); multiplying by \(e^{-2t}\) gives the displayed expressions.
Check: Each row sums to \(\tfrac12(1+e^{-4t})+\tfrac12(1-e^{-4t})=1\). At \(t=0\), the matrix is \(I\). Differentiating its first row gives \((-2e^{-4t},\,2e^{-4t})\), which equals the first row of \(P(t)Q\): its entries are \(-2p_{11}(t)+2p_{12}(t)=-2e^{-4t}\) and \(2p_{11}(t)-2p_{12}(t)=2e^{-4t}\). The second row satisfies the same equation by symmetry.
Worked Example: Absorption with a Strictly Larger Uniformization Rate
Let \(S=\{1,2\}\), with state \(2\) absorbing and a transition from state \(1\) to state \(2\) at rate \(3\). Thus $$ Q=\begin{bmatrix}-3&3\\0&0\end{bmatrix}. $$ The generator row sums are \(-3+3=0\) and \(0+0=0\); the exit rates are \(3\) and \(0\). Choose \(\nu=4\), which is strictly larger than the maximum exit rate. Then $$ R=I+\frac{Q}{4} =\begin{bmatrix}\tfrac14&\tfrac34\\0&1\end{bmatrix}. $$ The row sums are \(\tfrac14+\tfrac34=1\) and \(0+1=1\).
After \(n\) steps of \(R\), the probability of still being in state \(1\), starting from state \(1\), is \((1/4)^n\): each step must remain in state \(1\), with probability \(1/4\). The remaining probability is in state \(2\). Starting from state \(2\), the chain stays there. Therefore $$ (R^n)_{11}=(\tfrac14)^n,\qquad (R^n)_{12}=1-(\tfrac14)^n,\qquad (R^n)_{21}=0,\qquad (R^n)_{22}=1. $$ Substituting these entries into the series gives $$ p_{11}(t)=e^{-4t}\sum_{n=0}^{\infty}\frac{(4t)^n}{n!}(\tfrac14)^n =e^{-4t}\sum_{n=0}^{\infty}\frac{t^n}{n!}=e^{-3t}. $$ The other entries follow from the same series and the row sums: $$ P(t)=\begin{bmatrix}e^{-3t}&1-e^{-3t}\\0&1\end{bmatrix}. $$
Check: The rows sum to \(e^{-3t}+1-e^{-3t}=1\) and \(0+1=1\). At \(t=0\), \(P(0)=I\). The first row of \(P'(t)\) is \((-3e^{-3t},3e^{-3t})\). Multiplying the first row of \(P(t)\) by \(Q\) gives \((-3e^{-3t},3e^{-3t})\), as required; the second row is zero under both operations.
Worked Example: Two Sequential Transitions
Let \(S=\{1,2,3\}\), with transitions \(1\to2\) and \(2\to3\), each at rate \(1\), and with state \(3\) absorbing. Then $$ Q=\begin{bmatrix}-1&1&0\\0&-1&1\\0&0&0\end{bmatrix}. $$ Each row sums to zero, and the exit rates are \(1,1,0\). Choose \(\nu=1\). The resulting matrix is $$ R=I+Q=\begin{bmatrix}0&1&0\\0&0&1\\0&0&1\end{bmatrix}. $$ Its row sums are \(1,1,1\). The first three powers needed to track the changing rows are $$ R^0=I,\qquad R^1=\begin{bmatrix}0&1&0\\0&0&1\\0&0&1\end{bmatrix},\qquad R^2=\begin{bmatrix}0&0&1\\0&0&1\\0&0&1\end{bmatrix}. $$ Multiplication gives \(R^n=R^2\) for every \(n\ge2\).
Consequently, the first row of the series has contributions to state \(1\) only from \(n=0\), to state \(2\) only from \(n=1\), and to state \(3\) from every \(n\ge2\). The second row contributes to state \(2\) only from \(n=0\), and to state \(3\) from \(n\ge1\). Summing those terms gives $$ P(t)= \begin{bmatrix} e^{-t}&te^{-t}&1-(1+t)e^{-t}\\ 0&e^{-t}&1-e^{-t}\\ 0&0&1 \end{bmatrix}. $$
Check: The first row sums to \(e^{-t}+te^{-t}+1-(1+t)e^{-t}=1\); the second sums to \(e^{-t}+1-e^{-t}=1\); the third sums to \(1\). At \(t=0\), the result is \(I\). Differentiating the first row gives \((-e^{-t},(1-t)e^{-t},te^{-t})\). Multiplying that row of \(P(t)\) by \(Q\) gives \((-e^{-t},e^{-t}-te^{-t},te^{-t})\), the same vector. The second row derivative is \((0,-e^{-t},e^{-t})\), also equal to the second row of \(P(t)Q\); the third row is constant and its product with \(Q\) is zero.
Why the Rate Bound Cannot Be Dropped
The condition \(\nu\ge\max_iq_i\) is not a technical convenience: it ensures that the diagonal entries of \(R\) are nonnegative. For example, take the valid two-state generator $$ Q=\begin{bmatrix}-3&3\\1&-1\end{bmatrix}. $$ Its row sums are zero and its exit rates are \(3\) and \(1\). If one incorrectly chooses \(\nu=2\), then $$ I+\frac{Q}{2}=\begin{bmatrix}-\tfrac12&\tfrac32\\\tfrac12&\tfrac12\end{bmatrix}. $$ Both rows still sum to \(1\), but the first matrix entry is negative, so this is not a transition matrix. The weighted terms in the proposed series are then not a mixture of transition matrices. Choosing \(\nu=3\), for instance, gives \(R=\begin{bmatrix}0&1\\\tfrac13&\tfrac23\end{bmatrix}\), whose entries are nonnegative and whose rows sum to \(1\).
A related algebraic mistake is to omit the factor \(e^{-\nu t}\). The powers \(R^n\) are stochastic, but their coefficients \((\nu t)^n/n!\) alone do not sum to one; their sum is \(e^{\nu t}\). The factor \(e^{-\nu t}\) normalizes the weights. The formula also applies to any admissible \(\nu\), not only to the largest exit rate: in the absorbing example, using \(\nu=4\) produced the same transition probabilities as the generator with exit rate \(3\).
Uniformization matters because it replaces a continuous-time transition calculation with powers of a single stochastic matrix, combined with explicit scalar weights. The proof shows that this is exact, not an approximation: the series is the matrix exponential of \(tQ\), and therefore it satisfies the transition equations and initial condition. The stochastic-matrix form also makes row sums and nonnegativity transparent under the stated rate condition.
Check Your Understanding
Use the generator-to-matrix construction and verify each calculation before applying the series.
- For \(Q=\begin{bmatrix}-2&2\\1&-1\end{bmatrix}\), check the row sums and exit rates. Is \(\nu=2\) admissible, and what is \(R\)?
- Explain why the powers \(R^n\) are row-stochastic whenever \(R\) is row-stochastic.
- For the two-state switching example, verify directly that the two entries in each row of \(P(t)\) sum to \(1\).
- In the absorbing example, why does the \((1,1)\) entry of \(R^n\) equal \((1/4)^n\)?
- What fails in the uniformization interpretation if some diagonal entry of \(I+Q/\nu\) is negative?