Is stratified sampling useful for volume estimation via Monte Carlo integration?

Question

In the Wikipedia article on Monte Carlo integration, they give an example of stratified sampling for integrating the function

$$ f(x,y) = \begin{cases} 1 \;,\; x^2+y^2 < 1 \\ 0 \;,\; x^2+y^2 \geq 1\end{cases} $$

over the unit square $x,y \in [-1, 1]$. This integral basically represents the area of the unit circle.

So I was wondering whether stratified sampling is even useful for such volume estimations, also in higher dimensions. The standard error for the Monte Carlo integral of binary functions (i.e. either $1$ or $0$), which represents the volume of the region where $f \equiv 1$, can be expressed in the following way:

$$ \begin{aligned} \sigma_N^2 &= \frac{1}{N-1}\sum_{i=1}^{N}\left[f_i - \langle f\rangle \right]^2 \\ &= \frac{1}{N-1}\left[\sum_i f_i^2 - 2N\langle f\rangle^2 + N\langle f\rangle^2 \right] \\ &= \frac{1}{N-1}\left[\sum_i f_i^2 - N\langle f\rangle^2\right] \\ &= \frac{N}{N-1}\left[\langle f\rangle - \langle f\rangle^2\right] \\ \Rightarrow \mathrm{standard\,error\,of\,}\langle f\rangle &= \frac{\sigma_N}{\sqrt{N}} = \sqrt{\frac{\langle f\rangle - \langle f\rangle^2}{N-1}} \end{aligned} $$

where $f_i$ is the $i$-th Monte Carlo sample and $\sum_i f_i = N\langle f\rangle$ and $f_i^2 = f_i$ has been used.

The function $\langle f\rangle - \langle f\rangle^2$ behaves in the following way, so the maximum error is obtained for $\langle f\rangle = \frac{1}{2}$:

The error relative to the actual estimate, i.e.

$$ \frac{\mathrm{standard\,error}}{\langle f\rangle} = \sqrt{\frac{\frac{1}{\langle f\rangle} - 1}{N-1}} $$

is largest for $\langle f\rangle \ll 1$.

How does stratified sampling help in this case to reduce the standard error of the volume estimate?

Answer 1

As can be seen from the formula

$$ \frac{\mathrm{standard\ error}}{\langle f\rangle} = \sqrt{\frac{\frac{1}{\langle f\rangle}-1}{N-1}} $$

the error relative to the estimate $\langle f\rangle$ increases for smaller $\langle f\rangle$. This is where stratified sampling helps. It samples on a subspace (stratum) that is effectively much smaller and hence manages to achieve much larger values of $\langle f\rangle$. Note that the actual estimate of the integral remains the same because in fact $\langle f\rangle$ needs to be multiplied by $V$, the sampled volume. Without stratified sampling, $V$ is the entire domain and hence $\langle f\rangle$ might be very small. For stratified sampling, however, only relevant regions of the domain are sampled and hence the effective $V$ is much smaller while one obtains a proportionally increased $\langle f\rangle$ with the same number of samples $N$. This decreases the error estimate while the estimate of the integral, the product $V\langle f\rangle$, remains similar.