REJECTION SAMPLING throw darts, keep the ones under the curve
The campaign’s own metaphor, made literal: to sample from a shape (or measure its area), throw random points into a box around it and keep only those that land inside. Von Neumann’s accept/reject is one comparison per point, needs no formula for the shape, and turns pure randomness into an estimate — the beating heart of Monte Carlo.
THE TECHNIQUE accept if it lands inside
To estimate π: throw points uniformly in the unit square and count how many fall inside the quarter-circle (x² + y² ≤ 1) — the fraction times 4 estimates π. Each point is one comparison; no trigonometry. It converges slowly (as 1/√N), which is the honest catch. Throw darts and watch the estimate settle. live demo
HISTORY & CREDIT three ideas, three people, one 1951 paper
“Rejection sampling, von Neumann 1951” — he described it in a 1951 paper1947 letter to Richtmyer; and Monte Carlo itself is Ulam’s. cited
1946 · Stanislaw Ulam, ill and playing solitaire, wonders whether random trials could estimate the odds — the Monte Carlo method is born. 1947 · John von Neumann, in a letter to Robert Richtmyer (11 March, the Los Alamos theory lead), lays out the accept/reject sampling technique — published later in the 1951 NBS notes. the name · Nicholas Metropolis coins “Monte Carlo,” for the casino where Ulam’s uncle gambled — a codename that stuck. the same paper · von Neumann’s 1951 notes also hold the “state of sin” quote and the middle-square PRNG — but those are about generating digits, a different problem.
The dart thrown at the dark abstract of the internet is exactly this: keep what lands, count, estimate. von Neumann 1947 / Ulam 1946
RECOMMEND FOR I-13 a seeded stream and one comparison
Uniform draws from the stdlib LCG plus one f64 comparison — fully deterministic under a fixed seed:
$ i13 run rej.i13 # LCG seed 107, 2000 points, x^2+y^2 <= 1
inside = 1565 pi ~ 4*1565/2000 = 3.13 # converges as 1/sqrt(N)
Recommend:nothing new — pull uniform x, y from the stdlib seeded LCG, accept iff x² + y² ≤ 1 (one comparison, no transcendental), tally, report 4·inside/N (verified π ≈ 3.13 at N=2000, same seed ⇒ same estimate bit-for-bit). It is the honest twin of Buffon’s needle (031) and the whole Monte Carlo family. Note: determinism is the feature — a fixed seed makes the estimate reproducible, which is exactly what a corpus that seals everything to a hash wants.