Skip to content
Computational Lab.

Monte Carlo Estimation

Random darts, converging on pi.

Beginner / probability / sampling / convergence

Throw uniform darts at a unit square; the fraction inside the quarter circle estimates pi over four. The estimate error falls like one over root N - agonizingly slow, which is the Monte Carlo lesson. The running absolute error against true pi is displayed, exponent and all.

Tagged: pi estimate, variance, inverse sqrt, uniform sampling

Live simulation

More darts, smaller error - falling like one over root N.

Speed

More darts, smaller error - falling like one over root N.

Mathematics

Monte Carlo estimation turns a deterministic quantity into a sampling problem: the fraction of uniform darts inside a quarter circle estimates pi/4, with standard error falling like 1/sqrt(N). The price of generality is that slow convergence rate - four times the darts buys half the error.

estimate: pi_hat = 4 * (hits / N)

standard error: sigma / sqrt(N) with sigma ~ 1.64 for this estimator

running error: |pi_hat - pi|

The displayed absolute error against true pi fluctuates - sometimes getting worse for a stretch - because the convergence rate is statistical, not monotone. That honesty matters: Monte Carlo methods buy generality with variance, and the only cure is more samples.

How it works

Each tick throws a fixed number of seeded darts; the display buffer keeps the most recent ones so the point cloud stays readable while the statistics accumulate over every draw ever made. The quarter-circle arc, the square, and the in/out coloring make the estimator's geometry literal.

At 400 darts per tick, a hundred ticks is 40,000 darts - error around the 1% mark, exactly as 1/sqrt(N) predicts.

Implementation

src/engine/experiments/monte-carlo.ts · 111 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4const CAPACITY = 20000;
5
6/**
7 * Monte Carlo estimation of pi: uniform darts on the unit square, the ratio
8 * inside the quarter circle converges to pi/4. The error against the true
9 * pi should fall like 1/sqrt(N) - the metric shows the actual exponent.
10 */
11export class MonteCarloExperiment extends BaseExperiment {
12 readonly id = "monte-carlo";
13
14 private xs = new Float32Array(CAPACITY);
15 private ys = new Float32Array(CAPACITY);
16 private inside = new Uint8Array(CAPACITY);
17 private darts = 0;
18 private totalHits = 0;
19 private estimate = 0;
20 private error = 0;
21
22 protected params(): ParameterDef[] {
23 return [
24 { key: "rate", label: "Darts per tick", min: 20, max: 3000, step: 20, defaultValue: 400 },
25 {
26 key: "show",
27 label: "Show darts",
28 options: [
29 { value: "recent", label: "Recent" },
30 { value: "none", label: "None" },
31 ],
32 defaultValue: "recent",
33 },
34 ];
35 }
36
37 protected onReset(): void {
38 this.darts = 0;
39 this.totalHits = 0;
40 this.estimate = 0;
41 this.error = 0;
42 }
43
44 protected onUpdate(): void {
45 const rate = this.num("rate");
46 const slots = Math.min(CAPACITY, rate);
47 // Fill the display buffer round-robin; statistics use all draws ever.
48 for (let i = 0; i < rate; i++) {
49 const x = this.rng();
50 const y = this.rng();
51 const hit = x * x + y * y <= 1 ? 1 : 0;
52 const slot = this.darts % CAPACITY;
53 this.xs[slot] = x;
54 this.ys[slot] = y;
55 this.inside[slot] = hit;
56 this.totalHits += hit;
57 this.darts += 1;
58 }
59 void slots;
60 this.estimate = this.darts > 0 ? (4 * this.totalHits) / this.darts : 0;
61 this.error = Math.abs(this.estimate - Math.PI);
62 }
63
64 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
65 ctx.fillStyle = theme.bg;
66 ctx.fillRect(0, 0, this.width, this.height);
67 const size = Math.min(this.width, this.height) - 32;
68 const ox = (this.width - size) / 2;
69 const oy = (this.height - size) / 2;
70 // Quarter circle arc (unit circle from the corner)
71 ctx.strokeStyle = theme.accent;
72 ctx.lineWidth = 1.6;
73 ctx.beginPath();
74 ctx.arc(ox, oy + size, size, 1.5 * Math.PI, 2 * Math.PI);
75 ctx.stroke();
76 ctx.strokeStyle = theme.line;
77 ctx.strokeRect(ox, oy, size, size);
78 // Recent darts
79 if (this.str("show") === "recent") {
80 const shown = Math.min(this.darts, 2600);
81 for (let s = 0; s < shown; s++) {
82 const slot = (this.darts - 1 - s + CAPACITY * 4) % CAPACITY;
83 const px = ox + this.xs[slot] * size;
84 const py = oy + (1 - this.ys[slot]) * size;
85 ctx.fillStyle = this.inside[slot] ? theme.accent : theme.viz[1];
86 ctx.globalAlpha = 0.7;
87 ctx.fillRect(px - 1, py - 1, 2, 2);
88 }
89 ctx.globalAlpha = 1;
90 }
91 ctx.lineWidth = 1;
92 }
93
94 getMetrics() {
95 return {
96 darts: this.darts.toLocaleString("en-US"),
97 inside: this.totalHits.toLocaleString("en-US"),
98 estimate: this.estimate.toFixed(5),
99 absError: this.error.toExponential(2),
100 };
101 }
102
103 describe(): string {
104 return `${this.darts.toLocaleString("en-US")} darts thrown; ${this.totalHits.toLocaleString("en-US")} landed inside the quarter circle, estimating pi as ${this.estimate.toFixed(4)} (error ${this.error.toExponential(1)}).`;
105 }
106
107 entities(): number {
108 return this.darts;
109 }
110}
111

Performance

Time per tick
O(1) per dart
Space
A 20,000-dart display ring buffer
Notes
The estimate is unbiased from the very first dart - it just takes a while to become precise.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.