The complexity of real-world problems in economics, biology, physics, finance and even mathematics sometimes renders deterministic methods inadequate. Computer-based numerical methods that use randomness can then prove extraordinarily useful. Among them is the so-called Monte Carlo method, developed shortly before 1950 by the physicist Nicholas Constantine Metropolis. In mathematics, it is particularly effective for computing high-dimensional integrals over very large domains and, in practice, yields more accurate numerical results than classical deterministic methods. Let's see how it works in a simple case.
Simulating randomness -------------------------------------
To compute the integral I=∫01f(x)dx\text{I}=\int _0^1 f(x)dx, we treat the real number x (which ranges from 0 to 1) as a random variable and construct a sequence of independent values x1, x2… xn, uniformly distributed over the interval [0, 1). We then estimate the definite integral I using the following relation, in which the familiar notion of a mean appears:
I−1n∑i=1nf(xi).\text{I}-\frac{1}{n}\sum_{i=1}^{n}f(x_i).
The weak law of large numbers (or the central limit theorem) gives a fairly precise estimate of the method's convergence rate. This rate is of order 1/n1/\sqrt{n} and is proportional to the standard deviation of the random variable f (x) arising from the sampling procedure. In a simple case such as estimating I, this convergence rate may seem slow. But it offers two advantages. First, it is unaffected by the dimension of the integral. Second, it does not depend on the regularity of the function being integrated, provided that the function is square-integrable (a necessary condition for the variance of f (x) to exist).