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

Question

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.

Answer 1

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.