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?


2 Answers 2


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.

  • $\begingroup$ 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 :-) $\endgroup$ Commented Aug 18, 2019 at 19:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – πr8
    Commented Aug 18, 2019 at 19:55
  • $\begingroup$ Are you sure you can interchange the product and expectation in the second line of the proof of unbiasedness? $\endgroup$
    – jbowman
    Commented Aug 18, 2019 at 20:31
  • 2
    $\begingroup$ Seems like it's ok because they're computed iid, right? $\endgroup$ Commented Aug 18, 2019 at 20:33
  • 3
    $\begingroup$ +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. $\endgroup$
    – whuber
    Commented Aug 19, 2019 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.

  • 1
    $\begingroup$ 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 :-) ) $\endgroup$ Commented Aug 18, 2019 at 19:28
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented Aug 18, 2019 at 19:32
  • $\begingroup$ 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... $\endgroup$ Commented Aug 18, 2019 at 19:35
  • 4
    $\begingroup$ BTW I'd really appreciate your thoughts on the other answer to this question! $\endgroup$ Commented Aug 18, 2019 at 19:59
  • $\begingroup$ I did in a comment to that answer. $\endgroup$
    – whuber
    Commented May 19, 2022 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.