thumb|right|an illustration of monte carlo integration. in this example, the domain d is the inner circle and the domain e is the square. because the square's area (4) can be easily calculated, the area of the circle (Ï*12) can be estimated by the ratio (0.8) of the points inside the circle (40) to the total number of points (50), yielding an approximation for the circle's area of 4*0.8 = 3.2 â Ï*12. in mathematics, monte carlo integration is a technique for numerical integration using random numbers. it is a particular monte carlo method that numerically computes a definite integral. while other algorithms usually evaluate the integrand at a regular grid,press et al, 2007, chap. 4. monte carlo randomly choose points at which the integrand is evaluated.press et al, 2007, chap. 7. this method is particularly useful for higher-dimensional integrals. there are different methods to perform a monte carlo integration, such as uniform sampling, stratified sampling and importance sampling. == overview == in numerical integration, methods such as the trapezoidal rule use a deterministic approach. monte carlo integration, on the other hand, employs a non-deterministic approach: each realization provides a different outcome. in monte carlo, the final outcome is an approximation of the correct value with respective error bars, and the correct value is within those error bars. the problem monte carlo integration addresses is the computation of a multidimensional definite integral :i = \int_{\omega}f(\overline{\mathbf{x}}) \, d\overline{\mathbf{x}} where Î©, a subset of rm, has volume :v = \int_{\omega}d\overline{\mathbf{x}} the naive monte carlo approach is to sample points uniformly on Î©:newman, 1999, chap. 1. given n uniform samples, :\overline{\mathbf{x}}_1, \cdots, \overline{\mathbf{x}}_n\in \omega, i can be approximated by : i \approx q_n \equiv v \frac{1}{n} \sum_{i=1}^n f(\overline{\mathbf{x}}_i) = v \langle f\rangle. this is because the law of large numbers ensures that : \lim_{n \to \infty} q_n = i. given the estimation of i from qn, the error bars of qn can be estimated by the sample variance using the unbiased estimate of the variance: : \mathrm{var}(f)\equiv\sigma_n^2 = \frac{1}{n-1} \sum_{i=1}^n \left (f(\overline{\mathbf{x}}_i) - \langle f \rangle \right )^2. which leads to : \mathrm{var}(q_n) = \frac{v^2}{n^2} \sum_{i=1}^n \mathrm{var}(f) = v^2\frac{\mathrm{var}(f)}{n} = v^2\frac{\sigma_n^2}{n}. as long as the sequence : \left \{ \sigma_1^2, \sigma_2^2, \sigma_3^2, \ldots \right \} is bounded, this variance decreases asymptotically to zero as 1/n. the estimation of the error of qn
Monte_Carlo_methods