Rare-event reweighting, overlap and certified partition ratios

Let $\mathsf{X}$ be a finite nonempty set equipped with counting measure. For $a\in \{0,1\}$, let $w_a:\mathsf{X}\to (0,\mathrm{\infty })$ be a finite positive weight, define $Z_a={\sum }_{x\in \mathsf{X}}{w}_a(x)$, and define the probability mass function ${\pi }_a(x)=w_a(x)\mathrm{/}{Z}_a$. For an integer $n\ge 1$, let $X_1,\dots ,X_n$ be independent random variables with common law ${\pi }_0$. Define $R(x)=w_1(x)\mathrm{/}{w}_0(x)$, ${\widehat{r}}_n=n^{-1}{\sum }_{j=1}^{n}R(X_j)$, and ${\chi }^2({\pi }_1\mathrm{\parallel }{\pi }_0)={\sum }_{x\in \mathsf{X}}{\pi }_0(x)({\pi }_1(x)\mathrm{/}{\pi }_0(x)-1{)}^2$. Then

${\mathbb{E}}_{{\pi }_0}[{\widehat{r}}_n]=\frac{Z_1}{Z_0},\frac{{\mathrm{Var}}_{{\pi }_0}({\widehat{r}}_n)}{(Z_1\mathrm{/}{Z}_0{)}^2}=\frac{{\chi }^2({\pi }_1\mathrm{\parallel }{\pi }_0)}{n}\mathrm{.}$

The estimator uses only the finite raw-weight ratios $w_1(X_j)\mathrm{/}{w}_0(X_j)$; the partition sums define the target ratio and probability laws but are not inputs to its computation.

Ordinary importance sampling

Ordinary importance sampling has finite variance and a CLT under a weighted second moment

The proof uses the ordinary importance-sampling variance identity only after symbolically normalizing the target. It does not treat the ordinary importance-sampling algorithm, whose contract requires a known target normalizer, as a procedure for computing an unknown partition ratio.

Input a finite nonempty state space $\mathsf{X}$, an integer $K\ge 1$, positive finite weights $w_0,\dots ,w_K:\mathsf{X}\to (0,\mathrm{\infty })$, positive integers $n_0,\dots ,n_{K-1}$, and, on a common probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, supplied random variables $X_{k,j}:\mathrm{\Omega }\to (\mathsf{X},\mathcal{P}(\mathsf{X}))$ for $0\le k<K$ and $1\le j\le n_k$. For each $k$, set $Z_k={\sum }_{x\in \mathsf{X}}{w}_k(x)$ and ${\pi }_k(x)=w_k(x)\mathrm{/}{Z}_k$, a probability mass function on $\mathsf{X}$ and thus a probability measure on $\mathcal{P}(\mathsf{X})$. Require $\mathbb{P}(X_{k,j}=x)={\pi }_k(x)$ for every $x\in \mathsf{X}$ and require the entire finite family $(X_{k,j}{)}_{k,j}$ to be mutually independent. These exact draws are inputs, not outputs of this procedure; approximate Gibbs draws, correlated trajectories, and adaptively chosen bridges are outside its contract.

For each $k=0,\dots ,K-1$, compute ${\bar{R}}_k=n_k^{-1}{\sum }_{j=1}^{n_k}{w}_{k+1}(X_{k,j})\mathrm{/}{w}_k(X_{k,j})$. Return $\widehat{R}={\prod }_{k=0}^{K-1}{\bar{R}}_k$. The procedure evaluates only raw-weight ratios; it neither computes nor requires any $Z_k$ as a numeric input.

Finite partition-ratio estimator and overlap variance

Let $\mathsf{X}$ be a finite nonempty set, let $K\ge 1$, and let $w_0,\dots ,w_K:\mathsf{X}\to (0,\mathrm{\infty })$ be finite positive weights. For each $k$, set $Z_k={\sum }_{x\in \mathsf{X}}{w}_k(x)$ and ${\pi }_k(x)=w_k(x)\mathrm{/}{Z}_k$. For strictly positive probability mass functions $\nu ,\mu :\mathsf{T}\to (0,1]$ on any finite nonempty set $\mathsf{T}$ (so ${\sum }_{x\in \mathsf{T}}\nu (x)={\sum }_{x\in \mathsf{T}}\mu (x)=1$), define ${\chi }^2(\nu \mathrm{\parallel }\mu )={\sum }_{x\in \mathsf{T}}\mu (x)(\nu (x)\mathrm{/}\mu (x)-1{)}^2$. On a common probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, let $X_{k,j}:\mathrm{\Omega }\to (\mathsf{X},\mathcal{P}(\mathsf{X}))$ for $0\le k<K$ and $1\le j\le n_k$ be mutually independent random variables with $\mathbb{P}(X_{k,j}=x)={\pi }_k(x)$ for each $x\in \mathsf{X}$, where $n_k\ge 1$; these are the supplied stage samples in alg-csm-frontier-independent-bridge-ratios. Then

