Finite generator master equations and uniformization

Let $S=\{0,1,\dots ,n-1\}$ with $n\ge 1$. Identify its real matrices with $M_n(\mathbb{R})$, the finite matrix space with row and column indices in $S$ from The vector space $M_{m\times n}(F):=F^{m\times n}$ of $m$ by $n$ matrices over a field, with entrywise operations, and use the matrix-product and identity conventions of Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes. A finite column generator on $S$ is a real matrix $Q=(q_{ij})\in M_n(\mathbb{R})$ satisfying

$q_{ij}\ge 0(i\mathrm{\ne }j),{\sum }_{i<n}{q}_{ij}=0(j<n)\mathrm{.}$

The column index $j$ is the source state and the row index $i$ is the destination state: for $i\mathrm{\ne }j$, $q_{ij}$ is the transition rate from $j$ to $i$. The exit rate from $j$ is

$r_j:=-q_{jj}={\sum }_{i\mathrm{\ne }j}{q}_{ij}\ge 0.$

A column probability vector is $p\in {\mathbb{R}}^n$ with $p_i\ge 0$ for each $i$ and ${\sum }_{i<n}{p}_i=1$. A subprobability vector has the same coordinatewise nonnegativity and has coordinate sum at most one. These conventions are used throughout this page.

For a finite real square matrix $A$, define

$e^{tA}:={\sum }_{k=0}^{\mathrm{\infty }}\frac{t^k{A}^k}{k!}\mathrm{.}$

This series converges absolutely and uniformly for $t$ in every bounded interval. It is differentiable with $\frac{d}{dt}{e}^{tA}=A{e}^{tA}=e^{tA}A$ and $e^{0A}=I$. If finite square matrices $A$ and $B$ commute, then $e^A{e}^B=e^{A+B}$.

For $N\sim \mathrm{Pois}(\mu )$ with $\mu \ge 0$ and integer $K\ge 0$, write ${\tau }_K(\mu ):=\mathbb{P}(N>K)$. If $\mu =0$, then ${\tau }_K(\mu )=0$. If $\mu >0$ and $\mu <K+2$, then

${\tau }_K(\mu )\le \frac{e^{-\mu }{\mu }^{K+1}}{(K+1)!(1-\mu \mathrm{/}(K+2))}\mathrm{.}$

The right side is a geometric majorant computed from a Poisson mass, not a floating-point subtraction of a rounded partial sum from one.

Let $S$ be a nonempty at most countable state space, and let $q(x,y)\ge 0$ be a finite transition rate for each pair $x,y\in S$ with $x\mathrm{\ne }y$. For a nonnegative family indexed by an at most countable set, its sum is the supremum of its finite subsums, including the empty subsum $0$; if these subsums are unbounded, the sum is $+\mathrm{\infty }$. Require the total exit rate

$\lambda (x):={\sum }_{y\mathrm{\ne }x}q(x,y)$

to be finite for every $x$. The associated column rate matrix convention is $Q_{yx}=q(x,y)$ for $y\mathrm{\ne }x$ and $Q_{xx}=-\lambda (x)$; thus the source state indexes the column. No finite-dimensional matrix is asserted for an infinite $S$.

A given time-homogeneous pure-jump Markov chain with rates $q$ is a process $X=(X_t{)}_{t\ge 0}$ with values in $S$ whose conditional future law given its history depends only on its present state and elapsed time, and whose paths are constant between successive jumps. Its transition kernels $K_t$ depend only on elapsed time, satisfy $K_0=I$, and obey $K_{s+t}=K_s{K}_t$ using the composition $(K_s{K}_t)(x,A):={\int }_S{K}_t(z,A)K_s(x,dz)$ of Composition of probability kernels. At state $x$ with $\lambda (x)>0$, its holding time has survival $e^{-\lambda (x)t}$ and its next state is $y\mathrm{\ne }x$ with probability $q(x,y)\mathrm{/}\lambda (x)$, independently of that holding time; at $\lambda (x)=0$ it stays at $x$. It is nonexplosive when almost surely it has only finitely many state changes on every bounded time interval.

