Monte Carlo integration

Direct Monte Carlo integration can be referred to as randomized quadrature or crude Monte Carlo. Here random values are generated in the domain of a uniform distribution; the function to be integrated f is evaluated at those locations. Subsequently, the mean value of this function values is formed and multiplied by the width of the domain. This value is then used to estimate the integral. Compared to the numerical integration the deterministic support points are replaced by random support points. Given the approximation quality of numerical quadrature method, it may be surprising that there are methods such as Monte Carlo integration at all. In fact it can be seen quickly in testing the procedure that compared to the numerical quadrature usually many more support points are needed to achieve a similar result.

Unlike numerical quadrature method, the idea of Monte Carlo integration can be applied to the calculation of high-dimensional integrals very easily. There, the Monte Carlo integration has advantages over numerical integration method and therefore is still used today in this areas.

Another difference from the numerical integration is the typeof the convergence. In the numerical quadrature there are error estimatesin form of upper bounds for the error between the actual value of the integral and the computed approximation. These bounds strive for a finer decompositions of the domain to 0. In Monte Carlo integration the integral to be calculated is estimated by a random value. It can be shown that the expected value of this estimator is the exact value of the integral, and the variance of this estimator tends to 0, that is, with an increasing number of support points, the variation around the exact value is getting lower.

The error bounds of numerical integration rules contain a derivative term, therefore for the approximation to tend to the the correct value, is has to hold that the function to be integrated f is sufficiently smooth (f has to be differentiable four times as for Simpson's rule). Such demands are not needed at the Monte Carlo integration.

The hit-or-miss Monte Carlo integration directly uses the interpretation of the integral as area. The studied area is bounded by a rectangle, and on this random points are generated following a uniform distribution. The probability for such a point to be in the investigated area corresponds to the ratio of the desired surface content and the surface area of the whole rectangle. By the strong law of large numbers the relative frequency of the points that lie within the investigated area, just tends to this probability. The desired area thus can be approximated by the proportion of the points within the investigated area multiplied by the area of the rectangle.

Of course also other geometric boundaries can be used instead of a rectangle; it is important that the area can be relatively easily calculated, and that uniformly distributed points can be created in this area in a simple manner. As for the direct Monte Carlo integration here also numerical quadrature methods provide significantly better results on the here illustrated functions; the hit-or-miss-variant of the Monte Carlo integration is nowadays used only to calculate high-dimensional integrals.

Compared to the direct Monte Carlo integration, the variance of the estimator is even larger in the hit-or-miss-variant, this means the results are even less precise with the same number of points. But unlike all other methods one only needs to decide whether a y-coordinate is below the graph of the function or not, this may be associated with significantly less computational effort than the calculation of the function value itself.

A classic example is the semi-circle formed by the graph of the function with function term f(x)=sqrt(1-x²) and the x-axis. The equation y<f(x) can here be interpreted equivalent to y²+x²<1, e.g. for this decision it is not necessary to calculate the square root. As for computers adding and multiplying is much easier than the extraction of roots, in this way a significant amount of computing time can be saved.

There are examples where by such term transformations of the advantage of the hit-or-miss-variant of the Monte Carlo integration is even bigger than in this simple example; it may even happen that it is possible to decide whether y<f(x) is valid or not, even though there is no possibility to calculate f(x) explicitly. In such situations the hit-or-miss method often is the only way to calculate an integral (approximate).

In this window two predetermined functions can be integrated via Monte Carlo integration. The function to be integrated can be selected via the selection box at the bottom left. Using the slider at the bottom one can adjust the number of points to be used for Monte Carlo integration.