Rare-event reweighting, overlap and certified partition ratios — Examples

Let $\mathsf{S}$ be a finite nonempty set and let $p_0,p_1:\mathsf{S}\to (0,1]$ be distinct strictly positive probability mass functions, so ${\sum }_{s\in \mathsf{S}}{p}_i(s)=1$ for $i=0,1$. 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$. For each integer $m\ge 1$, define ${\pi }_i^{(m)}:{\mathsf{S}}^m\to (0,1]$ by ${\pi }_i^{(m)}(x_1,\dots ,x_m):={\prod }_{j=1}^m{p}_i(x_j)$; these are the positive product probability mass functions. Then

$1+{\chi }^2({\pi }_1^{(m)}\mathrm{\parallel }{\pi }_0^{(m)})={(1+{\chi }^2(p_1\mathrm{\parallel }{p}_0))}^m\mathrm{.}$

On a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, let $X_1,\dots ,X_N:\mathrm{\Omega }\to ({\mathsf{S}}^m,\mathcal{P}({\mathsf{S}}^m))$ be independent random variables with common law ${\pi }_0^{(m)}$, where $N\ge 1$. Define the one-stage raw-ratio estimator $\widehat{r}=N^{-1}{\sum }_{j=1}^N{\pi }_1^{(m)}(X_j)\mathrm{/}{\pi }_0^{(m)}(X_j)$. Its relative variance is $((1+{\chi }^2(p_1\mathrm{\parallel }{p}_0){)}^m-1)\mathrm{/}N$. Since $p_0\mathrm{\ne }{p}_1$, keeping this relative variance at most a fixed $\epsilon >0$ requires $N\ge ((1+{\chi }^2(p_1\mathrm{\parallel }{p}_0){)}^m-1)\mathrm{/}\epsilon$, an exponential sample-size bound for this one-stage estimator.

Finite partition-ratio estimator and overlap variance