Monte Carlo Systems

Monte Carlo estimate & variance

Simple Fundamental Explanation

Imagine you want to calculate the area of an irregularly shaped lake. You could try to use complex calculus and geometry to measure every tiny curve of the shoreline. This would take months of painstaking survey work.

Or, you could use a Monte Carlo approach:

1. Draw a perfect square around the entire lake on a map. You know the exact area of this square.
2. Blindfold yourself and randomly throw 10,000 darts at the map.
3. Count how many darts landed in the water, and how many landed on the dry land inside the square.

If 70% of the darts landed in the water, then the area of the lake is approximately 70% of the area of the square.

A Monte Carlo System is any computational algorithm that relies on repeated random sampling to obtain numerical results. Instead of trying to calculate a perfect, deterministic mathematical answer (which might be impossible), you simulate the problem thousands of times using randomness and look at the average outcome.

---

Deep Dive: How It Works Under the Hood

Monte Carlo methods are used primarily for three problem classes:

1. Optimization: Finding the best solution among trillions of possibilities (e.g., finding the best move in Chess).
2. Numerical Integration: Calculating the area under complex curves.
3. Generating Draws from a Probability Distribution: Simulating complex, real-world systems with unknown outcomes (e.g., the stock market or weather).

The Core Loop

A typical Monte Carlo simulation follows this pattern:

1. Define a domain of possible inputs.
2. Generate inputs randomly from a probability distribution over the domain.
3. Perform a deterministic computation on the inputs.
4. Aggregate the results of the individual computations into a final estimate.

Visual Diagram: Estimating Pi ($\pi$)

Draw a 2x2 square (Area = 4).
Draw a circle inside it with radius r=1. (Area = pi * r^2 = pi).

Randomly generate coordinates (x, y) between -1 and 1.
Check if the point is inside the circle: x^2 + y^2 <= 1.

Dart 1: (0.5, 0.5)   -> 0.25 + 0.25 = 0.5 <= 1  [HIT]
Dart 2: (0.9, 0.9)   -> 0.81 + 0.81 = 1.62 > 1  [MISS]
Dart 3: (-0.1, 0.2)  -> 0.01 + 0.04 = 0.05 <= 1 [HIT]
...
Dart 1,000,000.

Hits = 785,398
Total = 1,000,000

Ratio = Hits / Total = 0.785398
Area of Circle = Ratio * Area of Square
pi = 0.785398 * 4
pi = 3.141592

---

Practical Example: AlphaGo and MCTS

In 2016, DeepMind’s AlphaGo defeated the world champion in the ancient board game Go. Chess algorithms (like Deep Blue) used deterministic “Minimax” search. They looked ahead at every possible move, evaluated the board, and picked the best one.

Go has more possible board configurations than there are atoms in the universe ($10^{170}$). A deterministic search would run until the sun exploded without finding an answer.

AlphaGo used Monte Carlo Tree Search (MCTS). When deciding what move to make, the AI didn’t calculate every possibility. It picked a potential move, and then “played out” the rest of the game to the very end completely randomly (thousands of times). If randomly playing out Move A resulted in a win 60% of the time, and Move B resulted in a win 40% of the time, the AI confidently chose Move A. By using random simulations combined with a neural network to guide the randomness, it achieved superhuman intuition.

---

The Mathematics: Equations and In-Depth Analysis

1. The Law of Large Numbers

The entire foundation of Monte Carlo methods rests on the Strong Law of Large Numbers. If $X$ is a random variable with expected value $\mu$, and we take $N$ independent, identically distributed samples $x_1,x_2,\dots ,x_N$, the sample average ${\bar{x}}_N$ converges to the true expected value as $N$ goes to infinity:

$$\underset{N\to \infty }{\lim }\frac{1}{N}\sum _{i=1}^N{x}_i=\mu$$

2. Error Rate and Convergence

How many “darts” do we need to throw to get an accurate answer? The accuracy of a Monte Carlo estimate is determined by its variance. According to the Central Limit Theorem, the standard error of the estimate ${\bar{x}}_N$ is:

$$\text{Error}\approx \frac{\sigma }{\sqrt{N}}$$

Where $\sigma$ is the standard deviation of the underlying function.

This equation is both the greatest strength and greatest weakness of Monte Carlo.

• The Weakness: To cut the error in half, you must quadruple ($4\times$) the number of samples. To get 1 extra decimal point of precision (10x better), you need 100x more compute power. Convergence is slow.
• The Strength: Notice what is missing from the equation: the number of dimensions $D$. In traditional deterministic integration (like grid search), calculating a 100-dimensional problem takes $O(N^{100})$ time. In Monte Carlo, the error is always $\frac{1}{\sqrt{N}}$, completely regardless of how many dimensions the problem has. This makes Monte Carlo the only mathematically viable way to solve high-dimensional physics, finance, and AI problems.

Lab

Monte Carlo integration: random samples estimate π (quarter-circle hits in the unit square) or ∫₀¹ x² dx. The convergence strip plots |estimate − truth| vs N; metrics show the README’s σ/√N standard error.

Sample count (N)4000 samples

RNG seedseed 42

Few samples (noisy)Many samples∫ x² on [0,1]

▶ Play samples

Estimate π∫₀¹ x² dx

|π̂ − π| vs sample count (log-spaced checkpoints, same seed).

Halving error needs ~4× samples (README). At N=4000, try N≈16000 for ~½ SE.

At N=4000 for π, will the standard error σ/√N be within 2.5× of |estimate − exact| (CLT band)?

Yes — within CLT band (error < 2.5× SE)No — error exceeds CLT band

π estimate 3.1690 · exact 3.1416 · SE 0.0257. Reveal above for side-by-side compare.