# Unbiased estimator of exponential of measure of a set?

Suppose we have a (measurable and suitably well-behaved) set $$S\subseteq B\subset\mathbb R^n$$, where $$B$$ is compact. Moreover, suppose we can draw samples from the uniform distribution over $$B$$ wrt the Lebesgue measure $$\lambda(\cdot)$$ and that we know the measure $$\lambda(B)$$. For example, perhaps $$B$$ is a box $$[-c,c]^n$$ containing $$S$$.

For fixed $$\alpha\in\mathbb R$$, is there a simple unbiased way to estimate $$e^{-\alpha \lambda(S)}$$ by uniformly sampling points in $$B$$ and checking if they are inside or outside of $$S$$?

As an example of something that doesn't quite work, suppose we sample $$k$$ points $$p_1,\ldots,p_k\sim\textrm{Uniform}(B)$$. Then we can use the Monte Carlo estimate $$\lambda(S)\approx \hat\lambda:= \frac{\#\{p_i\in S\}}{k}\lambda(B).$$ But, while $$\hat\lambda$$ is an unbiased estimator of $$\lambda(S)$$, I don't think it's the case that $$e^{-\alpha\hat\lambda}$$ is an unbiased estimator of $$e^{-\alpha\lambda(S)}$$. Is there some way to modify this algorithm?

Suppose that you have the following resources available to you:

1. You have access to an estimator $$\hat{\lambda}$$.
2. $$\hat{\lambda}$$ is unbiased for $$\lambda ( S )$$.
3. $$\hat{\lambda}$$ is almost surely bounded above by $$C$$.
4. You know the constant $$C$$, and
5. You can form independent realisations of $$\hat{\lambda}$$ as many times as you'd like.

Now, note that for any $$u > 0$$, the following holds (by the Taylor expansion of $$\exp x$$):

\begin{align} e^{-\alpha \lambda ( S ) } &= e^{-\alpha C} \cdot e^{\alpha \left( C - \lambda ( S ) \right)} \\ &= e^{- \alpha C} \cdot \sum_{k \geqslant 0} \frac{ \left( \alpha \left[ C - \lambda ( S ) \right] \right)^k}{ k! } \\ &= e^{- \alpha C} \cdot e^u \cdot \sum_{k \geqslant 0} \frac{ e^{-u} \cdot \left( \alpha \left[ C - \lambda ( S ) \right] \right)^k}{ k! } \\ &= e^{u -\alpha C} \cdot \sum_{k \geqslant 0} \frac{ u^k e^{-u} }{ k! } \left(\frac{ \alpha \left[ C - \lambda ( S ) \right]}{u} \right)^k \end{align}

Now, do the following:

1. Sample $$K \sim \text{Poisson} ( u )$$.
2. Form $$\hat{\lambda}_1, \cdots, \hat{\lambda}_K$$ as iid unbiased estimators of $$\lambda(S)$$.
3. Return the estimator

$$\hat{\Lambda} = e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \cdot \prod_{i = 1}^K \left\{ C - \hat{\lambda}_i \right\}.$$

$$\hat{\Lambda}$$ is then a non-negative, unbiased estimator of $$\lambda(S)$$. This is because

\begin{align} \mathbf{E} \left[ \hat{\Lambda} | K \right] &= e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \mathbf{E} \left[ \prod_{i = 1}^K \left\{ C - \hat{\lambda}_i \right\} | K \right] \\ &= e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \prod_{i = 1}^K \mathbf{E} \left[ C - \hat{\lambda}_i \right] \\ &= e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \prod_{i = 1}^K \left[ C - \lambda ( S ) \right] \\ &= e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \left[ C - \lambda ( S ) \right]^K \end{align}

and thus