The chain and nonexplosion are input hypotheses in this item and in the projection results below. This definition does not construct a chain from an arbitrary countable rate matrix and proves no general nonexplosion claim.

Let $S$ be at most countable. For nonnegative functions $a,b:S\to [0,\mathrm{\infty })$ with finite total masses, define

$\mathrm{\parallel }a-b{\mathrm{\parallel }}_{{\mathrm{\ell }}^1(S)}:={\sum }_{x\in S}\mathrm{\mid }a(x)-b(x)\mathrm{\mid }\mathrm{.}$

For a nonnegative family, ${\sum }_{x\in S}$ means the supremum of its finite subsums; this agrees with the ordinary series under any enumeration of $S$. The distance is finite because $\mathrm{\mid }a(x)-b(x)\mathrm{\mid }\le a(x)+b(x)$ termwise, so $\mathrm{\parallel }a-b{\mathrm{\parallel }}_{{\mathrm{\ell }}^1(S)}\le {\sum }_{x}a(x)+{\sum }_{x}b(x)$. In particular it is defined for probability and subprobability mass functions.

Let $Q$ be a finite column generator and let $\nu \ge {\max }_{j<n}{r}_j$. If $\nu >0$, then

$P:=I+Q\mathrm{/}\nu$

has nonnegative entries and every column sums to one. If $\nu =0$, then $Q=0$.

Let $X$ be a given nonexplosive chain as in Given countable nonexplosive pure-jump chain with finite rates, with initial law $p_0$ on $S$, and let $F\subseteq S$ be finite and nonempty. Its first exit time from $F$ is

${\tau }_F:=\inf \{s\ge 0:X_s\mathrm{\notin }F\},$

with ${\tau }_F=0$ when $X_0\mathrm{\notin }F$. Adjoin a new state $†\mathrm{\notin }S$ and define the killed projection $Y_t=X_t$ for $t<{\tau }_F$ and $Y_t=†$ for $t\ge {\tau }_F$. The killed mass vector is $u_F(t,x):=\mathbb{P}(Y_t=x)$ for $x\in F$, and the cemetery mass is $c_F(t):=\mathbb{P}(Y_t=†)$. Initially, $u_F(0,x)=p_0(x)$ for $x\in F$ and $c_F(0)=p_0(S\setminus F)$.

For $x\in F$ let $\lambda (x)={\sum }_{y\mathrm{\ne }x}q(x,y)$. The killed principal subgenerator on $F$ has entries $(Q_F{)}_{yx}=q(x,y)$ for $y\mathrm{\ne }x$ in $F$ and $(Q_F{)}_{xx}=-\lambda (x)$; its column sum is $-{\sum }_{y\mathrm{\notin }F}q(x,y)$. The cemetery lift is the finite matrix ${\tilde{Q}}_F$ on $F\cup \{†\}$ with these same entries on $F$, with

${\tilde{Q}}_{†x}=\lambda (x)-{\sum }_{\begin{array}{c}y\in F\\ y\mathrm{\ne }x\end{array}}q(x,y)={\sum }_{y\mathrm{\notin }F}q(x,y)(x\in F),{\tilde{Q}}_{x†}=0(x\in F),{\tilde{Q}}_{††}=0.$

Every column of ${\tilde{Q}}_F$ sums to zero and its off-diagonal entries are nonnegative, so it is a finite column generator in the sense of Finite column generator. The cemetery state is absorbing; trajectories that return to $F$ after their first exit remain at $†$ in this projection.

Let $Q$ be an $n\times n$ finite column generator, let $p_0$ be a column probability vector, and let $t\ge 0$. The unique differentiable solution of

$p^{\mathrm{\prime }}(t)=Qp(t),p(0)=p_0,$

is $p(t)=e^{tQ}{p}_0$. If $\nu >0$ and $\nu \ge {\max }_j{r}_j$, put $P=I+Q\mathrm{/}\nu$; then

$p(t)={\sum }_{k=0}^{\mathrm{\infty }}{e}^{-\nu t}\frac{(\nu t{)}^k}{k!}{P}^k{p}_0\mathrm{.}$

