How to sample a probability distribution you can only score, never invert: take a random walk that accepts good steps always and bad steps sometimes, and the walk’s footprints reproduce the distribution. It runs the modern world’s statistics — and its real author spent decades uncredited.
THE TECHNIQUE propose · accept good · sometimes accept bad
Stand at x. Propose a nearby x′. If the target is higher there, move. If lower, move anyway with probability p = target(x′)/target(x). The footprints, histogrammed, become the target — even a two-humped one you never solved. live demo
HISTORY & CREDIT the coder history forgot
It is the Metropolis algorithm — but Nicholas Metropolis, by his co-authors’ own account, wrote none of it. The person who actually programmed it was long left out. cited
1953 · Equation of State Calculations by Fast Computing Machines — five authors on the MANIAC computer at Los Alamos. the real work · Arianna W. Rosenbluth wrote the actual MANIAC code and ran the computations; Marshall Rosenbluth did the physics (a key weighting insight came from Edward Teller). Metropolis (listed first) ran the computer lab — Marshall recalled “we never had a single scientific discussion with him.” the erasure · Arianna Rosenbluth left physics for family soon after; the algorithm carried Metropolis’s name for half a century before her authorship was widely restored. 1970 · W. K. Hastings generalizes it to asymmetric proposals — the “Hastings” half.
Credit where it is due: the code that runs modern Bayesian statistics was written by Arianna Rosenbluth. restored
RECOMMEND FOR I-13 two walls: randomness and exp
The accept rule needs a random draw and the target usually needs exp. I-13 has neither built in — exp is not a function:
$ i13 check accept.i13
error[E0202] semantic/semantics: unknown function `exp`
--> accept.i13:1:8 (I y <- exp(x))
Recommend: a small transcendental library written IN I-13 — not new opcodes. exp, ln, sin, cos are all bounded Taylor sums of + − * /, which I-13 already has; a fixed term count keeps them total and analyzable. The 13 counted symbols are enough — they just need a stdlib. Plus the seeded PRNG (see darts 004, 030). With those two, Metropolis–Hastings would run natively. Honest note: this recommend spends zero new alphabet and zero new opcodes — it is a library, the cheapest kind of growth. That is the right way to give a minimal language reach.