Poisson Tail Bounds for Uniformization

Truncation Error in Uniformization

Uniformization represents a continuous-time transition matrix as a Poisson-weighted sum of powers of a discrete-time transition matrix. In computation, that infinite sum must be cut off. The key fact is that the omitted terms have a direct probabilistic interpretation: their total weight is a Poisson upper-tail probability. This gives a computable error bound before any matrix powers are evaluated.

Let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with generator \(Q=(q_{ij})\). Choose a uniformization rate \(\nu>0\) at least as large as every exit rate \(q_i=-q_{ii}\), and let \(R=I+Q/\nu\). Thus \(R\) is row-stochastic: its entries are nonnegative and each row sums to \(1\). For \(t\ge0\), write \(m=\nu t\) and let \(N\) have a Poisson distribution with mean \(m\). The uniformization formula is \(P(t)=\sum_{n=0}^{\infty}w_nR^n\), where \(w_n=e^{-m}m^n/n!=\mathbb{P}(N=n)\). We use this formula, established in the earlier material on uniformization, under the condition that \(R\) is a well-defined stochastic transition matrix.

The approximation \(P_K(t)\) is generally substochastic rather than stochastic: some probability mass has been left out. This makes the error especially transparent. The following result gives several forms of the same bound.

Proof. Since \(R\) is row-stochastic, each power \(R^n\) is row-stochastic: multiplying two nonnegative matrices with row sums \(1\) again gives a nonnegative matrix with row sums \(1\). Therefore every term in the omitted sum \(\sum_{n=K+1}^{\infty}w_nR^n\) is entrywise nonnegative, and the sum of row \(i\) is \(\sum_{n=K+1}^{\infty}w_n=\varepsilon_K(m)\). A nonnegative entry in a row cannot exceed the sum of that row, proving the entrywise bound. For an initial distribution \(\mu\), the difference of the two row vectors is \(\sum_{n>K}w_n\mu R^n\), which is nonnegative coordinatewise. Each \(\mu R^n\) is a probability vector, so the coordinates of the difference sum to \(\sum_{n>K}w_n=\varepsilon_K(m)\). Its sum of absolute values is consequently \(\varepsilon_K(m)\), and half that sum is \(\varepsilon_K(m)/2\). If \(t=0\), then \(m=0\), all Poisson mass is at \(0\), and the same conclusions hold with zero omitted mass. \(\square\)

For a specified tolerance \(\epsilon>0\), it is therefore sufficient to choose \(K\) so that \(\mathbb{P}(N>K)\le\epsilon\). The exact tail can be evaluated from the Poisson probabilities, using \(w_0=e^{-m}\) and the recurrence \(w_{n+1}=w_n m/(n+1)\), then summing the probabilities beyond \(K\) or subtracting their cumulative sum from \(1\). For large \(m\), a proved exponential bound can be more convenient.

Proof. For any \(\theta>0\), the event \(N\ge r\) implies \(e^{\theta N}\ge e^{\theta r}\). Markov's inequality gives \(\mathbb{P}(N\ge r)\le e^{-\theta r}\mathbb{E}[e^{\theta N}]\). The Poisson probability formula yields \(\mathbb{E}[e^{\theta N}]=\sum_{n=0}^{\infty}e^{\theta n}e^{-m}m^n/n!=\exp(m(e^\theta-1))\). Choose \(\theta=\log(r/m)>0\), which is positive because \(r>m\). Substitution gives \(\exp(-r\log(r/m)+r-m)=e^{-m}(em/r)^r\). Taking \(r=K+1\) gives the truncation bound. \(\square\)

Choosing a Truncation Level

There are two practical choices. If computing Poisson probabilities is inexpensive, increase \(K\) until the exact omitted mass is at most the requested tolerance. This gives the smallest acceptable \(K\) for that exact-tail criterion. Alternatively, increase \(K\) until the exponential bound is below the tolerance. That condition is sufficient, but may choose a larger \(K\) than the exact tail requires. The exponential bound is stated only for \(K+1>m\); if that condition fails, it gives no guarantee, so use the exact tail or increase \(K\).

Reading the Bound in a Matrix Calculation

The Poisson tail controls the truncation error without depending on the entries of \(R\). The matrix still matters for computing the retained sum, but not for this error guarantee, provided \(R\) is stochastic. The next example displays both the truncated matrix and its exact row-sum deficit.

Common Pitfall: The Off-by-One Tail

A frequent mistake is to retain terms through \(K\) but bound the probability \(\mathbb{P}(N>K+1)\). That event omits one fewer Poisson term than the matrix truncation does. For example, when \(m=1\) and \(K=2\), the actual omitted mass is \(\mathbb{P}(N\ge3)\), not \(\mathbb{P}(N>3)\). The two values are

The first subtracts the retained probabilities for \(n=0,1,2\), whose sum is \(e^{-1}(1+1+\tfrac12)=5/(2e)\). The second subtracts probabilities through \(n=3\), adding \(e^{-1}/6\) to the retained sum. The difference is exactly \(\mathbb{P}(N=3)=1/(6e)\). For a truncation through \(K\), consistently use the omitted event \(N\ge K+1\), or equivalently \(N>K\).

In applications, choose the error criterion that matches the quantity being reported. The entrywise bound controls each transition probability separately. The full row-vector error bound controls the sum of absolute coordinate errors, while the conventionally defined total variation distance is half that amount. All of these follow from the same omitted Poisson mass; they are not interchangeable numerical tolerances.