Each term $P^k{p}_0$ is a probability vector, and the displayed Poisson mixture is a probability vector. If $\nu =0$, then $Q=0$ and $p(t)=p_0$.

Inputs. A finite column generator $Q$, a column probability vector $p_0$, $t\ge 0$, an admissible rate $\nu \ge {\max }_j{r}_j$, a positive tail budget $\epsilon$, a positive integer total-term cap $B$, and either exact real arithmetic or a validated arithmetic backend. In a rounded execution, the backend must certify the scalar control decisions defining $m$ and $\mu$, each finite tail-budget comparison, and an outward upper bound $T\ge m{G}_K(\mu )$; it must also return a certified ${\mathrm{\ell }}^1$ error bound $E_{\mathrm{a}\mathrm{l}\mathrm{g}}:=\mathrm{\parallel }\widehat{p}-R_{\mu ,K}^m{p}_0{\mathrm{\parallel }}_1$ for its computed vector. The vector bound includes any arithmetic error from the weights, time split, and matrix-free $P$ actions. If any scalar or vector certificate is unavailable, return certificate-unavailable.

Outputs. Return $(p_0,0,0)$ when $\nu =0$ or $t=0$. Otherwise return budget-exhausted or certificate-unavailable, or an approximate vector $\widehat{p}$ and certified bounds $(T,E_{\mathrm{a}\mathrm{l}\mathrm{g}})$ for which $\mathrm{\parallel }p(t)-\widehat{p}{\mathrm{\parallel }}_1\le T+E_{\mathrm{a}\mathrm{l}\mathrm{g}}$. Here $T\ge m{G}_K(\mu )$ is an outward-certified Poisson-tail upper bound and $E_{\mathrm{a}\mathrm{l}\mathrm{g}}$ bounds the arithmetic/algebraic error relative to the exact truncated accumulation. In exact real arithmetic, $T=m{G}_K(\mu )$ and $E_{\mathrm{a}\mathrm{l}\mathrm{g}}=0$.

Procedure. For $\nu t>0$, set $m=\lceil \nu t\rceil$ and $\mu =\nu t\mathrm{/}m$, so $0<\mu \le 1$. A rounded backend must certify these values and inequalities; if it cannot, return certificate-unavailable. If $m>B$, return budget-exhausted. Set $K_{\max }=\lfloor B\mathrm{/}m\rfloor -1$. Search the finite list $K=0,1,\dots ,K_{\max }$ for a member satisfying

$G_K(\mu ):=\frac{e^{-\mu }{\mu }^{K+1}}{(K+1)!(1-\mu \mathrm{/}(K+2))}\le \epsilon \mathrm{/}m\mathrm{.}$

In rounded arithmetic, accept a candidate only when a validated upper enclosure proves the displayed inequality, and set $T=\epsilon$, copying the already certified accepted tail budget. This is an exact bound because the accepted comparison certifies $m{G}_K(\mu )\le \epsilon$. If no candidate works, return budget-exhausted when the comparisons certify that every candidate fails, and certificate-unavailable when they do not decide the search. In exact arithmetic set $T=m{G}_K(\mu )$. Set $P=I+Q\mathrm{/}\nu$ and $x_0=p_0$. For each substep $j=1,\dots ,m$, initialize $v_0=x_{j-1}$, $w_0=e^{-\mu }$, and $x_j=w_0{v}_0$. For $k=0,\dots ,K-1$, update

$v_{k+1}=P{v}_k,w_{k+1}=w_k\frac{\mu }{k+1},x_j\leftarrow x_j+w_{k+1}{v}_{k+1}\mathrm{.}$

These $P$ actions use the exact operator-application interface of The matrix-free access model for Krylov methods: the routine supplies $v\mapsto Pv$ and vector additions and scalar multiples, without requiring stored matrix entries. No CSR representation, operation-count estimate, or convergence claim is part of this procedure. The exact term count is $m(K+1)\le B$ and the certified tail bound satisfies $T\le \epsilon$. Never replace a tail certificate by floating-point $1-{\sum }_{k\le K}{w}_k$.

