Fix a half-space $H = \{x\_1 \geq 0: ~ (x\_1,\dots,x\_n) \in \mathbb{R}^n\}$. Let $p$ be a distribution with support in $\mathbb{R}^n$. I am interested in the following way of estimating the weight $p(H) = \Pr\_{\mathbf{x} \sim p}\left[\mathbf{x} \in H\right]$ using random Voronoi partitions.


Take $m$ i.i.d. samples $\mathbf{c}^{(1)},\dots,\mathbf{c}^{(m)} \sim p$. Let $\mathcal{V}$ be the Voronoi partition induced by the centers $\mathbf{c}^{(1)},\dots,\mathbf{c}^{(m)}$. Namely, $\mathcal{V} = (V\_1,\dots,V\_m)$, where $V\_i \subseteq \mathbb{R}^n$ is the set of points that are closer in $\ell\_2$ distance to $\mathbf{c}^{(i)}$ than to any $\mathbf{c}^{(j)}$ for $j \neq i$ (with ties broken arbitrarily).


Consider the estimate $\hat{p}(H) = p\left(\bigcup\{V\_i: ~ \mathbf{c}^{(i)} \in H\} \right)$. In words, $\hat{p}(H)$ is the probability according to $p$ of all the Voronoi neighborhoods with centers in $H$.


**My Question:** is $\hat{p}(H)$ an unbiased estimator of $p(H)$? Namely, is it true that:
$$
\mathbb{E}\_{\mathbf{c}^{(1)},\dots,\mathbf{c}^{(m)} \sim p}\left[ \hat{p}(H) \right] = p(H)
$$



Approximating the probability of a half-space using random Voronoi diagrams
No. E.g., suppose that $n=1$, $m=2$, and the pdf $f$ of each of the $m=2$ iid sample points $X\_i:=\mathbf c^{(i)}$ ($i=1,\dots,m$) is given by the formula $f(x)=e^{-x-1}1(x>-1)$ for real $x$.
Then, by straightforward calculations,
$$p(H)=e^{-1}= 0.367\ldots\ne0.506\ldots=\frac{-2+6 e^2-8 e^3+6 e^4+e^6}{3 e^6}=E\hat p\_H.$$




---


Intuitively, the reason for this is clear: the Voronoi diagram is all about distances, whereas a distribution does not have to care about distances at all.


