Monte Carlo integration
In mathematics, Monte Carlo integration is a technique for numerical integration using random numbers.
≈ 8 min read
Monte Carlo integration. encyclopegia.org, snapshot enwiki-001319230291. /a/monte-carlo-integration
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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, Monte Carlo randomly chooses points at which the integrand is evaluated.
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, importance sampling, sequential Monte Carlo (also known as a particle filter), and mean-field particle methods.
I = \int_{\Omega}f(\overline{\mathbf{x}}) \, d\overline{\mathbf{x}} where Ω, a subset of \mathbb{R}^m , has volume V = \int_{\Omega}d\overline{\mathbf{x}} The naive Monte Carlo approach is to sample points uniformly on Ω: 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 Q N , the error bars of Q N can be estimated by the sample variance using the unbiased estimate of the variance. \mathrm{Var}(f)=\mathrm{E}(\sigma_N^2) \equiv \frac{1}{N-1} \sum_{i=1}^N \mathrm{E}\left [\left (f(\overline{\mathbf{x}}_i) - \langle f \rangle \right )^2\right ]. 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{\mathrm{E}(\sigma_N^2)}{N}.
Since the sequence \left \{ \mathrm{E}(\sigma_1^2), \mathrm{E}(\sigma_2^2), \mathrm{E}(\sigma_3^2), \ldots \right \} is bounded due to being identically equal to Var(f), as long as this is assumed finite, this variance decreases asymptotically to zero as 1/N. The estimation of the error of Q N is thus \delta Q_N\approx\sqrt{\mathrm{Var}(Q_N)}=V\frac{\sqrt{\mathrm{Var}(f)}}{\sqrt{N}}, which decreases as \tfrac{1}{\sqrt{N}} . This is standard error of the mean multiplied with V . This result does not depend on the number of dimensions of the integral, which is the promised advantage of Monte Carlo integration against most deterministic methods that depend exponentially on the dimension.
It is important to notice that, unlike in deterministic methods, the estimate of the error is not a strict error bound; random sampling may not uncover all the important features of the integrand that can result in an underestimate of the error. While the naive Monte Carlo works for simple examples, an improvement over deterministic algorithms can only be accomplished with algorithms that use problem-specific sampling distributions.
With an appropriate sample distribution it is possible to exploit the fact that almost all higher-dimensional integrands are very localized and only small subspace notably contributes to the integral. A large part of the Monte Carlo literature is dedicated in developing strategies to improve the error estimates.
In particular, stratified sampling—dividing the region in sub-domains—and importance sampling—sampling from non-uniform distributions—are two examples of such techniques. H\left(x,y\right)=\begin{cases} 1 & \text{if }x^{2}+y^{2}\leq1\\ 0 & \text{else} \end{cases} and the set Ω = [−1,1] × [−1,1] with V = 4. Notice that I_\pi = \int_\Omega H(x,y) dx dy = \pi.
Thus, a crude way of calculating the value of π with Monte Carlo integration is to pick N random numbers on Ω and compute Q_N = 4 \frac{1}{N}\sum_{i=1}^N H(x_{i},y_{i}) In the figure on the right, the relative error \tfrac{Q_N-\pi}{\pi} is measured as a function of N, confirming the \tfrac{1}{\sqrt{N}} . include include include int main() { // Initialize the number of counts to 0, setting the total number to be 100000 in the loop. int throws = 99999, insideCircle = 0; double randX, randY, pi; srand(time(NULL));
// Checks for each random pair of x and y if they are inside circle of radius 1. for (int i = 0; i import numpy as np rng = np.random.default_rng(0) throws = 2000 radius = 1 Choose random X and Y data centered around 0,0 x = rng.uniform(-radius, radius, throws) y = rng.uniform(-radius, radius, throws) Count the times (x, y) is inside the circle, which happens when sqrt(x^2 + y^2) f(x) = \frac{1}{1+\sinh(2x)\log(x)^2} from 0.8 using the Monte-Carlo method in Mathematica: func[x_] := 1/(1 + Sinh[2*x]*(Log[x])^2);
(*Sample from truncated normal distribution to speed up convergence*) Distrib[x_, average_, var_] := PDF[NormalDistribution[average, var], 1.1*x - 0.1]; n = 10; RV = RandomVariate[TruncatedDistribution[{0.8, 3}, NormalDistribution[1, 0.399]], n];
Int = 1/n Total[func[RV]/Distrib[RV, 1, 0.399]]*Integrate[Distrib[x, 1, 0.399], {x, 0.8, 3}] NIntegrate[func[x], {x, 0.8, 3}] (*Compare with real answer*) E(f) = \tfrac{1}{2} \left (E_a(f) + E_b(f) \right ) is given by, \mathrm{Var}(f) = \frac{\sigma_a^2(f)}{4 N_a} + \frac{\sigma_b^2(f)}{4 N_b} It can be shown that this variance is minimized by distributing the points such that, \frac{N_a}{N_a + N_b} = \frac{\sigma_a}{\sigma_a + \sigma_b} Hence the smallest error estimate is obtained by allocating sample points in proportion to the standard deviation of the function in each sub-region. The MISER algorithm proceeds by bisecting the integration region along one coordinate axis to give two sub-regions at each step.
The direction is chosen by examining all d possible bisections and selecting the one which will minimize the combined variance of the two sub-regions. The variance in the sub-regions is estimated by sampling with a fraction of the total number of points available to the current step. The same procedure is then repeated recursively for each of the two half-spaces from the best bisection.
The remaining sample points are allocated to the sub-regions using the formula for N a and N b . This recursive allocation of integration points continues down to a user-specified depth where each sub-region is integrated using a plain Monte Carlo estimate. These individual values and their error estimates are then combined upwards to give an overall result and an estimate of its error.
Consider the following example where one would like to numerically integrate a Gaussian function, centered at 0, with σ = 1, from −1000 to 1000. Naturally, if the samples are drawn uniformly on the interval [−1000, 1000], only a very small part of them would be significant to the integral.
This can be improved by choosing a different distribution from where the samples are chosen, for instance by sampling according to a Gaussian distribution centered at 0, with σ = 1. Of course the "right" choice strongly depends on the integrand.
Formally, given a set of samples chosen from a distribution p(\overline{\mathbf{x}}) : \qquad \overline{\mathbf{x}}_1, \cdots, \overline{\mathbf{x}}_N \in V, the estimator for I is given by Q_N \equiv \frac{1}{N} \sum_{i=1}^N \frac{f(\overline{\mathbf{x}}_i)}{p(\overline{\mathbf{x}}_i)} Intuitively, this says that if we pick a particular sample twice as much as other samples, we weight it half as much as the other samples. This estimator is naturally valid for uniform sampling, the case where p(\overline{\mathbf{x}}) is constant.
The Metropolis–Hastings algorithm is one of the most used algorithms to generate \overline{\mathbf{x}} from p(\overline{\mathbf{x}}) , thus providing an efficient way of computing integrals. g(x_1, x_2, \ldots) = g_1(x_1) g_2(x_2) \ldots so that the number of bins required is only Kd. This is equivalent to locating the peaks of the function from the projections of the integrand onto the coordinate axes.
The efficiency of VEGAS depends on the validity of this assumption. It is most efficient when the peaks of the integrand are well-localized. If an integrand can be rewritten in a form which is approximately separable this will increase the efficiency of integration with VEGAS.
VEGAS incorporates a number of additional features, and combines both stratified sampling and importance sampling. Café math : Monte Carlo Integration : A blog article describing Monte Carlo integration (principle, hypothesis, confidence interval) Boost.Math : Naive Monte Carlo integration: Documentation for the C++ naive Monte-Carlo routines Monte Carlo applet applied in statistical physics problems
Text derived from https://en.wikipedia.org/w/index.php?oldid=1319230291 under CC BY-SA 4.0; modifications have been made.