Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results; i.e., by running simulations many times over in order to calculate those same probabilities heuristically just like actually playing and recording your results in a real casino situation: hence the name.
They are often used in physical and mathematical problems and are most suited to be applied when it is impossible to obtain a closed-form expression or infeasible to apply a deterministic algorithm. Monte Carlo methods are mainly used in three distinct problems: optimization, numerical integration and generation of samples from a probability distribution.
Monte Carlo methods are especially useful for simulating systems with many coupled degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model). They are used to model phenomena with significant uncertainty in inputs, such as the calculation of risk in business. They are widely used in mathematics, for example to evaluate multidimensional definite integrals with complicated boundary conditions. When Monte Carlo simulations have been applied in space exploration and oil exploration, their predictions of failures, cost overruns and schedule overruns are routinely better than human intuition or alternative "soft" methods.
Monte Carlo methods vary, but tend to follow a particular pattern:
- Define a domain of possible inputs.
- Generate inputs randomly from a probability distribution over the domain.
- Perform a deterministic computation on the inputs.
- Aggregate the results.
Example
Consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that is π/4, the value of π can be approximated using a Monte Carlo method:
- Draw a square on the ground, then inscribe a circle within it.
- Uniformly scatter some objects of uniform size (grains of rice or sand) over the square.
- Count the number of objects inside the circle and the total number of objects.
- The ratio of the two counts is an estimate of the ratio of the two areas, which is π/4. Multiply the result by 4 to estimate π.
In this procedure the domain of inputs is the square that circumscribes our circle. We generate random inputs by scattering grains over the square then perform a computation on each input (test whether it falls within the circle). Finally, we aggregate the results to obtain our final result, the approximation of π.
If grains are purposely dropped into only the center of the circle, they are not uniformly distributed, so our approximation is poor. Second, there should be a large number of inputs. The approximation is generally poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.
Summary
수 많은 샘플링을 통해 결과를 종합하여 특정 사건이 발생할 확률 또는 발생한 비율을 추정한다.
Monte Carlo Integration
In mathematics, Monte Carlo integration is a technique for numerical integration using random numbers. It is a particular method of Monte Carlo methods that numerically computes a definite integral. While other algorithms usually evaluate the integrand(피적분함수) at a regular grid, Monte Carlo algorithms randomly choose the points at which the integrand is evaluated. This method is particularly useful for higher dimensional integrals.
Informally, to estimate the area of a domain D, first pick a simple domain E whose area is easily calculated and which contains D (D ⊂ E). Now pick a sequence of random points that fall within E. Some fraction of these points will also fall within D. The area of D is then estimated as this fraction multiplied by the area of E.
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 can be easily calculated, the area of the circle 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 π/4 ≈ 0.8
The original Monte Carlo approach was a method developed by physicists to use random number generation to compute integrals.
Suppose we wish to compute a complex integral
If we can decompose h(x) into the production of a function f(x) and a probability density function p(x) defined over the interval (a,b), then note that
so that the integral can be expressed as an expectation of f(x) over the density p(x). Thus, if we draw a large number of random variables x1, x2, ..., xn from the density p(x), then
This is referred to as Monte Carlo integration.
Summary
몬테 카를로 방법은 난수 생성을 통해 integral을 계산하는 방법이다. Integral은 특정 확률 분포 p(x)를 따르는 어느 함수 f(x)의 기대값으로 표현될 수 있다.