$\mathbb{E}[\widehat{R}]=\frac{Z_K}{Z_0},\frac{\mathbb{E}[{\widehat{R}}^2]}{(Z_K\mathrm{/}{Z}_0{)}^2}={\prod }_{k=0}^{K-1}(1+\frac{{\chi }^2({\pi }_{k+1}\mathrm{\parallel }{\pi }_k)}{n_k})\mathrm{.}$

Consequently, $\mathrm{Var}(\widehat{R})\mathrm{/}(Z_K\mathrm{/}{Z}_0{)}^2$ is the displayed product minus $1$. This is an exact finite-sample result under independent exact draws; it gives no claim for reused trajectories, approximate Gibbs draws, or adaptively selected bridges.

Independent finite bridge-ratio estimator

Finite partition-ratio estimator and overlap variance

Input a finite nonempty set $\mathsf{X}$ with an explicit enumeration $(x_1,\dots ,x_m)$ listing each element exactly once, functions $w:\mathsf{X}\to (0,\mathrm{\infty })$ and $f:\mathsf{X}\to \mathbb{R}$, and, for each $x\in \mathsf{X}$, rational numbers $a_x\le b_x$ and $c_x\le d_x$ such that $w(x)\in W_x:=[a_x,b_x]$ and $f(x)\in F_x:=[c_x,d_x]$. Here a closed rational input interval $[a,b]$ means $a,b\in \mathbb{Q}$ and $a\le b$; its endpoints need not be dyadic, so before conversion it is distinct from the finite-dyadic real interval defined in def-intervals-rectangles-and-complex-balls. Choose a finite dyadic format $\mathbb{F}$ as in def-dyadic-floating-point-format-and-directed-rounding, with its directed roundings. The interval assertions are certified input premises; this procedure does not derive them from energies or evaluate an exponential or logarithm.

For $i=1,\dots ,m$ in increasing order, convert $W_{x_i}$ and then $F_{x_i}$ by rounding each lower rational endpoint down and each upper rational endpoint up into $\mathbb{F}$; denote the converted intervals by ${\widehat{W}}_i$ and ${\widehat{F}}_i$. If any conversion overflows, return unresolved-overflow and no finite enclosure claim. Initialize ${\mathcal{Z}}_0={\mathcal{N}}_0=[0,0]$. For $i=1,\dots ,m$ in increasing order, compute the following three operations in the displayed order:

${\mathcal{P}}_i={\widehat{W}}_i{\widehat{F}}_i,{\mathcal{Z}}_i={\mathcal{Z}}_{i-1}+{\widehat{W}}_i,{\mathcal{N}}_i={\mathcal{N}}_{i-1}+{\mathcal{P}}_i\mathrm{.}$

These recurrences fix the finite expression DAG: both sums are accumulated from left to right in the supplied enumeration, with rounding after each displayed operation and no reassociation. On completing the loop, set $\mathcal{Z}={\mathcal{Z}}_m$ and $\mathcal{N}={\mathcal{N}}_m$.

Every addition and multiplication uses the outward-rounded interval operations; division is used only for a denominator interval excluding zero. If any operation returns a non-finite status, return unresolved-operation and no finite enclosure claim. Otherwise return the finite intervals $\mathcal{Z}$ and $\mathcal{N}$. If the lower endpoint of $\mathcal{Z}$ is strictly positive, also return the outward interval quotient $\mathcal{E}=\mathcal{N}\mathrm{/}\mathcal{Z}$; if that endpoint is nonpositive, return unresolved-denominator and no normalized-expectation enclosure.

This is finite enumeration and can require exponentially many operations in the model size. It certifies arithmetic from supplied weight intervals; it does not certify how those intervals were obtained.

Dyadic floating-point format and directed rounding

Real intervals, complex rectangles and ball enclosures

Outward-rounded interval, rectangle and ball operations

Directed dyadic rounding encloses with explicit underflow and overflow bounds

Finite real interval operations enclose their exact values

Let $\mathsf{X}$ be finite and nonempty, let $w:\mathsf{X}\to (0,\mathrm{\infty })$ be an exact finite positive weight, and let $f:\mathsf{X}\to \mathbb{R}$ be a finite observable. Suppose the finite rational input intervals in the definition of alg-csm-frontier-interval-finite-partition contain every exact $w(x)$ and $f(x)$. The algorithm terminates after finitely many operations. If it returns finite intervals $\mathcal{Z}$ and $\mathcal{N}$, then they contain $Z={\sum }_{x\in \mathsf{X}}w(x)$ and $N={\sum }_{x\in \mathsf{X}}w(x)f(x)$, respectively. If it also returns an expectation interval $\mathcal{E}$, then its denominator interval has positive lower endpoint and $\mathcal{E}$ contains the exact normalized expectation ${\sum }_x\pi (x)f(x)=N\mathrm{/}Z$, where $\pi (x)=w(x)\mathrm{/}Z$. An overflow, non-finite operation, or nonpositive denominator lower endpoint produces an unresolved status and carries no normalized-expectation enclosure claim.

Certified finite partition and expectation enclosure

Dyadic floating-point format and directed rounding

Real intervals, complex rectangles and ball enclosures

Outward-rounded interval, rectangle and ball operations

Directed dyadic rounding encloses with explicit underflow and overflow bounds

Finite real interval operations enclose their exact values