next up previous
Next: Exercise 10.1: One dimensional Up: Monte Carlo integration Previous: Simple Monte Carlo integration

Monte Carlo error analysis

The Monte Carlo method clearly yields approximate results. The accuracy deppends on the number of values $N$ that we use for the average. A possible measure of the error is the ``variance'' $\sigma^2$ defined by:

\begin{displaymath}
\sigma ^2=\langle f^2 \rangle - \langle f \rangle ^2,
\end{displaymath} (269)

where

\begin{displaymath}
\langle f \rangle = \frac{1}{N} \sum_{i=1}^N f(x_i)
\end{displaymath}

and

\begin{displaymath}
\langle f^2 \rangle = \frac{1}{N} \sum_{i=1}^{N} f(x_i)^2.
\end{displaymath}

The ``standard deviation'' is $\sigma$. However, we should expect that the error decreases with the number of points $N$, and the quantity $\sigma$ defines by (271) does not. Hence, this cannot be a good measure of the error.

Imagine that we perform several measurements of the integral, each of them yielding a result $I_n$. Thes values have been obtained with different sequences of $N$ random numbers. According to the central limit theorem, these values whould be normally dstributed around a mean $\langle I
\rangle$. Suppouse that we have a set of $M$ of such measurements ${I_n}$. A convenient measure of the differences of these measurements is the ``standard deviation of the means'' $\sigma_M$:

\begin{displaymath}
\sigma_M ^2=\langle I^2 \rangle - \langle I \rangle ^2,
\end{displaymath} (270)

where

\begin{displaymath}
\langle I \rangle = \frac{1}{M} \sum_{n=1}^M I_n
\end{displaymath}

and

\begin{displaymath}
\langle I^2 \rangle = \frac{1}{M} \sum_{n=1}^{M} I_n^2.
\end{displaymath}

Although $\sigma_M$ gives us an estimate of the actual error, making additional meaurements is not practical. instead, it can be proven that
\begin{displaymath}
\sigma_M \approx \sigma/\sqrt{N}.
\end{displaymath} (271)

This relation becomes exact in the limit of a very large number of measurements. Note that this expression implies that the error decreases withthe squere root of the number of trials, meaning that if we want to reduce the error by a factor 10, we need 100 times more points for the average.



Subsections
next up previous
Next: Exercise 10.1: One dimensional Up: Monte Carlo integration Previous: Simple Monte Carlo integration
Adrian E. Feiguin 2009-11-04