11
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\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$ – Justin Solomon Aug 18 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 Aug 18 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 Aug 18 at 20:31
  • 2
    $\begingroup$ Seems like it's ok because they're computed iid, right? $\endgroup$ – Justin Solomon Aug 18 at 20:33
  • 2
    $\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 Aug 19 at 13:54
10
$\begingroup$

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.

$\endgroup$
  • 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$ – Justin Solomon Aug 18 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 Aug 18 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$ – Justin Solomon Aug 18 at 19:35
  • 4
    $\begingroup$ BTW I'd really appreciate your thoughts on the other answer to this question! $\endgroup$ – Justin Solomon Aug 18 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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