Let $Q$ be a finite column generator, $p_0$ a column probability vector, and $\nu >0$ an admissible rate. For $\lambda =\nu t$ and $K\ge 0$, the exact one-series partial sum

$u_K(t):={\sum }_{k=0}^K{e}^{-\lambda }\frac{{\lambda }^k}{k!}{P}^k{p}_0$

is nonnegative and substochastic, and its exact ${\mathrm{\ell }}^1$ distance from $p(t)$ is the scalar Poisson tail ${\tau }_K(\lambda )=\mathbb{P}(\mathrm{Pois}(\lambda )>K)$. If $\nu t>0$, the budgeted algorithm sets $m=\lceil \nu t\rceil$ and $\mu =\nu t\mathrm{/}m\le 1$, and uses $R_{\mu ,K}={\sum }_{k=0}^K{e}^{-\mu }{\mu }^k{P}^k\mathrm{/}k!$. Then $R_{\mu ,K}^m{p}_0$ is nonnegative and substochastic, and its exact transient ${\mathrm{\ell }}^1$ error is

$1-{\left({\sum }_{k=0}^K{e}^{-\mu }\frac{{\mu }^k}{k!}\right)}^m\le m{\tau }_K(\mu )\le m{G}_K(\mu )\mathrm{.}$

If a computed vector $\widehat{u}$ has a separately certified accumulated arithmetic/algebraic error $E_{\mathrm{a}\mathrm{l}\mathrm{g}}:=\mathrm{\parallel }\widehat{u}-R_{\mu ,K}^m{p}_0{\mathrm{\parallel }}_1$, then $\mathrm{\parallel }p(t)-\widehat{u}{\mathrm{\parallel }}_1\le m{G}_K(\mu )+E_{\mathrm{a}\mathrm{l}\mathrm{g}}$. In rounded arithmetic, if $T$ is a validated upper bound for $m{G}_K(\mu )$, then $\mathrm{\parallel }p(t)-\widehat{u}{\mathrm{\parallel }}_1\le T+E_{\mathrm{a}\mathrm{l}\mathrm{g}}$. The geometric tail certificate is not obtained by floating-point subtraction from one.

Let $X_t$ be a given nonexplosive countable chain with rates $q(x,y)$, initial law $p_0$, and finite exit rates as in Given countable nonexplosive pure-jump chain with finite rates. For a finite nonempty $F\subseteq S$, let ${\tau }_F$ and $Y_t$ be the killed projection of Killed finite-state projection and cemetery lift. Write $p_t(x)=\mathbb{P}(X_t=x)$ and $u_F(t,x)=\mathbb{P}(Y_t=x)$ for $x\in F$. Then

$u_F(t,x)=\mathbb{P}(X_t=x,{\tau }_F>t)\le p_t(x),c_F(t)=\mathbb{P}({\tau }_F\le t)\mathrm{.}$

If ${\bar{u}}_F$ is $u_F$ extended by zero to $S\setminus F$, then

$\mathrm{\parallel }{p}_t-{\bar{u}}_F(t){\mathrm{\parallel }}_{{\mathrm{\ell }}^1(S)}=c_F(t)\mathrm{.}$

For any bounded real observable $f:S\to \mathbb{R}$, put $\mathrm{osc}(f):={\sup }_{x\in S}f(x)-{\inf }_{x\in S}f(x)$ and extend it to the cemetery state by $f(†):=(\sup f+\inf f)\mathrm{/}2$. The corresponding expectation error obeys

$\mathrm{\mid }\mathbb{E}[f(X_t)]-\mathbb{E}[f(Y_t)]\mathrm{\mid }\le \frac{1}{2}\mathrm{osc}(f)c_F(t)\mathrm{.}$

The finite cemetery lift ${\tilde{Q}}_F$ in Killed finite-state projection and cemetery lift is a finite generator and $\mathcal{L}(Y_t)=e^{t{\tilde{Q}}_F}\mathcal{L}(Y_0)$. A path that exits $F$ and later returns contributes to the full marginal but remains at the cemetery state in the killed projection.