2
$\begingroup$

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.

Question

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Leonidas May 3 '20 at 14:17

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.