Skip to main content
2 of 4
deleted 2 characters in body
π314
  • 33
  • 4

Approximating the Probability of a Half-Space Using Random Voronoi Diagrams

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 D^m}\left[ \hat{p}(H) \right] = p(H) $$

π314
  • 33
  • 4