previous up next ','..','$myPermit') ?> SYLLABUS  Previous: 5 MONTE-CARLO METHOD  Up: 5 MONTE-CARLO METHOD  Next: 5.2 Stochastic theory


5.1 Monte Carlo integration


Slide : [ integration || VIDEO 99) echo " modem - ISDN - LAN "; else echo "login";?> ]

The most common use of Monte Carlo methods is the evaluation of multi-dimensional integrals [24]. Consider first the approximation of an integral obtained from the trapezoidal rule (3.3#eq.1)

$\displaystyle \int_a^b f(\xi)\,d\xi = \sum_{i=0}^{N-1}f(x_i) \frac{b-a}{N}\; +\; \mathcal{O} \left( \frac{1}{N} \right) \;, \qquad x_i = a + \frac{b-a}{N-1} i$ (1)

Instead of a uniform sampling, imagine an evaluation where the positions $ \left\{x_i\right\}$ are random numbers uniformly distributed in the interval $ [a,b]$ ; this yields a Monte Carlo integration

$\displaystyle \int_a^b f(\xi)\,d\xi = \sum_{i=1}^Nf(x_i)\frac{b-a}{N} + \mathcal{O} \left( \frac{1}{\sqrt{N}} \right) \;, \qquad x_i \in \mathcal{U}(a,b)$ (2)

The convergence rate is of course lower than from a uniform sampling (5.1#eq.1); the strength however appears for integrals in higher dimensions $ d>2$ , where the Monte Carlo error scales as $ N^{-1/2}$ irrespective of the number of dimensions - instead of the scaling in $ N^{-1/d}$ that is achieved when using a uniform mesh.