Mathematics.

computational probability

Monte Carlo Methods

Probability25 minDifficulty3 out of 10

You should know: law of large numbers

Overview

Monte Carlo methods are a broad class of computational algorithms that use repeated random sampling to estimate numerical quantities that are difficult or impossible to compute exactly, such as complex integrals, expectations, or probabilities. The core idea is to simulate a random process many times and use the sample average of the outcomes as an estimate of the true quantity, relying on the law of large numbers to guarantee that this average converges to the correct value as the number of simulations grows. The method takes its name from the Monte Carlo Casino, evoking the role of chance, and was formalized by Stanislaw Ulam and John von Neumann in the 1940s for nuclear physics calculations.

Intuition

Suppose you want to know the area of an oddly-shaped splatter of paint, but there's no formula for its boundary. One trick: throw darts randomly at a rectangle that contains the splatter, count what fraction land inside the splatter, and multiply that fraction by the rectangle's area. Throw enough darts and this estimate gets very accurate — that's the entire idea behind Monte Carlo methods. Instead of solving a hard problem analytically, you turn it into 'what fraction of random samples satisfy this property,' and let the law of large numbers guarantee that repeating the experiment enough times converges to the right answer.

Formal Definition

Definition

To estimate an expectation E[g(X)] using n independent samples X₁,...,Xₙ drawn from the distribution of X:

θ^n=1n∑i=1ng(Xi)\hat{\theta}_n = \frac{1}{n}\sum_{i=1}^{n} g(X_i)
Monte Carlo estimator
θ^n→PE[g(X)]as n→∞\hat{\theta}_n \xrightarrow{P} E[g(X)] \quad \text{as } n \to \infty
Consistency (by the law of large numbers)
SE⁡(θ^n)=σn\operatorname{SE}(\hat{\theta}_n) = \frac{\sigma}{\sqrt{n}}
Standard error of the estimate

Worked Examples

  1. The circle has area π(1)² = π, and the square has area 2×2=4, so the ratio of areas equals the fraction landing inside.

    darts in circletotal darts≈π4\frac{\text{darts in circle}}{\text{total darts}} \approx \frac{\pi}{4}

  2. Solve for π using the observed fraction 785/1000 = 0.785.

    π≈4×0.785=3.14\pi \approx 4 \times 0.785 = 3.14

Answer: π ≈ 3.14, close to the true value of 3.14159....

Practice Problems

Difficulty 3/10

In a dart-throwing simulation to estimate π, 900 out of 1200 darts land inside a unit circle inscribed in a 2×2 square. Estimate π.

Difficulty 4/10

A Monte Carlo estimate has σ=5. How many samples n are needed to reduce the standard error to 0.5?

Difficulty 5/10

A risky financial option's expected payoff is estimated via Monte Carlo simulation of 10,000 random price paths, giving a sample average payoff of $42 with sample standard deviation $200. Estimate the standard error of this Monte Carlo estimate.

Quiz

Monte Carlo methods estimate quantities by:
The theoretical justification that a Monte Carlo estimate converges to the true value as n grows is:
To cut the standard error of a Monte Carlo estimate in half, you generally need to:

Summary

  • Monte Carlo methods estimate hard-to-compute quantities via repeated random sampling and averaging.
  • Convergence of the sample average to the true value is guaranteed by the law of large numbers.
  • The estimate's standard error shrinks as σ/√n, so accuracy improves slowly (quadratically in cost) with more samples.

References

  1. WebsiteWikipedia — Monte Carlo method