Choosing the Uniformization Rate

What the Uniformization Rate Controls

Uniformization represents a continuous-time Markov chain using a Poisson event clock and a discrete-time transition matrix. The rate of that clock is a computational choice: it can be larger than the chain’s fastest exit rate. Increasing it creates more clock events, some of which leave the state unchanged. The key fact is that these extra self-transitions change the representation, not the chain’s transition probabilities.

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})\), with \(q_{ij}\ge0\) for \(i\ne j\) and rows summing to zero. Write \(q_i=-q_{ii}=\sum_{j\ne i}q_{ij}\) for the exit rate from \(i\), and \(q_{\max}=\max_{i\in S}q_i\). The transition matrix at time \(t\) is \(P(t)=e^{tQ}\).

The restriction \(\nu\ge q_{\max}\) makes every diagonal entry of \(R_\nu\) nonnegative. Its off-diagonal entries are also nonnegative, and each row sums to one because the corresponding row of \(Q\) sums to zero. Thus \(R_\nu\) is a valid row-stochastic matrix. The formula mixes its \(n\)-step transition matrices using the probabilities of a Poisson random variable with mean \(\nu t\).

Why Admissible Rates Preserve the Chain

Proof. For each row \(i\), the off-diagonal entries of \(R_\nu\) are \(q_{ij}/\nu\ge0\), and the row sum is \(1+\sum_jq_{ij}/\nu=1\). Its diagonal entry is \(1+q_{ii}/\nu=1-q_i/\nu\), which is nonnegative exactly when \(\nu\ge q_i\). Therefore all entries are nonnegative exactly when \(\nu\ge\max_iq_i=q_{\max}\), proving the first claim.

For an admissible rate, the matrix exponential series gives \(e^{tQ}=e^{-\nu t}e^{\nu tI+tQ}\), since \(I\) commutes with \(Q\). Since \(\nu tI+tQ=\nu tR_\nu\), expanding the exponential yields \(e^{tQ}=e^{-\nu t}\sum_{n=0}^{\infty}(\nu t)^nR_\nu^n/n!\). This series converges entrywise because it is a finite matrix exponential series. Its right side is the uniformization formula. The left side depends on \(Q,t\), not on \(\nu\), so every admissible choice gives the same transition matrix. \(\square\)

There is one degenerate case worth separating. If \(q_{\max}=0\), then every exit rate is zero and \(Q=0\); the chain stays at its initial state. Any \(\nu>0\) gives \(R_\nu=I\), so the formula still returns \(P(t)=I\). The value \(\nu=0\) is not an admissible uniformization rate because \(Q/\nu\) is undefined; the constant chain is handled directly.

Rate Choice and Computational Work

For a fixed time horizon \(t\), the number of uniformization events has a Poisson distribution with mean \(\nu t\). A direct evaluation of the series therefore uses matrix powers up to a truncation index appropriate for that Poisson mean. The smallest admissible rate is \(q_{\max}\) when \(q_{\max}>0\); it minimizes the mean event count among admissible choices. Larger rates remain mathematically valid, but they add self-transitions and generally increase the work of evaluating the mixture. The precise cost also depends on how the computation is implemented.

Proof. Let \(N_1\) and \(N_2\) be independent Poisson random variables with means \(\nu_1t\) and \((\nu_2-\nu_1)t\), respectively. Their sum has a Poisson distribution with mean \(\nu_2t\): for \(n\ge0\), its probability of equaling \(n\) is \(e^{-\nu_2t}\sum_{k=0}^n(\nu_1t)^k((\nu_2-\nu_1)t)^{n-k}/(k!(n-k)!) =e^{-\nu_2t}(\nu_2t)^n/n!\), by the binomial theorem. Under this coupling, \(N_1+N_2\ge N_1\) for every outcome, so the larger-rate count is at least the smaller-rate count. Their means are \(\nu_2t\) and \(\nu_1t\), respectively, which proves the expectation claim. For \(t=0\), both counts are zero and the claim still holds. \(\square\)

A Rate That Is Too Small

Common mistake. A rate below \(q_{\max}\) is not a more efficient uniformization rate: it can make the proposed matrix invalid. For the generator in the preceding example, the exit rates are both \(1\). If one tries \(\nu=\tfrac12\), then

Each row sums to one, but each has a negative entry, so this is not a transition matrix. The correction is to require \(\nu\ge q_{\max}=1\); for example, \(\nu=1\) gives \(R_1=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), with nonnegative entries and row sums equal to one. Row sums alone do not establish that a matrix is stochastic.

In practice, start by finding the largest exit rate. The smallest admissible rate avoids unnecessary virtual events, while a larger rate may still be chosen for a separate implementation reason. Whatever rate is selected, check nonnegativity and row sums, and remember that it changes the Poisson mixture and embedded self-transitions—not the CTMC transition matrix \(e^{tQ}\).