# Comparing Variances of two Hit-or-Miss methods for estimating volume

My question is on Exercise 1.4 of Neal Madras' "Lectures on Monte Carlo Methods" (problem pictured below). My current work is as follows:

Method 1: Let $$X_1,X_2,\ldots,X_N$$ be i.i.d. uniform on the set $$A$$. Define \begin{align*} Y_i = \begin{cases} 1 & \text{if } X_i \in B \\ 0 & \text{otherwise}, \end{cases} \qquad \text{for } i = 1,2,\ldots,N. \end{align*}

Our estimator in this case is $$I_N = \frac{1}{N} \sum_{i=1}^{N} Y_i.$$ To compute $$\text{var}(I_N)$$, note that $$Y_i \overset{\text{iid}}{\sim} \text{Bernoulli}(p)$$, where $$p = \frac{\text{vol}(B)}{\text{vol}(A)}$$. Then \begin{align*} \text{var}(I_N) = \text{var} \bigg(\frac{1}{N} \sum_{i=1}^{N} Y_i \bigg) = \frac{1}{N^2} \sum_{i=1}^{N} \text{var}(Y_i) = \frac{1}{N^2} \cdot N \text{var}(Y_1) = \frac{\text{Var}(Y_1)}{N} = \frac{p(1-p)}{N}. \end{align*}

Method 2: Since vol$$(B) = \text{vol}(B \cap D) + \text{vol}(B \cap D^c)$$ (this book does not deal with measure theory) and we know $$\text{vol}(D \cap B)$$, we only need to estimate vol$$(D \cap B^c)$$. So our second estimator for vol$$(B)$$ is $$\hat{I}_N = \text{vol}(D \cap B) + \frac{1}{N} \sum_{i=1}^{N} Z_i,$$

where the $$Z_i$$'s are i.i.d. uniform on $$A \cap D^c$$. Clearly, $$Z_i \overset{\text{iid}}{\sim} \text{Bernoulli}(\hat{p})$$ where $$\hat{p} = \text{vol}(B \cap D^c)/ \text{vol}(A \cap D^c)$$. Thus, $$\text{var}(\hat{I}_N) = \frac{\text{var}(Z_1)}{N} = \frac{\hat{p}(1-\hat{p})}{N}.$$ So now I need to show that $$\frac{\text{vol}(B \cap D^c)}{\text{vol}(A \cap D^c)} \bigg(1 - \frac{\text{vol}(B \cap D^c)}{\text{vol}(A \cap D^c)} \bigg) \leq \frac{\text{vol}(B)}{\text{vol}(A)} \bigg(1 - \frac{\text{vol}(B)}{\text{vol}(A)} \bigg).$$

This is where I am stuck; I don't see any clear way of getting to the above inequality. Clearly, $$p(1-p)$$ is maximized at $$p = 1/2$$, so $$\hat{p}$$ should be farther from $$1/2$$ than $$p$$ to make $$\text{var}(\hat{I}_N) \leq \text{var}(I_N)$$, but this still doesn't seem to get me anywhere. Any help would be greatly appreciated.

You forgot a coefficient in $$\hat I$$ (by the way, this is an unusual use of hat symbol for statistics): $$\hat I_N = \text{vol}(D \cap B) + \text{vol}(A \cap D^c) \left(\frac{1}{N} \sum_{i=1}^{N} Z_i\right).$$

Proving that $$\hat I_N$$ has indeed lower variance that $$I_N$$ takes some more steps, and I'm not sure about what's the easiest path. However, I'll show you one possible way. I edited the answer because I found that my previous proof had a flaw, so I'm posting a version that I think it's actually simpler.

## Proof

Consider $$I_N$$ as a sum of two terms analogous to the two in the equation above: $$I_N = \frac{1}{N} \sum_{X_i \in D} Y_i + \frac{1}{N} \sum_{X_i \in D^c} Y_i.$$

From now on we will consider just the second term of this equation. For brevity, we will call $$k := \#(X_i \in D^c)$$ and $$p := \text{E}[Y_i | X_i \in D^c]$$. That is clearly the same expected value of the $$Z_i$$ in the formula of $$\hat I_N$$. Moreover, we will call $$q := \text{vol}(A \cap D^c)$$, so that $$k \sim Bin(q, N)$$.

The only non trivial passage here involves the law of total variance:

$$\text{Var}\left[ \frac{1}{N} \sum_{X_i \in D^c} Y_i \right] = \frac{1}{N^2} \Big( \text{E}[k\,p(1-p)] + \text{Var}[k\,p] \Big)= \\ = \frac{1}{N^2} \big( qNp(1-p) + q(1-q)Np \big) = q\frac{1}{N}p(2-q-p)$$ While: $$\text{Var}\left[ q \left(\frac{1}{N} \sum_{i=1}^{N} Z_i\right) \right] = q^2\frac{1}{N}p(1-p)$$

This leads to the following equation:

$$q\frac{1}{N}p(2-q-p) \stackrel{?}{=} q^2\frac{1}{N}p(1-p) \rightarrow\\ 2-q-p \stackrel{?}{=} q(1-p) \rightarrow\\ 2-p \stackrel{?}{=} q(2-p)$$

If $$q=1$$ the two estimators not only have the same variance, but they are no different. However, if $$q < 1$$, the second term alone of $$I_N$$ has higher variance than the whole $$\hat I_N$$. Equality actually also occurs if $$p \in \{0, 1\}$$ or if $$q = 0$$, in those cases $$\hat I_N$$ will have null variance, while the variance of $$I_N$$ will only depend on its first term.

• Thank you for your work on this problem! Forgetting the "coefficient" was indeed a big oversight on my part. I worked out a solution that I think is very similar to yours, albeit with slightly different notation. I may post it later if I have time. May 3, 2020 at 14:17