Uniformization for Sparse Generators

Uniformization with Sparse Updates

For a finite-state continuous-time Markov chain, uniformization expresses the transition distribution at time \(t\) as a Poisson-weighted sum of discrete-time updates. When the generator is sparse, the key computational step is not to form powers of a transition matrix: it is to multiply a row vector by the matrix one sparse update at a time. This preserves the local structure of the generator and makes it possible to check probability mass throughout the computation.

Let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a finite state space \(S=\{1,\ldots,d\}\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its generator is \(Q=(q_{ij})\): for \(i\ne j\), \(q_{ij}\ge0\), and every row sums to zero. Write \(q_i=-q_{ii}=\sum_{j\ne i}q_{ij}\) for the exit rate from state \(i\). Suppose the initial distribution is the row vector \(\mu\), so that \(\mu_i=\mathbb{P}(X_0=i)\). We seek the row vector \(\mu(t)=\mu P(t)\), where \(P(t)=e^{tQ}\).

The choice \(\nu>0\) is required even if all exit rates are zero; in that case any positive \(\nu\) works and \(R=I\). For every allowed \(\nu\), the diagonal entry \(R_{ii}=1-q_i/\nu\) is nonnegative, and the off-diagonal entries are \(R_{ij}=q_{ij}/\nu\). The row sum is \(1-q_i/\nu+\sum_{j\ne i}q_{ij}/\nu=1\). The diagonal entries represent steps at which the discrete-time chain stays in its current state.

Here is the sparse calculation. Store the nonzero entries \(R_{ij}\), including any nonzero diagonal entries. Given a row vector \(\alpha_k\), initialize a zero row vector \(\alpha_{k+1}\), and for each nonzero \(R_{ij}\), add \(\alpha_k(i)R_{ij}\) to coordinate \(j\). Separately generate the weights using \(w_0=e^{-\theta}\) and \(w_{k+1}=w_k\theta/(k+1)\). This requires no dense matrix powers. If \(R\) has \(m\) nonzero entries, each vector update takes \(O(m)\) arithmetic operations, rather than the \(O(d^2)\) operations of a dense matrix-vector multiplication.

Why the Updates and Mass Checks Work

The two facts that support the algorithm are that each update remains a probability distribution and that omitting Poisson terms has a directly measurable mass cost. The first fact makes mass checks useful during implementation; the second makes truncation a controlled approximation rather than an unexplained loss of probability.

Proof. First, \(R\) is row-stochastic by the entry and row-sum calculation above. Since \(\alpha_0=\mu\) is a probability row vector, multiplication by \(R\) preserves nonnegativity and total mass: if \(\alpha_k\) is a probability row vector, then \((\alpha_kR)_j=\sum_i\alpha_k(i)R_{ij}\ge0\), and \(\sum_j(\alpha_kR)_j=\sum_i\alpha_k(i)\sum_jR_{ij}=\sum_i\alpha_k(i)=1\). Induction proves the claim for every \(k\).

For the evolution identity, \(Q=\nu(R-I)\), and \(R\) commutes with \(I\). The matrix exponential therefore factors as \(e^{tQ}=e^{-\nu t}e^{\nu tR}\). Expanding the second exponential in its convergent power series gives \(e^{tQ}=e^{-\nu t}\sum_{k=0}^{\infty}(\nu t)^kR^k/k!=\sum_{k=0}^{\infty}w_kR^k\). Multiplying on the left by \(\mu\) gives the asserted sum because \(\alpha_k=\mu R^k\), which follows by induction from the update rule. Finally, \(\widetilde{\mu}_K(t)\) has mass \(\sum_{k=0}^K w_k\), since each \(\alpha_k\) has mass one. The difference from the full sum is the nonnegative row vector \(\sum_{k>K}w_k\alpha_k\). Its \(L^1\) norm, defined as the sum of the absolute values of its coordinates, is its total mass, \(\sum_{k>K}w_k\sum_j\alpha_k(j)=\sum_{k>K}w_k\). \(\square\)

In particular, the truncated vector is generally a subprobability vector, not a probability vector. Its missing mass is exactly the omitted Poisson tail. To choose \(K\), use a Poisson tail bound or compute the tail to the desired tolerance. Do not silently interpret a small mass deficit as an error in the Markov-chain updates: the update vectors should each have mass one, while the truncated weighted sum should have mass equal to the included Poisson weights.

Worked Sparse Calculations

Implementation Checks and a Common Mistake

At every iteration, check that the update vector has nonnegative entries and sums to one, allowing for small floating-point roundoff in numerical implementations. Check separately that the accumulated truncated vector has mass equal to the sum of the weights included so far. These are different checks: normalizing the truncated vector to mass one conceals the omitted Poisson tail and changes the approximation.

Common mistake: using a column-vector update with a row-stochastic matrix. In the four-state cycle example, the initial row vector is \((1,0,0,0)\), and the correct update is \(\alpha_1=\alpha_0R=(0,1,0,0)\). If one instead applies \(R\) to the column vector \((1,0,0,0)^{\mathsf T}\), the result is \((0,0,0,\tfrac12)^{\mathsf T}\), which is not even a probability vector. The convention here is that distributions are row vectors and update by right multiplication. A separate common error is to renormalize a truncated sum: in the same example its mass at \(K=2\) is \(5/(2e)\), not one. That deficit is the exact omitted Poisson mass, not a failure of the individual sparse updates.

Uniformization is useful when the generator has few transitions out of each state, as in network models and large sparse state-space approximations. Its computational advantage depends on exploiting that sparsity in each update; explicitly forming \(R^k\) defeats that purpose. The mass identities also provide a practical diagnostic: an update vector whose mass differs materially from one indicates an indexing, orientation, or accumulation error, whereas a truncated sum has a predictable deficit determined by the Poisson weights.