Monte Carlo Expected Error

We follow Chapter 2 of Niederreiter [#!kn:Niederreiter1992!#] page 4. The notation is changed somewhat so as to reduce name clashes with later applications in finance.

Consider a function h(x) where x is an n-dimensional vector over some volume $\Omega$.

$$\int h(x) dx = \lambda(\Omega) \int h d\phi = \lambda(\Omega) E[h]$$ (2.7)

where $d\phi = dx/\lambda(\Omega)$ and $\lambda(\Omega)$ is the volume of $\Omega$, i.e. its Lesbesgue measure. This is equation 1.3 of Niederreiter [#!kn:Niederreiter1992!#] page 4. Note that h need not be non-negative or positive.

We have the expression

Definition 11 (Monte Carlo Estimate)  

$$E[h] = \frac{1}{N} \sum_{i=1}^N f(x_i) + \epsilon$$ (2.8)

This becomes an approximation when we assume that $\epsilon$ is zero. What makes it Monte Carlo is when the points $x_i$ are distributed according to the distribution $\phi$, where now we don't require that we have the $\phi$ above for Niederreiter's explanation of how to write an integral in terms of an expectation.

The variance of the distribution is defined as

Definition 12 (Variance)  

$$\sigma^2(h) = E[(h - E(h))^2]$$ (2.9)

The expected error of the Monte Carlo estimate is defined to be its sample variance, i.e.

Definition 13 (Expected Error)  

$$\sigma_e^2(h) = E[(\frac{1}{N}\sum_{i=1}^N f(x_i) - E(h))^2]$$ (2.10)

Here we use N as the divisor and not N-1 following Niederreiter.

Niederreiter proves Theorem 1.1 (his numbering) on (his) page 4 that

Theorem 2 (Expected Error)  

$$\sigma_e^2(h) = \sigma^2(h)/N$$ (2.11)

This shows that this expression for the error is the expected error and not derived, at least in this form as a bound on the error.

In fact, it is easy to show examples in which the error is greater than this value. One can simply take a sample in which all the points exceed some lower bound or are lower than some greater bound and choose the bound so that the Monte Carlo Estimate is more than the Expected Error from its expected value.