\begin{align} \mathbf{E} \left[ \hat{\Lambda} \right] &= \mathbf{E}_K \left[ \mathbf{E} \left[ \hat{\Lambda} | K \right] \right] \\ &= \mathbf{E}_K \left[ e^{u -\alpha C} \cdot \left(\frac{ \alpha }{u} \right)^K \left[ C - \lambda ( S ) \right]^K \right] \\ &= e^{u -\alpha C} \cdot \sum_{k \geqslant 0} \mathbf{P} ( K = k ) \left(\frac{ \alpha }{u} \right)^K \left[ C - \lambda ( S ) \right]^K \\ &= e^{u -\alpha C} \cdot \sum_{k \geqslant 0} \frac{ u^k e^{-u} }{ k! } \left(\frac{ \alpha \left[ C - \lambda ( S ) \right]}{u} \right)^k \\ &= e^{-\alpha \lambda ( S ) } \end{align}

by the earlier calculation.

• Interesting! Doesn't the estimator for $\hat\lambda$ described in the question work here, since it's bounded above by $\lambda(B)<\infty$? Also how come this doesn't contradict @whuber 's answer below? Is there an easy argument why this is unbiased? Sorry for many questions, my probability theory is weak :-) – Justin Solomon Aug 18 at 19:52
• The estimator you describe works, since you know $\lambda (B)$. I think this doesn't contradict the other answer because of assumption $5$; given finite access to unbiased estimators, I don't think this construction would work. The unbiasedness comes by comparing the expectation of $\hat{\Lambda}$ to the power series above; I'll make that clearer in the answer. – πr8 Aug 18 at 19:55
• Are you sure you can interchange the product and expectation in the second line of the proof of unbiasedness? – jbowman Aug 18 at 20:31
• Seems like it's ok because they're computed iid, right? – Justin Solomon Aug 18 at 20:33
• +1 I think this is an interesting and instructional example. It succeeds by not making an assumption implicit to my answer: that the sample size is either specified or at least bounded. – whuber Aug 19 at 13:54

The answer is in the negative.

A sufficient statistic for a uniform sample is the count $$X$$ of points observed to lie in $$S.$$ This count has a Binomial$$(n,\lambda(S)/\lambda(B))$$ distribution. Write $$p=\lambda(S)/\lambda(B)$$ and $$\alpha^\prime = \alpha\lambda(B).$$

For a sample size of $$n,$$ let $$t_n$$ be any (unrandomized) estimator of $$\exp(-\alpha \lambda(S)) = \exp(-(\alpha\lambda(B)) p) = \exp(-\alpha^\prime p).$$ The expectation is

$$E[t_n(X)] = \sum_{x=0}^n \binom{n}{x}p^x (1-p)^{n-x}\, t_n(x),$$

which equals a polynomial of degree at most $$n$$ in $$p.$$ But if $$\alpha^\prime p \ne 0,$$ the exponential $$\exp(-\alpha^\prime p)$$ cannot be expressed as a polynomial in $$p.$$ (One proof: take $$n+1$$ derivatives. The result for the expectation will be zero but the derivative of the exponential, which itself is an exponential in $$p,$$ cannot be zero.)

The demonstration for randomized estimators is nearly the same: upon taking expectations, we again obtain a polynomial in $$p.$$

Consequently, no unbiased estimator exists.

• Ah, that's a downer! Thanks for the nice proof. But, the Taylor series for $\exp(t)$ converges fairly quickly --- perhaps there's an "approximately unbiased" estimator out there? Not sure what that means (I'm not much of a statistician :-) ) – Justin Solomon Aug 18 at 19:28
• How quickly, exactly? The answer depends on the value of $\alpha^\prime p$--and therein lies your problem, because you don't know what that value is. You know only that it lies between $0$ and $\alpha.$ You could use that to establish a bound on the bias if you like. – whuber Aug 18 at 19:32
• In my application I expect $S$ to occupy a large portion of $B$. I'd like to use this value in a pseudo-marginal Metropolis-Hastings acceptance ratio, not sure if that method can handle even controllable levels of bias... – Justin Solomon Aug 18 at 19:35
• BTW I'd really appreciate your thoughts on the other answer to this question! – Justin Solomon Aug 18 at 19:59