Numbers, Randomness, and Probability

Probability and numerical computing are usually taught as separate courses, yet in engineering they keep colliding: floats decide how accurately you can compute, and randomness decides whether you can compute at all. This post brings together eight related articles: how IEEE 754 packs real numbers into 64 bits, the two uses of randomness in algorithms (Monte Carlo and Markov chains), the places where probability is deliberately engineered (gacha pity, scattering experiments, card tables, and board-game rules), information entropy pricing uncertainty, and finally the Ulam spiral’s prime stripes. Every chapter can be verified hands-on in the site’s games and tools.

IEEE 754: Anatomy of a Float

0.1 + 0.2 doesn’t equal 0.3 — this is not a JavaScript bug, and not some language implementation being lazy. The doubles in Python, Java, and C all hand back 0.30000000000000004. It’s the inevitable consequence of a standard called IEEE 754 packing real numbers into finitely many bits: once you see what 0.1 actually looks like in memory, the “counterintuitive” turns into “obvious”. This chapter takes a double-precision float apart bit by bit, pinpoints where rounding error is born, meets the rest of the floating-point family along the way, and finally compresses the conclusions into a few engineering rules you can execute directly.

Hands-on versions: IEEE 754 Viewer (single and double-precision bit layout), Bitwise Calculator, Numeral.

Anatomy of a Float

How 64 Bits Split Up

The name comes from scientific notation: write a number as $\pm d_1.d_2d_3\cdots \times 2^e$, with the point floating wherever the exponent $e$ puts it.

IEEE 754’s double-precision format (binary64 — Java’s double, JS’s Number) cuts those 64 bits into three segments:

The decoding formula is one line:

One design decision is key here: the hidden bit.

A normalized binary number always leads with 1 (just as decimal scientific notation always leads with a nonzero digit), so that bit needn’t be stored. The 52-bit mantissa therefore expresses 53 significant bits.

Single precision (binary32, binary64’s younger brother) is a 1 + 8 + 23 split, bias 127, 24 significant bits. What you can inspect bit by bit in the IEEE 754 Viewer is exactly this single-precision layout.

Why an exponent field instead of spending all 64 bits on a fixed-point fraction? Because of dynamic range.

A fixed-point grid is uniform: if it represents $10^{-18}$ exactly, it can only reach somewhere around $10^{1}$. An exponent field makes the grid logarithmic, sparser the farther out you go. It holds $10^{-308}$ and $10^{308}$ both, at the cost of finite precision everywhere.

Every quirk of floating point descends from that trade: the range is bought, the precision is sold.

Rebuild the Bit Pattern by Hand in Thirty Seconds

If hearing about it isn’t enough, any browser console can take 0.1’s bit pattern apart on the spot.

The trick borrows a typed array so the same memory gets read through two lenses: a 64-bit float goes in, a 64-bit unsigned integer comes out.

1
const buf = new ArrayBuffer(8);
2
new Float64Array(buf)[0] = 0.1;
3
new BigUint64Array(buf)[0].toString(2).padStart(64, "0");
4
// "0011111110111001100110011001100110011001100110011001100110011010"

The output is exactly 64 bits: bit 1 is the sign, 0; bits 2 through 12 are the exponent field 01111111011, which reads as 1019, minus the bias for −4; the remaining 52 bits are the mantissa, and the trailing 1010 is the scar left by rounding the repeating block 1001 upward.

That trick is worth copying outright when debugging serialization precision — much faster than reading a hex dump.

Taking 0.1 Apart

The standard way to convert a decimal fraction to binary is multiply by 2 and take the integer part: keep doubling the fractional part, and the integer digits in order are the binary digits.

Run it on 0.1:

1
0.1 × 2 = 0.2  → 0
2
0.2 × 2 = 0.4  → 0
3
0.4 × 2 = 0.8  → 0
4
0.8 × 2 = 1.6  → 1
5
0.6 × 2 = 1.2  → 1
6
0.2 × 2 = 0.4  → 0   (back to the start, the cycle begins)

The remainder starts cycling from the second step, so:

That’s an infinitely repeating fraction, and the mantissa holds 52 bits.

So the repeating string is truncated at the fifty-third place, carries once under the rounding rule, and yields the bit pattern from the console above.

Run that bit pattern back through the formula and 0.1’s true stored value is:

1
0.1000000000000000055511151231257827021181583404541015625

So strictly speaking, the number 0.1 never exists inside a computer.

Only “the number nearest 0.1 that 53 binary significant bits can express”, written $\text{fl}(0.1)$.

Same for 0.2 and 0.3, each carrying its own deviation.

By contrast 0.5, 0.25, and 0.75 are exact: they are fractions of the form $k/2^n$, finite in binary by nature (0.75 is 0.11₂).

A criterion worth memorizing: a decimal fraction is exactly representable in floating point if and only if, in lowest terms, the denominator’s only prime factor is 2 (0.5, 0.125, 0.375, say).

In decimal, 0.2 is the terminating fraction 1/5, but the 5 in the denominator has no answer in binary. 5 and 2 are coprime, and multiply-by-2 never comes out even.

For the relation between radix and representability, flip the same number between base 2, 8, 10, and 16 in Numeral and the point lands much faster: changing the radix changes only the spelling, never whether the number can be “written out”.

Rounding: Where the Error Comes From

Representation Error and Operation Error

Floating-point error has two sources, and they only make sense kept apart.

The first is representation error: reals are continuous, floats are discrete, and the gap between adjacent representable numbers (the unit in the last place, ulp) near 1 is $2^{-52} \approx 2.2 \times 10^{-16}$, widening as the numbers grow.

Any real that misses the grid carries a deviation from the moment it’s stored. The 5.5×10⁻¹⁸ riding on 0.1 comes from exactly here.

The second is operation error: operate on two floats, and the mathematically exact result most likely misses the grid too, so the hardware must round once more.

IEEE 754’s guarantee is correct rounding of each single operation. The result is equivalent to computing the true value at infinite precision first, then rounding onto the grid.

Which is why every add, subtract, multiply, and divide can introduce up to half an ulp of error — and why error accumulates along the chain of computation.

The Whole Story of 0.1 + 0.2

Now let’s settle the account of why 0.1 + 0.2 doesn’t equal 0.3.

The adder takes three steps:

Step one: align the exponents. Two operands with different exponents can’t have their mantissas added directly; the smaller exponent’s mantissa shifts right until it lines up with the larger.

$\text{fl}(0.1)$ has exponent −4 and $\text{fl}(0.2)$ has −3, so 0.1’s mantissa shifts right one place.

The shift squeezes the lowest bit out. It doesn’t vanish into thin air — the hardware books it as a sticky bit for the final rounding.

Precision starts leaking from the moment the exponents align.

Step two: add the mantissas. The two aligned mantissas add into an intermediate sum of roughly 54 bits.

Step three: normalize and round. The sum’s leading bit reached $2^1$, so everything shifts right to renormalize and the exponent becomes −2. Then the rounding mode presses the result back to 53 significant bits.

Three steps done, the value is:

1
0.3000000000000000444089209850062616169452667236328125

While $\text{fl}(0.3)$ is:

1
0.299999999999999988897769753748434595763683319091796875

The two differ by one ulp: one approaches 0.3 from above, the other from below.

Strict equality is of course false.

Which is to say 0.1 + 0.2 ≠ 0.3 was settled the moment 0.1 and 0.2 were stored. The addition only airs each one’s deviation and adds a share of its own.

Why Some Additions “Look Right”

Amusingly, 0.1 + 0.3 does equal 0.4 (at least as printed).

After alignment, the two rounding directions happen to cancel, and the sum rounds back onto $\text{fl}(0.4)$.

Which shows floating-point error has no stable direction: the same shaped expression flips between “right” and “wrong” when you swap an operand, and enumerating examples by eye is a lottery.

Another famous case: formatting 1.005 to two decimals gives 1.00, because 1.005’s true stored value is 1.00499999999999989…, which rounds naturally down to 1.00.

Anyone hoping to fix that by “round first, then format” has already lost to representation error.

The pile of similar wrecks is long and all of one root: adding 0.1 ten times gives 0.9999999999999999; 0.1 + 0.7 times 10 isn’t 8 (0.7999999999999999 first, then 7.999999999999999); 1 − 0.9 = 0.09999999999999998.

None of them should surprise you. They’re just 0.1 + 0.2 in a change of costume.

Cancellation

Multiplication and division’s relative error is at most half an ulp per step; the relative error that actually causes disasters comes from subtracting nearby numbers: subtract two nearly equal numbers and the significant digits wipe each other out at scale, leaving error in charge of whatever digits remain.

The classic case is the quadratic $x^2 - 10^8 x + 1 = 0$, with roots around $10^8$ and $10^{-8}$.

Compute the small root with the quadratic formula and the numerator is $-b - \sqrt{b^2 - 4}$, where $\sqrt{b^2-4}$ differs from $10^8$ by only $2 \times 10^{-8}$. At the $10^8$ scale double’s ulp is about $1.5 \times 10^{-8}$; minuend and subtrahend each round once, and the computed difference is simply untrustworthy.

The stable fix detours through Vieta: compute the large root first (subtraction becomes addition, no cancellation), then derive the small root from $x_1 x_2 = c/a$.

Numerical analysis calls it catastrophic cancellation, and the engineering signal is a formula containing “the difference of two large numbers” where that difference is several orders of magnitude smaller than the numbers themselves. See it, restructure the expression.

The Default Rounding Mode

IEEE 754’s default rounding mode is round to nearest, ties to even: find the nearest representable number, and when exactly halfway, pick the one whose last mantissa bit is even.

Why not round half up, the way grade school does? Because always rounding up gives the error a systematic bias — over a long computation it goes larger every time, and error accumulates on one side.

Ties-to-even swings symmetrically between up and down, statistically near-unbiased over the long run.

The standard also defines three directed modes — toward zero, toward positive infinity, toward negative infinity — for interval arithmetic and certain financial cases, but general computing uses the default almost exclusively.

The Edges of the Exponent

The Cliffs of the Range

The largest finite double is $(2 - 2^{-52}) \times 2^{1023} \approx 1.8 \times 10^{308}$. Finite results beyond it round to ±Infinity (overflow).

Downward, the smallest normal number is $1.0 \times 2^{-1022}$. Below that, numbers lose the hidden bit’s bonus and enter the subnormal range: the mantissa may start with 0, the exponent is pinned at −1022, and the grid thins all the way to $2^{-1074}$ before true zero.

Subnormals exist for gradual underflow — letting relative error degrade slowly near underflow instead of cliff-diving — at the cost that operations on them may run an order of magnitude slower on old hardware.

Both ends of the exponent field are reserved for special values, a table worth memorizing:

NaN carries a whole logic of its own: NaN compared with anything returns false, including NaN compared with itself.

Which is why NaN checks need a dedicated isNaN rather than an equality operator. At the bit level NaN is a family of numbers (exponent all 1s, mantissa nonzero, the mantissa bits called the payload), and no comparator can assert that two NaNs with different payloads are “equal”.

Signed zero has its own pit: −0 equals +0 under ==, yet 1 divided by −0 gives −Infinity and 1 divided by +0 gives +Infinity. Division sees through them.

Infinity’s arithmetic, at least, matches the limits your intuition expects: adding a finite number still gives Infinity, and Infinity minus Infinity gives NaN (an indeterminate form).

Single precision’s cliffs are far steeper: overflow at $3.4 \times 10^{38}$, and 24 significant bits mean that from 16777217 (that is, $2^{24} + 1$) on, consecutive integers stop fitting.

In float32, 16777216 plus 1 is still 16777216.

Graphics and machine learning lean on half precision (fp16), where the edges are more dramatic still: the maximum is only 65504, and anything beyond overflows.

Throw a number into the IEEE 754 Viewer to see the single-precision layout, then hand-compute the exponent field’s value — the feel for these edges beats reading this post ten times.

One Family’s Trade-offs

IEEE 754 is a family, and its members’ division of labor is worth knowing, because picking the wrong member is itself a class of incident.

binary16 (fp16): 5 exponent bits plus 10 mantissa bits, small range, coarse precision, but storage and bandwidth halved. A regular in deep-learning inference, where weights run to hundreds of millions and precision is traded for throughput.

The later bfloat16 goes further: keep fp32’s 8-bit exponent, cut the mantissa to 7 bits, sacrifice precision to hold dynamic range, so training overflows and underflows less readily.

Both confirm the other end of the exponent-mantissa seesaw: precision and range can be reallocated on demand.

The other end is finance.

Binary floats can’t represent 0.01 exactly by nature, so serious accounting systems don’t use them.

Java’s BigDecimal is “arbitrary-precision decimal plus a scale”, and IEEE 754-2008 formally admitted decimal floating formats such as decimal128. The mantissa is stored in decimal digits, so 0.01 is exactly 0.01.

Databases’ DECIMAL type and Python’s decimal module belong to the same lineage.

The selection rule therefore fits in one sentence: scientific computing takes binary floats (fast, hardware-supported), money takes decimal (exact, auditably explainable), and the statistics and graphics in between hinge on whether the relative error is tolerable.

Engineering Rules

Comparison: Never Use Strict Equality

Rule one is common knowledge: compare floats with a tolerance.

Writing that tolerance, though, has an equally high error rate.

Take the language’s built-in minimal-precision constant (JS’s Number.EPSILON, i.e. $2^{-52}$) as an absolute error threshold and it means something only near 1. Past that it’s decorative: at the $10^8$ scale the gap between two adjacent doubles is already nearly eight orders of magnitude larger.

The general form is relative error:

1
function nearlyEqual(a, b, eps = 1e-9) {
2
  return Math.abs(a - b) <= eps * Math.max(Math.abs(a), Math.abs(b), 1);
3
}

The max(..., 1) keeps the comparison degrading to absolute error near zero, avoiding the over-generous tolerance that dividing by a tiny number would give.

Convergence checks in iterative algorithms (Newton’s method, gradient descent) should all take this form, and remember to cap the iteration count as well.

In the floating-point world “until it converges” is a loop condition that must have an upper bound, because rounding error can leave an iteration hovering around the threshold forever.

Accumulation: Order Matters

Associativity of addition doesn’t hold in floating point: 0.1, 0.2, 0.3 added in two different orders give different results.

Generalize to summation: the sum of a million numbers depends on the order you sum them in.

It’s one reason the same program produces subtly different numbers on different machines and at different optimization levels (compilers are entitled to reorder floating-point chains unless explicitly forbidden).

Two classic symptoms worth remembering.

One, big numbers eat small ones: add 1.0 onto $10^{16}$ repeatedly and nothing moves. The 1.0 was rounded away long ago.

Two, summing same-signed numbers from small to large usually errs less (get the small ones aboard while the books are still clean).

For sums that need precision, the standard weapon is Kahan compensated summation: keep a variable that books the part rounded away at each step and add it back next time.

1
function kahanSum(xs) {
2
  let sum = 0, c = 0;               // c is the ledger of the low bits we dropped
3
  for (const x of xs) {
4
    const y = x - c;
5
    const t = sum + y;              // rounding happens here
6
    c = (t - sum) - y;              // back out what this step lost
7
    sum = t;
8
  }
9
  return sum;
10
}

The price is four times the operations; what you get is error pressed from a magnitude that grows linearly with the term count back to one independent of it.

Nearly every statistics or linear-algebra library’s summation kernel carries a variant of it (pairwise summation is a different, tree-shaped idea).

The more practical rule for everyday business is the opposite one: if you can avoid accumulating floats, don’t accumulate.

Money in Integers, Counts in Integers

Where money is involved, use integers in the smallest currency unit. Cents.

Store 1.10 yuan as 110; add, subtract, multiply, and divide as integers, and format only at final display.

Same logic: statistics, ordinals, inventory counts — quantities that are naturally discrete — shouldn’t touch floats.

A companion language fact is worth knowing too: JavaScript’s bitwise operators truncate operands to 32-bit signed integers before computing, so a number beyond $2^{31}$ quietly flips sign when it enters a bitwise operation.

When tracking that kind of bug down, the Bitwise Calculator shows each bitwise result side by side in decimal, binary, and hex — much faster than guessing in the console.

One more number to memorize: the safe integer limit $2^{53} - 1$ (Number.MAX_SAFE_INTEGER).

It’s the other face of the hidden-bit account: 53 significant bits store every integer up to $2^{53} - 1$ exactly, and beyond that adjacent integers begin sharing one float.

Long integer IDs — snowflake IDs, database auto-increment keys past a hundred million — travel as strings or BigInt, never through Number.

A JSON parser reading an out-of-safe-range integer into a distorted float is the classic pit of frontend-backend integration.

When Floating Point Is Right

Having drawn the boundary, fairness also requires saying this: for scientific computing, graphics rendering, signal processing, and statistical inference, binary floats are the correct tool.

The reason is that their view of error is naturally relative: a $10^{-9}$ relative error in a physics simulation means nothing, half a pixel in rendering means nothing, and measurement noise already exceeds rounding error by several orders of magnitude.

Floats spread 64 bits across a $10^{\pm 308}$ dynamic range, which is precisely what such problems were built for.

So the engineering judgment isn’t “floats bad, integers good” but ask first what shape of error is acceptable: if the answer must be exact to the last cent (money, counts, IDs), use integers or a decimal type; if it only needs to be relatively accurate (physical quantities, gradients, coordinates), use double with confidence and spend your attention on controlling error propagation.

Three Derived Puzzles

The best test of understanding is an edge case.

All three below are phenomena that have shown up in real code, and every answer follows from the rules above; try them yourself before reading the solutions.

Puzzle one: 0.5 × 3 is exactly 1.5, yet 0.1 × 3 isn’t 0.3 — where’s the difference?

0.5 is $2^{-1}$, born on the grid. 0.5 × 3 = 1.5 = $2^{-1} \times 3$, which 53 significant bits hold with room to spare, no rounding anywhere.

0.1 already carries a relative deviation on the order of 5.5×10⁻¹⁷ from storage, and multiplying by 3 multiplies that deviation by 3 too, landing the result on a different grid point near 0.3.

Same multiplication: one is exact at the source, the other is in debt at the source.

Whether a result is exact depends on whether the operands are exact, not on the operation itself.

Puzzle two: what does rounding -0.5 (Math.round) return?

The answer is −0, a negative zero.

The rule says round half up, and for -0.5 “up” is 0; but IEEE 754 has two bit patterns for zero, and this path produces the negative one.

It compares strictly equal to the ordinary 0, but shows its true face as a divisor: 1 divided by −0 is −Infinity.

The incidental lesson: any “round half up” implementation detail needs its direction spelled out in the floating-point world, because “exactly halfway” numbers are more common than you’d think.

Puzzle three: what does parseInt(0.0000001) return?

Not 0 — 1.

Because parseInt takes only strings, 0.0000001 is first implicitly converted to a string. Float-to-string switches to scientific notation for very small values — “1e-7” — and parseInt parses digits from the front, stopping at the e, giving 1.

The lesson here isn’t about parseInt but about the string representation of a float carrying rounding of its own.

Converting to string means “pick the shortest spelling that round-trips uniquely” — a lossy window onto the float, and treating it as the number itself is how you step on the rake.

Floats settle how numbers are stored; in many problems the numbers haven’t been computed yet — they are produced by random processes. The next chapter splits randomness in the algorithmic world into its two uses: computing something deterministic with randomness, and packing a random process into a matrix.

Randomized Methods: Monte Carlo and Markov Chains

Randomness has two sharply different uses in the algorithmic world.

The first: using randomness to compute something deterministic. The answer is a fixed value (π, say), and randomness is only the means of getting there — that is the Monte Carlo method.

The second: packing a random process into a matrix. The future is itself random, and what we want to study is its long-run behavior — that is the Markov chain.

The two lines look unrelated, and they end up meeting at MCMC: sampling along a Markov chain becomes Monte Carlo’s strongest form for attacking high-dimensional problems.

Hands-on versions: Monte Carlo for π, Buffon’s needle, Markov chain visualization.

First Half: Monte Carlo

The Method Itself: Area Is Probability

Scatter N points uniformly into a unit square, count the fraction p that lands inside the quarter circle, and π ≈ 4p.

The game is so simple that it hardly looks like honest work, yet the method behind it holds up half of financial pricing, particle physics, graphics rendering, and Bayesian statistics.

The quarter circle sits inside a square of side 1; a random point (x, y) thrown uniformly into the square lands inside the circle if and only if x² + y² ≤ 1.

Let the probability of that event be p; then p = circle area / square area = π/4.

The Bernoulli law of large numbers guarantees that the hit frequency p̂ over N trials converges in probability to p, and so

That plain.

Monte Carlo’s general recipe is right here: disguise the quantity to compute as the expectation or probability of some random experiment, then let massive repetition squeeze frequency into probability.

It is needed because many high-dimensional integrals (path-dependent options in finance, partition functions in physics, the rendering equation) refuse analytic integration, and numerical grids explode with dimension.

The cost of random sampling, by contrast, does not grow exponentially with dimension — Monte Carlo’s only, but decisive, advantage.

The Price: The Cruelty of the √N Law

Hit or miss is a Bernoulli trial, and the estimator’s standard error is

Translated into the error on π: to gain one more correct digit (error down tenfold), N has to be multiplied by 100.

Run the numbers once and it becomes tangible:

A million points still only pin down three decimals.

That is Monte Carlo’s ceiling: it handles the dimension explosion, but it never delivers high precision.

Where ten significant digits are required it does not even qualify; where three will do but the dimension is 500, it has no rival.

Whether to pick it starts with the precision requirement.

(By the way, one common misconception: the error is statistical fluctuation, not systematic bias. The estimate wobbles around π instead of leaning to one side; raising N only compresses the wobble interval.)

From Scatter to Integral

Rewrite the dart-throwing estimate of π in the language of integration and Monte Carlo’s general shape appears.

The inside test I(x,y) is 1 inside the circle and 0 outside, so π = 4·E[I(U)].

U is a uniform random variable, and estimating π is estimating the expectation of a random variable.

An ordinary definite integral works the same way: ∫f(x)dx ≈ (b−a)·mean(f(U)) — swap “sweep a grid, evaluate the function” for “sample at random, average”.

This view ties variance reduction back to its source: those are not special dart-throwing tricks but general statistical tools for lowering the variance of an estimator, valid for any expectation estimate.

It also explains where the dimension problem really comes from: a grid’s node count grows exponentially with dimension (100 cells per axis, ten axes make 100²⁰ points), while the error of random sampling depends only on the total sample count N and is independent of dimension.

The higher the dimension, the bigger Monte Carlo’s edge.

π is a one-dimensional problem, so opening with it is an ox cleaver swung at a chicken, for the audience.

Variance Reduction

Since σ ∝ 1/√N is governed by the variance p(1−p), making the variance small is money in the bank.

There are three classical techniques, all under one idea: cancel the known part, randomize only the unknown part:

1. Antithetic variates: for every point (x, y) thrown, also average its “mirror estimate”, so the fluctuations on the two sides cancel each other out;
2. Conditional expectation: whatever part of the landing statistics can be integrated analytically, integrate it out and simulate only what is genuinely random — handle the “x direction” analytically and randomize only y, say, and the variance drops by a factor on the spot;
3. Importance sampling: throw points from a distribution shaped close to the integrand, so each sample’s contribution to the variance evens out.

On the π toy these techniques shrink the error coefficient several fold.

The coefficient, mind; the √N law itself does not budge.

Variance reduction changes the constant, never the exponent.

That is the dividing line between the changeable and the unchangeable in the Monte Carlo method.

Random Number Quality and Parallelism

Random number quality.

“Random” inside a program is pseudorandom. A deterministic seed runs out a deterministic sequence.

That is good news for Monte Carlo (reproducible, debuggable), and it imposes one baseline requirement: the sequence’s statistical properties have to pass (long enough period, even enough distribution, low correlation).

The default generator in a language’s standard library is fine for toys; serious simulation wants a better one.

One step further are quasi-random sequences (low-discrepancy sequences such as Sobol): give up “independent randomness” for deterministic points laid out deliberately evenly, and on smooth integrands the error improves from 1/√N to nearly 1/N.

Standard kit for high-dimensional financial pricing, at the price of possibly failing on jagged integrands.

Parallelism.

Monte Carlo is born parallel: samples are independent of one another, so a million points spread over a hundred machines at ten thousand each, then a weighted average of the estimates.

But read the ledger for what it is: the merged estimator’s variance is the sum of the parts’ variances, and the error still shrinks only by the √N law in the total sample count N.

Parallelism changes wall-clock time, not the economics of “one more digit, a hundred times the samples”.

Parallelism buys time, variance reduction buys precision; do not mix the two roads.

The More Classical Version: Buffon’s Needle

Buffon posed the problem in 1777, two hundred years before “Monte Carlo”, but the skeleton is identical.

Throw a needle of length l at random onto a set of parallel lines spaced t apart (l ≤ t); the probability that it crosses some line is

Hence π ≈ 2lN/(t × number of crossings).

People really did estimate π by throwing needles by hand, and the most famous report is Lazzarini’s in 1901: 3408 tosses, π ≈ 355/113, correct to six decimals.

Suspiciously good.

The usual reading in probability circles is that either he stopped at exactly the right moment (one more toss breaks 355/113) or he never ran the experiment at all.

The anecdote is a fine lesson: a “good result” from a random experiment, without an independence check, is only a good story.

Its teaching value: the same √N law, in a more laborious experiment.

The hit event is rarer, the variance larger, the convergence slower.

Playing the two side by side is the best way to feel the sentence “experimental design sets the constant”.

To close the first half: Monte Carlo trades freedom from dimension for a ceiling on precision, and the √N law is the price tag on that trade.

And all of its samples share one premise: mutual independence.

Relax independence, let the samples evolve along a chain, and the protagonist of the second half walks on.

Second Half: Markov Chains

Definition: One Matrix Is One Chain

The Markov chain belongs to that species of tool with an intimidating name and a minimal core: the distribution of the next state depends only on the current state, not on anything earlier.

That one memoryless assumption cuts away the entire complexity of a time series, and still props up PageRank, hidden Markov models, and countless text-generation toys.

Let the system have n states; the entry p_ij in row i, column j of the transition matrix P means “currently in state i, probability of going to state j next”.

Every row must sum to 1 (you have to go somewhere).

The Markov property (memorylessness) takes exactly one line of formula:

Given the present, the future is independent of the past.

The assumption is strong to the point of brusqueness. But many systems really do behave roughly like this: next week’s weather mostly looks at this week’s, a board position mostly at the current board, a page hop mostly at the current page.

A Toy Example: The Sun-Rain Model

Two states {sunny, rainy}, transition matrix:

1
        sunny  rainy
2
sunny     0.9    0.1
3
rainy     0.5    0.5

Sunny today, 0.1 chance of rain tomorrow. Rainy today, 0.5 chance of turning sunny tomorrow.

Question: in the long run, what fraction of days are sunny?

The intuitive attempt to “convert by proportion” usually answers wrong. The right tool is the stationary distribution.

The Stationary Distribution

The stationary distribution π is a row vector satisfying π = πP.

Take one more step and the distribution is unchanged.

For an ergodic chain (every state reaches every state, and no periodicity), this distribution exists, is unique, and no matter which initial state you start from, the distribution after t steps converges to it.

That is the chain forgetting where it started.

The sun-rain model’s stationary distribution: solve π_sunny = 0.9π_sunny + 0.5π_rainy together with π_sunny + π_rainy = 1, and π = (5/6, 1/6).

In the long run, 83% of days are sunny.

Note that the number is independent of whether today is sunny or rainy. The influence of the initial condition decays exponentially with every transition.

No need to actually solve the linear system: multiply P by itself many times (every row of $P^k$ tends to π), or just simulate tens of thousands of steps and count frequencies; both converge to the same answer.

The convergence can be hand-computed one step at a time: the first row of P² is (0.9×0.9 + 0.1×0.5, 0.9×0.1 + 0.1×0.5) = (0.86, 0.14).

The probability of sunny today and rain the day after tomorrow has moved from 0.1 to 0.14, already closing on (5/6, 1/6) ≈ (0.83, 0.17).

Each multiplication brings the two rows closer, until they merge into the same vector.

Two Common Misconceptions

• “Memoryless means completely random”. Wrong. A chain’s state distribution can be highly structured. The stationary distribution is that structure. Memoryless only says history supplies no extra information, not that transitions have no preferences;
• “Periodic chains converge too”. Wrong. If the chain is periodic (a perfect bipartite graph, say, oscillating forever between two groups of states), $P^k$ does not converge; it converges to π only in the averaged sense. Checking ergodicity (irreducible + aperiodic) is a necessary step before applying the stationary distribution.

Absorbing Chains

Ergodic chains get everywhere; another important family goes the other way: an absorbing chain has a few states that, once entered, are never left.

The classic is the gambler’s ruin model: capital drifts up and down in steps of 1, and the game stops at ruin (0) or at the target (N). 0 and N are absorbing states.

The stationary distribution of such a chain degenerates to a single answer: “in the end, everything sits in the absorbing states”.

But the questions that matter become two others: how many steps until absorption on average (the expected duration) and which absorbing state takes you (ruin probability versus success probability).

Both have clean linear-algebra answers: partition the transition matrix into transient and absorbing blocks, and the power sum of the transient block (the so-called fundamental matrix) gives the expected number of steps directly, while the absorption probabilities come from one matrix multiplication.

Gambler’s ruin also solves analytically: in a fair game the probability of ruin starting from k is (N−k)/N.

In expectation, “the longer you gamble the more surely you lose” is not a moral judgment but the result of inverting a matrix.

Absorbing chains are the complete answer to “what do you do when ergodicity fails”, and the shared skeleton of queueing systems, actuarial work, and population extinction.

Three Big Jobs on One Skeleton

Text generation: swap the state for a word or a character, take transition probabilities from corpus counts (how often “Chamber” follows “Red”), and you can generate a passage that looks plausibly like the thing.

A second-order model (looking at the previous two words) improves the output immediately. Which exposes the ceiling of the Markov assumption: language has long-range dependencies.

There is also a pitfall with immediate effect: a bigram that never appeared in the corpus has probability 0, and generation hits a wall one step in — hence smoothing. Carve a small slice off the total probability and share it out to unseen combinations.

Yet it was exactly this toy that evolved, step by step, into today’s language models: swap “the previous state” for “a context vector”, the counts for a neural network.

The next-word prediction framework has not changed since the 1950s.

PageRank: web pages as states, links as transitions (each page splits its probability evenly among its out-links), and the random walker’s stationary distribution is each page’s weight.

The damping factor 0.85 in the original formula is an engineering patch: jump to an arbitrary page with probability 0.15, which forces the chain to be irreducible and aperiodic and guarantees that the stationary distribution exists and is unique.

Mathematically it is precisely the step that removes dangling nodes and spider-trap islands.

MCMC runs the stationary distribution theorem backwards: to sample from a complicated distribution whose expression you cannot write down, construct a Markov chain that has it as its stationary distribution, run to convergence, then walk along the chain.

The chain’s trajectory is the samples.

This is the answer to the first half’s open question: the place where Monte Carlo is hemmed in by the √N law and by dimension is exactly “how to draw samples inside a complicated distribution”.

Sampling along a chain makes feasible the high-dimensional problems that independent dart-throwing cannot touch, and all of modern Bayesian computation rests on it.

The two lines converge here: the Markov chain manufactures the right randomness, Monte Carlo turns that randomness into the quantity you want.

Five Steps from Corpus to Generator

The text-generation toy is shorter to implement than expected; five steps:

1. Segment: split the corpus by word or by character. Character-level models have few states and can connect anything, but the sentences come out more broken; word-level models are more fluent but tend to “walk only the old roads the corpus already traveled”. Granularity is itself a pair of trade-offs;
2. Count: sweep the corpus once, tally how often each (current word, next word) pair occurs, and store the counts in a table;
3. Sample: no need to actually normalize the counts into probabilities. Draw the next word at random weighted by counts; equivalent, and one floating-point step cheaper;
4. Assemble: start from an initial state (the start of a sentence, or any word) and loop “look up the table → sample” until you draw an end-of-sentence symbol or hit the length cap;
5. Patch the holes: on a dead end with “no successor” (the corpus never used this word mid-sentence), fall back to a random restart or draw the highest-frequency word.

The two switches on generation quality both sit in steps 1 and 2: segmentation granularity, and the order (first order looks at one word, second at two).

Raise the order by one and fluency jumps immediately, but the corpus requirement grows exponentially and sparsity worsens (back to smoothing again).

This seesaw of order versus data volume is exactly the Markov generator’s teaching value: ten lines of code in, half the history of language models out.

Feeling Convergence Hands-On

In the Markov chain visualization you can adjust transition probabilities and watch the distribution flow with the steps.

Two phenomena deserve a deliberate look: convergence speed — the more connected the transition matrix (the smaller the second-largest eigenvalue), the faster it forgets the initial condition; and setting one transition probability to 0 to manufacture a “half-irreducible” chain, to watch how the distribution gets stuck.

Both are more intuitive than any formula.

Markov chains don’t live only in textbooks. Swap the state for a pity counter and absorption for a guaranteed hit, and you get the most intricate probability design in commercial products — the next chapter watches gacha pity sculpt a distribution.

Gacha Pity: Sculpting a Distribution

Naked independent probability is a beast nobody can ride: a 0.6% per-pull rate means nearly three in ten players walk away from two hundred pulls empty-handed, and no commercial product dares serve that experience to users as-is.

The whole craft of gacha design is, at bottom, sculpture on a probability distribution — cut the long tail, raise the midsection, keep the narrative alive, and finally package “luck” as “a budget you can plan”.

Hands-on versions: the Gacha Simulator, the Slot Machine, and the Permutation / Combination calculator.

Naked probability

The plainest gacha model has exactly one parameter: each pull independent, the probability constant at $p$.

The probability that pull $n$ is exactly the first hit is the first $n-1$ pulls all missing and pull $n$ landing:

This is the geometric distribution, and both its expectation and its variance have closed forms:

Substitute $p = 0.6\%$ and the expectation is 166.7 pulls.

That figure misleads badly, because the geometric distribution is heavily right-skewed: the median is only $\ln 0.5 / \ln 0.994 \approx 116$ pulls — half of players hit far earlier than the “expectation”, while a handful of spectacularly cursed accounts drag the mean out past the median.

One look at the tail shows where the trouble is: the probability that the first 199 pulls all miss is $0.994^{199} \approx 30.2\%$, and the first 299 all missing is still about 16.5%.

Run on naked probability, then, and one player in three eats two hundred empty pulls.

In expectation terms this is still “normal variance”, but landing on one specific player it is a disaster — and no player lives their life at the mean.

A pity-free reference point

To see what “raw, unsculpted randomness” looks like, the best reference object is a slot machine with no pity at all.

The site’s Slot Machine mini-game is the minimal model: three reels of six symbols each, landing independently and uniformly; three of a kind pays the jackpot (10× face value), exactly two pays the small prize (2× face value), everything else pays nothing.

Spread its distribution out and compute: three of a kind is $6/6^3 = 1/36 \approx 2.8\%$, exactly two is $3 \times 6 \times 5 / 216 = 5/12 \approx 41.7\%$, and nothing at all is $5/9 \approx 55.6\%$.

The amusing part: counting symbols at face value (5 to 100), the machine returns about 36 for every 10 fed in.

The expected value is positive for the player, because this is a teaching toy and not an economic simulation.

But at the level of experience the thing to look at is not the expectation but the shape: more than half of all rounds return nothing, and the payout concentrates into less than 3% of moments.

Losing streaks are the norm, bursts ride on vanishingly rare events — that is the daily weather an untamed distribution hands a player.

Every pity mechanism ever built exists to fix this shape.

Hard pity

Hard pity is the simplest possible rule: after $N$ consecutive pulls without a hit, pull $N$ is forced to hit.

The distribution goes from “a geometric with an infinite tail” to “a truncated geometric”:

The closed form is remarkably clean — it is just the survival probabilities summed:

Plug in $p = 0.6\%$, $N = 90$: $0.994^{90} \approx 0.582$, so $E[N] = (1-0.582)/0.006 \approx 69.7$ pulls.

Against the 166.7 of naked probability, one stroke removes 58%.

And all 58% of it comes out of the tail: pity changes none of the first 90 pulls’ probabilities, it merely compresses every “my hit would have come after pull 91” ending down onto pull 90.

The formula also hides a counterintuitive fact: $1-(1-p)^N \approx 41.8\%$ is the probability of hitting naturally before pity fires.

In other words, at a rate like 0.6% the majority of hits (58.2%) are delivered by pity itself, not by luck showing up.

Pity is not a bolt-on welfare program; it is the main delivery channel.

Designers know this perfectly well. That is why the published consolidated rate sits so far above the per-pull rate — a thread we pick up in the soft-pity section.

The cost of hard pity is just as visible: it turns pull 90 into a certain event.

Certain events have no pulse. If everyone knows it is “90 pulls at most”, then every pull after the sixtieth is emotionally nothing but a countdown.

Which is why hard pity is never the whole answer in practice — the probability itself needs a ramp grafted onto it.

Parameter sensitivity

Hard pity has another systemic effect that is easy to miss: it compresses the leverage of changes in the base rate $p$.

With the same 90-pull cap, run a comparison set through the expectation formula $(1-(1-p)^{90})/p$:

Without pity the expectation is strictly inversely proportional to $p$ — full leverage.

With pity in place, cutting $p$ from 1% to 0.6% moves the expectation only from 59.5 to 69.7 (about 17%), far short of the 67% climb under naked probability.

The reason is that earlier fact: the smaller $p$ gets, the more delivery depends on pity itself, and pity is a fixed quantity.

The base rate gradually demotes from “decider of the expectation” to “a small correction term inside the pity window”.

This explains the confidence behind round after round of base-rate cuts: as long as the pity cap stays put, the expected loss is bounded.

It also explains why, when arguing about gacha pricing, staring at pity parameters gets closer to the truth than staring at the per-pull rate.

Soft pity

Soft pity’s idea: before hard pity fires, let the probability climb linearly with the number of consecutive misses.

A widely used parameterization keeps $p = 0.6\%$ for the first 73 pulls, then adds 6 percentage points per pull from the 74th:

The expectation of this model can be worked out by hand with the survival function.

Let $s_k$ be the probability that the first $k$ pulls all missed; $s_k = 0.994^k$ up to pull 73, so $s_{73} = 0.994^{73} \approx 0.644$.

From pull 74 on, multiply term by term by $(1-p_k)$:

The expectation is the sum of all survival probabilities: the first 73 pulls contribute $(1-0.994^{74})/0.006 \approx 59.9$, the 16 ramp terms add about 2.4, giving

From 166.7 under naked probability down to 62.3, the expectation is cut by 63%.

Better still is the shape of the distribution: the mode of delivery sits around pull 77, and the ramp region (after pull 74) accounts for about 64% of all hits.

The player’s subjective experience shifts from “nowhere in sight” to “the closer I get, the more it feels due”, while the expectation is pressed down almost entirely by this 17-pull ramp. The low-probability narrative of the first 73 pulls is left untouched.

That is the essence of soft pity: the expectation is the back-office ledger; the front of house only stages the drama of a climbing probability.

Two numbers in collusion

Turn the 62.3-pull expectation into a per-pull consolidated rate and you get $1/62.3 \approx 1.6\%$.

So every gacha system carries two numbers that look contradictory: the 0.6% on the promo page (base per-pull rate) and the roughly 1.6% on the rules page (consolidated rate including pity).

Both are true, both are compliant, and both describe the same distribution from different sides.

Odds regulation requires publishing the drop rates and the pity rules, so designers have to write this piecewise model verbatim into the notice.

All a player needs to understand is that the per-pull rate describes the start, the consolidated rate describes the end, and the ramp in between joins them.

Quantiles are the real budget

The 62.3-pull expectation is also routinely misread: it is not the point by which half of players have hit.

As computed above, the median is only 76 pulls. The distribution is right-skewed, and a few extreme individuals drag the mean rearward.

When planning resources — how many pulls should I save up — the right question is never “how many on average” but “within how many pulls have nine in ten players hit”, which is to say, the quantiles.

Query the soft-pity survival function tier by tier and set it beside the naked model:

Under naked probability, 1% of players need more than 766 pulls to see their first gold.

That unbounded tail is the entire justification for pity.

The ramp presses it entirely below a 90-pull ceiling, so the 99th percentile falls from 766 to 83 — an order of magnitude gone.

Note the other contrast between the two distributions: the soft-pity quantile curve is squeezed together. The eight slots from pull 76 to pull 83 cover the outcomes of more than half of all players (cumulative probability rushing from 47% straight to 99%), so most experiences look much alike.

The naked model spreads the long tail flat: every player’s fate is wildly different.

In choosing the former, the designer chooses predictable frustration over unpredictable despair.

Frustration converts into spending; despair only converts into uninstalls.

The grand pity

Limited banners add a second layer of sculpture: after a top-rarity (5★) hit there is only a 50% chance it is the featured UP character; lose the coin flip and the next 5★ is guaranteed UP (the so-called grand pity).

That turns the expected pulls to obtain UP into

Note that the full state space of this system is two-dimensional: (pity counter, whether the guarantee is active).

Each pull’s probability depends only on the current state, not on anything earlier. That is the skeleton of a Markov chain, except the states here are counters built by the designer rather than arising on their own.

The process of chasing UP is a two-stage absorbing chain: a loss is transient, UP is absorbing, and each absorbs with probability one half.

The previous chapter, Randomized Methods, went through transition matrices and stationary distributions; gacha systems are the most commercialized site of that theory — designing the whole chain’s transition table is designing the entire paying experience.

Solving the absorbing chain with matrices

The chase-UP chain can be solved with the standard absorbing Markov chain toolkit.

Take two states: lose (transient) and UP (absorbing).

From a loss, the next step enters UP with probability 0.5 and loses again with probability 0.5. The transient submatrix is a single cell, $Q = (0.5)$, so the expected-visits matrix is $N = (I-Q)^{-1} = 2$.

Starting from the loss state, absorption takes on average 2 more 5★ windows (counting the current one), which converts back to $1.5 \times 62.3 \approx 93.4$ pulls.

With one cell the solution degenerates into primary-school division, but its value is extensibility.

If the rule becomes two consecutive losses guaranteeing the hit (common in three-way UP pools), the state space grows to three and $Q$ becomes $3 \times 3$, and the same $(I-Q)^{-1}$ hands back the answer unchanged.

As the rules get more complicated, the Markov toolbox needs no upgrade.

The 50/50 also manufactures a deliberate wealth gap: half of players end the fight in 62 pulls, the other half grind through two full cycles.

In pure product logic that variance is a defect that should be eliminated; here it is a social topic kept on purpose.

“One pull, one miracle” and “180 pulls, two lost flips” are both shareable material, and removing it — refunding half the resources on a loss, say — would flatten every player’s ending into the same one and cost half the stories.

Who rolls the dice

Every model above assumes the dice are rolled server-side, but pull the camera back to the engineering layer and that assumption is itself a design decision.

In an architecture where the client rolls and then reports, the probability table lives in the player’s hands. Decompiling the client, extracting the table, or just tampering with the submitted result are all operations within a controllable cost.

Server-side adjudication pulls the randomness back into a black box, at the cost of signed requests, replay protection, and rate limiting.

For a sense of the real intensity of that fight, see the reverse-engineering note on Obtaining the miyoushe Salt (LK2 & K2): to call miyoushe’s API you have to dig the salt material for request signing out of the APK layer by layer.

That is the front line of the “results adjudicated server-side, every request signed” route.

However elegant a gacha system’s probability design, if the dice sit on the client, every model is made of paper.

Distribution design solves fairness; interface security solves cheating; you need both.

Pseudo-randomness

Pity is hard reshaping of a distribution; a finer family of tools goes by PRD — Pseudo Random Distribution.

Dota 2’s critical strike is the classic application: the hit chance on attempt $n$ is $C \cdot n$, where $C$ is a constant below the nominal rate, and the counter resets on any hit.

A nominal 25% crit corresponds to $C \approx 8.5\%$: 8.5% on the first swing, 42.5% on the fifth after a losing streak, and the long-run frequency still converging to 25%.

But the variance of the individual experience is far smaller: marathon dry streaks nearly vanish, and the intuition that “the longer the streak, the more it is due” is quietly honored by the system.

Why can’t $C$ simply be the nominal rate? The arithmetic says why.

If $C = 0.25$, the first attempt hits 25%, the second 50%, the third 75%, the fourth 100%, and the expected number of attempts is $1 \times 0.25 + 2 \times 0.375 + 3 \times 0.28 + 4 \times 0.094 \approx 2.2$.

That is a long-run frequency of about 45%, far above the nominal 25%.

So $C$ has to be solved numerically: the constraint is that expected attempts equal $1/p$, and for 25% the solution is $C \approx 8.5\%$.

This awkward-looking mechanism is really an expectation preserver. It redistributes the distribution of when a hit lands while nailing the long-run books of how often.

Which is the precise meaning of “pseudo-random”: the shape of the randomness is fake; the quantity is real.

These tools line up on a spectrum: independent Bernoulli at one end (true random, maximum variance), PRD in the middle (gentle correlation), counter-based pity at the other end (strong negative correlation, variance pressed to its floor).

All three can share an identical long-run expectation while the player experience differs beyond recognition.

Here the behavioral-economics soundtrack fades in: human intuition about randomness is simply wrong. We expect uniformity even in small samples, and cry fake at any cluster in a truly random sequence.

The designer’s job is not to correct that intuition but to manufacture randomness along its grain: make the system “more like the randomness in players’ heads” than randomness itself.

Set against PRD are purely perceptual phenomena: warm-up pulls, lucky hours, burning incense before pity.

Players forcing memory onto a memoryless system.

The funny part is that a system with pity really does have memory — the counter — so superstition turns statistically half-true: you do know your pity count, and “I’m close to pity” is a verifiable statement.

Pity turns the gambler’s fallacy from a hallucination into a ledger, and that is what makes it cleverer than any marketing announcement: it buys back the player’s trust in randomness with a promise of certainty.

This trust engineering also has an imported finished product: the tenjou (ceiling, Japanese mobile-game jargon) — one step past hard pity, a spending cap where after a set number of pulls you exchange resources directly for the featured character and the random step leaves the stage entirely.

The tenjou turns the worst case from a probability event into a budget event; for the first time a player can enter a random system with bookkeeping.

Look back down the chain and a direction becomes clear: from naked probability to hard pity, soft pity, PRD, and finally the tenjou, randomness cedes its ground inch by inch to certainty.

Each layer trims extreme bad luck and adds plannability, while carefully keeping that topmost sliver of maybe-one-pull-does-it sweetness.

The endpoint of taming probability is not abolishing randomness but precisely fencing off the range where it may still make trouble.

From one pull to one team

Expected pulls answer “how long until a gold”, but the real goal is usually structured: complete a set, max out a character’s constellations, scrape a usable team out of the off-rate characters.

Ask one and combinatorics falls out of your mouth.

Start with the most common “structured” operation: the ten-pull.

Probabilistically a ten-pull is just ten independent draws, but because they share one pity counter, the experience gets repackaged.

At a 0.6% single-pull gold rate, the chance of at least one gold in a ten-pull is $1 - 0.994^{10} \approx 5.8\%$, and the blankness of nine empty pulls is hedged by ten times the visual impact.

More importantly, if the pity interval is a rule like “every ten-pull guarantees a 4★” — many games run high-rarity pity on a ten-pull cycle — the ten-pull becomes the second unit that truncates the tail.

When single pulls and ten-pulls share the counter, the community strategy of warming up with singles and finishing with a ten-pull becomes popular. That is at bottom players making optimal use of the counter state under the system’s rules — a dynamic-programming problem that emerged on its own.

On price, a ten-pull usually carries a 5% to 10% discount, and that is its economic substance: a bulk commitment traded for a certainty premium — the probability model untouched, the payment psychology overhauled.

The basic computational tool is the binomial: ignoring pity corrections, the probability of exactly $k$ 5★s in $N$ pulls is

For “exactly 2 5★s in 90 pulls” the first step is that binomial coefficient: $\binom{90}{2} = 4005$, giving $4005 \times 0.006^2 \times 0.994^{88} \approx 8.5\%$.

Such coefficients are easy to fumble by hand, and the site’s Permutation / Combination calculator does exactly this: enter $n$ and $k$, get both the permutation count $P(n,k)$ and the combination count $C(n,k)$ — a handy companion for this kind of estimate.

One layer up sits planning.

Aim at max constellations (the same UP character obtained 7 times) at 93.4 pulls per UP, and the expected total is about 654 pulls. Linear, no surprises.

What is worth computing is the quantile, not the expectation: budgets should be set so that “eight in ten players can get there”, not at the average.

Which is the value of the Gacha Simulator: set the total pulls, the per-pull rate, and the pity interval (0 for none), run one simulation, and get the full record — total pulls, how many obtained, which pull the first hit landed on, average pulls per copy.

One run is a single player’s fate; run it a few more times and you have the distribution itself.

The expectation is the theoretical figure on the ledger; the quantile is the number to read when budgeting — and in heavy-tailed distributions the gap between them can be terrifying.

Pity is hard reshaping of a distribution, but distributions also grow shapes on their own: throw something at random into a geometric structure, then count the outcomes. The three scattering experiments of the next chapter span half the introductory history of statistics.

Scattering Experiments: The Galton Board and Buffon’s Needle

Three point-scattering experiments, each a century old, each doing one small thing: throw something at random into a geometric structure, then count the outcomes. Line them up and they happen to span half the introductory history of statistics — the Galton board piles coin-flip-like left-right bounces into a bell curve, Buffon’s needle back-derives π from geometric probability, and scattering points into a circle is the plainest Monte Carlo there is. The terminus of that line is today’s practice: no painstaking scattering any more, but sampling straight from the normal distribution.

Hands-on versions: Plinko, Buffon’s Needle, Monte Carlo π, the Gaussian Sampler.

The Galton Board

Around 1876 Francis Galton built a vertical board: a funnel at the top, dozens of staggered rows of pegs below; a ball dropped from the top meets each peg and chooses left or right with some bias, finally landing in a slot at the bottom, where the balls pile into a bell curve.

Galton named the board the quincunx, and used it in Natural Inheritance to demonstrate heredity and regression.

A crowd of individually random tiny perturbations, and once summed they always come out the same shape.

The mathematical model is plain to the point of laziness. Let the board have $n$ rows of pegs; the ball veers randomly left or right at each row, so its landing position is the sum of $n$ independent Bernoulli trials:

This is the binomial distribution.

The coefficient $\binom{n}{k}$ is not an abstract symbol; it counts all the paths that pick exactly $k$ rights out of $n$ bounces.

The $n$-th row of Pascal’s triangle is the entire probability mass of the landings.

For $n=12$ that row reads:

Below, that table runs live for you. The balls deflect randomly row by row, the pile in the slots slowly takes on a bell-shaped outline as the count grows, and after 400 balls the theoretical distribution is overlaid as a dashed line for comparison:

The site’s Plinko brings this machine into the browser: 12 rows of pegs in a triangular layout, a swinging launcher tossing the balls in, the balls bouncing physically among the pegs with gravity, friction, and elasticity, and 11 slots at the bottom scoring by multiplier (10× in the center, decaying all the way to 0.2× at the edges).

By the pure binomial, at $n=12$ the landings concentrate in the middle: $k$ from 4 to 8 sums to $495+792+924+792+495 = 3498$, which is 85.4% of $4096$ — the overwhelming majority of balls should pile dead center.

Real marbles do not quite obey this ideal model: balls carry momentum, one bounce shapes the direction of the next, and adjacent landings are not independent.

But the skeleton — many rows of independent small perturbations, summing to a center-heavy total — survives, and that is the entire point of the binomial distribution.

The row of multiplier slots at the bottom deserves a second look: it turns a distribution of landings into a distribution of payouts, a nonlinear transform of the binomial random variable.

The center slot has the highest probability and pays the most, the edges the lowest probability and pay the least — the exact opposite of a real pachinko machine’s high payout at the rim, a deliberate teaching design that lifts the expectation to please the player.

You can take $\binom{12}{k}/4096$ as weights on paper, multiply each slot’s multiplier through and sum, and estimate the expected return of this design. That is a decent combinatorics exercise in itself.

From Binomial to Normal

The Galton board’s real trick happens at the limit.

In 1733 de Moivre proved what later took the name de Moivre–Laplace theorem: as $n$ grows, the standardized binomial approaches the normal.

In modern notation, if $X \sim B(n, p)$, then:

With $n=12$ and $p=1/2$ the mean is 6, and the standard deviation is $\sqrt{12 \times 0.25} = \sqrt{3} \approx 1.73$.

A 12-row board already shows a rather standard bell.

The central limit theorem later generalized this to sums of arbitrary independent, identically distributed small perturbations. Whatever distribution a single perturbation follows, as long as there are enough of them, each small enough and independent enough, the sum tends to the normal.

The bell curve is everywhere not because of the curve itself but because the generating mechanism — summing a large number of tiny independent factors — is simply too common. Measurement error is the sum of countless disturbances, height the sum of countless genetic and environmental factors, a marble’s landing point the sum of countless bounces off pegs.

So the Galton board’s historical standing lies not in its mechanism but in its being the first touchable path from probability to the normal: the normal distribution is not assumed, it is piled up from the binomial, layer by layer.

Once that lands, the statistics-course convention of “assuming errors are normal” stops being an arbitrary rule and becomes a reasonable approximation of a summation mechanism.

One more entry on the historical line.

The normal distribution’s first role on stage was exactly the “law of error”: in 1809 Gauss argued, while computing planetary orbits, that measurement error ought to follow this curve, and along the way built least squares. The name “normal distribution” is still also “Gaussian distribution” for that reason — it was derived first-principles as an error model.

Laplace later generalized de Moivre’s limit theorem into the earliest form of the central limit theorem, and “error is the sum of many tiny perturbations” was upgraded from assumption to theorem.

Another identity of the normal in statistical physics is worth knowing too: among all distributions with a fixed variance, the normal is the one with maximum entropy. Knowing “nothing but the variance”, the normal is the most honest assumption in the information-theoretic sense.

Where Regression to the Mean Was Born

Galton built the board for genetics, not for teaching.

His question was concrete: do eminent fathers have eminent sons?

The data said “yes, but less so”. The offspring of the very extreme sit on average only a little above the mean; extreme values fall back toward it.

To explain that, he added a stage to the quincunx: balls in the upper half first pile into slots at the middle level (the parental phenotype), then drop from those slots through the lower peg array (the random perturbation acting on the offspring), and the offspring distribution that forms comes out narrower and more centered than the parents’.

The term regression to the mean was born here; regression originally means “going back”.

What this bolt-on board left behind reaches far beyond genetics.

Extreme values fall back not because the mean has any gravity but because of pure sampling structure: an extreme value = a high base level + an extremely lucky perturbation; the next perturbation returns to normal and the result falls back on its own.

Athletes’ “champion’s curse”, the flop of a best-seller’s sequel, the reshuffling of performance rankings — most of it is this mechanism performing.

The test for spotting it is simple: wherever “being selected” correlates with “random fluctuation”, regression will happen. And the vast majority of ranking settings satisfy exactly that condition.

A Corollary Worth Guarding Against

The other direction needs clarity too: the central limit theorem’s three premises — independence, smallness, multitude — are all required.

Once the perturbations are strongly correlated (one gust blows every ball to the same side), or a single perturbation can be huge (one row of pegs flings the ball straight to the edge), the bell collapses.

Finance’s “asset returns are normal” assumption keeps crashing, and what usually fails is the “small and independent” clause. In a market panic the perturbations are highly correlated, and fat tails follow.

A Galton board cannot pile up a fat tail. The real world can.

Buffon’s Needle

Change the scattered object from pegs to needles and the story goes back to 1777.

Buffon asked: a needle of length $l$, thrown at random onto parallel lines spaced $d$ apart ($l \le d$), what is the probability that it crosses one of them?

The question is the founding work of geometric probability. The sample space is no longer discrete counts but continuous configurations: the needle’s position is given by its midpoint and its angle, and “uniformly random” means scattering uniformly over that continuous space.

The solution takes two steps: let $y$ be the distance from the midpoint to the nearest line and $\theta$ the angle between needle and lines (taking $0$ to $\pi/2$ suffices); the needle crosses a line exactly when $y \le \frac{l}{2}\sin\theta$.

Scatter uniformly over the rectangle $\theta \in [0, \pi/2]$, $y \in [0, d/2]$; the hit region’s area over the total is the probability:

π falls out of the sky.

Nobody in the 1780s saw any use for it, until Laplace pointed out the other face: since $P = 2l/(\pi d)$, inverting it to estimate probability by frequency gives:

where $N$ is the number of needles thrown and $C$ the number of crossings.

The whole idea of estimating a constant with a random experiment took shape here for the first time, more than a hundred and sixty years before “Monte Carlo methods” got the name (Manhattan Project, von Neumann and Ulam).

Note the rigorous boundary of that inversion: the π in the formula means “the experiment’s efficiency depends on π’s true value”; using it to estimate π is logically consistent (the frequency converges to the probability $P$, and π is solved from $P$ and known quantities), but that is exactly why it is a poor estimator — the target constant hides in the denominator of the hit probability, so the estimate carries a heavier nonlinear amplification.

The Buffon’s Needle tool implements the experiment: each click drops 1500 needles (needle length and line spacing both 1), needles that cross a line are drawn red and the rest gray, and the estimate $\pi \approx 2lN/(dC)$ appears alongside the cumulative throw count.

The crossing ratio should hover around $2/\pi \approx 0.637$, while the π estimate wobbles between 3.0 and 3.3; several rounds are needed to see how slowly it tightens.

Comparing the Cost of Two Experiments

Put Buffon’s needle and scatter-π on the same table and compare variances, and the weight of the words “experiment design” becomes visible.

Scatter-π has a hit probability of $\pi/4 \approx 0.785$; the needle only $2/\pi \approx 0.637$.

The Bernoulli estimator’s variance is $p(1-p)/N$; substituting: scatter $\approx 0.169/N$, needle $\approx 0.231/N$.

At the same sample size the needle’s variance is 37% larger.

In other words, to reach the same precision, Buffon’s needle needs about 37% more throws.

It is the more expensive experiment, expensive because the hit event is rarer and carries less information.

That was true of the hand experiments two hundred years ago and remains true of today’s simulation systems: the estimator’s constant factor is your electricity bill.

π by Scattering Points

The third experiment is the most direct: scatter points uniformly in a square of side $s$, count the fraction $p$ inside the inscribed circle, and the area ratio gives it at once:

Monte Carlo π is the browser version: a square canvas with an inscribed circle, 2000 points per click, points inside marked red and outside gray, and the estimate $\pi \approx 4 \times \text{inside}/\text{total}$ displayed next to the cumulative sample count.

Being a Bernoulli estimate, the standard error is:

That is the famous √N law: the error is proportional to $1/\sqrt{N}$, so every extra decimal digit of precision costs 100× the samples.

2000 points give a typical error around 0.04; at 2 million the estimate settles to three decimals.

Randomized Methods earlier in this post already worked through the √N ledger in detail; here just the positive side: error shrinking as $\sqrt{N}$ is slow, but it is independent of dimension.

Scattering points in a two-dimensional square and in a five-hundred-dimensional ball follow exactly the same precision law.

Scatter-π uses a toy of one-dimensional difficulty to demonstrate the skeleton of the only method that works in high-dimensional integration.

All three experiments assembled, here they are side by side:

The first answers “where does a distribution come from”, the latter two “how is a constant computed”.

The two threads meet on one point: inferring a deterministic answer from random samples.

The origin of the name Monte Carlo deserves a paragraph; it happens to be one of science history’s famous sofa inspirations.

In 1946 Ulam, a colleague of von Neumann’s, was ill and bedridden, playing Canfield solitaire alone, wondering “what is the probability this deal is winnable”. Enumerating all deck orders explodes combinatorially, and it struck him: play a few hundred games, count the wins, and the answer arrives by itself.

After the war he and von Neumann carried the same idea to neutron transport calculations; the name was coined by their colleague Metropolis (the Monaco gambling city — meaning “computing by probability”, not “living on luck”).

Scatter-π and solitaire are structurally identical: turn “can it succeed” into a frequency, and let the law of large numbers do the rest.

Every “random simulation” in today’s financial pricing, particle transport, and graphics rendering descends from that card table by the sickbed.

Direct Sampling

The Galton board piles a bell out of 12 rows of physical bounces, Monte Carlo closes in on π with oceans of samples. Both are brute force.

Once the target is known to be the normal distribution, the question flips: can we skip the piling and draw a sample straight from $N(\mu, \sigma^2)$?

The most general idea is inverse transform sampling: compute the target’s cumulative distribution function $\Phi$, draw a uniform number $u$, and set the sample $= \Phi^{-1}(u)$.

Stretch the uniform on the probability scale into the target shape on the density scale. The exponential distribution comes out this way with $-\ln u / \lambda$, clean and neat.

But the normal stalls here: $\Phi^{-1}$ has no elementary closed form, and numerical inversion means tables or iteration.

So a cleverer construction takes over.

The Box–Muller transform (1958): take two independent uniform random numbers $u, v \in (0, 1)$, then:

The key to the derivation is the radial symmetry of the two-dimensional normal.

The joint density of the 2D standard normal is $\frac{1}{2\pi}e^{-(x^2+y^2)/2}$, depending only on the radius $r$ and not on the angle. So in polar coordinates radius and angle are independent, the angle is uniform on $[0, 2\pi)$ (hence $2\pi v$), and the distribution of the squared radius, to satisfy “density decaying exponentially in $r^2$”, is exactly an exponential: set $u = e^{-r^2/2}$ and solve for $r = \sqrt{-2\ln u}$.

Uniform random numbers are square on the plane; this transform squeezes them into a circularly symmetric Gaussian cloud.

One multiplication, one logarithm, one cosine; two uniform numbers buy one normal number (in fact a pair: swap $\cos$ for $\sin$ and you get another — standard normal samples, buy one get one).

Engineering also uses a variant, the Marsaglia polar method: rejection-sample inside the unit circle to get polar coordinates and avoid $\ln$ and trigonometry, with a rejection rate of $1-\pi/4 \approx 21\%$ — a real speedup in the era before hardware transcendentals.

The Gaussian Sampler uses exactly the Box–Muller formula ($\sqrt{-2\ln u}\cos 2\pi v$, with rejection resampling when $u=0$): tune the two parameters $\mu$ and $\sigma$, drag the sample-size slider, and the histogram redraws live.

Few samples and the histogram is all jagged teeth; many samples and the bell appears by itself — turning “more samples look more like the population” into something one drag can demonstrate.

In teaching order the line runs backwards: first the Galton board’s physical piling (distributions emerge), then Buffon and scatter-π (distributions are designed), finally Box–Muller (distributions are constructed).

Simulation systems today work the third way: whatever distribution you need, build a transformation chain starting from uniform numbers. Uniform to exponential with $-\ln u/\lambda$, uniform to normal with Box–Muller, any distribution at all with inverse transform or rejection sampling.

Every marble in the Galton board is now a line of $\text{mu} + \text{sigma} \times \text{gauss}()$.

Variance Reduction

The √N law nails down the error’s exponent, but the constant factor is still negotiable. This is where variance reduction earns its keep.

The core idea in one sentence: cancel the known part, randomize only the unknown part.

• Antithetic variables: in scatter-π, for each point $(x, y)$ also average its “antithetic point” $(1-x, 1-y)$. One inside, one outside, strongly negatively correlated; the fluctuations cancel and the variance drops at a stroke. Buffon’s needle is the same: tally the needle together with its complementary configuration;
• Conditional expectation: integrate out whatever can be integrated analytically. A variant of scatter-π randomizes only $x$ and solves the $y$ direction analytically; each point carries more information and the constant factor drops again;
• Importance sampling: scatter from a distribution close to the hit boundary, evening out each sample’s information contribution. Especially apt for an experiment like Buffon’s needle, where most needles sit far from any line and the outcome is never in doubt.

These techniques press the constant down several fold, but mind the boundary: variance reduction changes the constant, not the exponent.

The 2 inside $\sqrt{N}$ does not budge, and the ledger of 100× samples per extra digit is unchanged.

Exponential speedup requires changing the estimator itself (from a Bernoulli estimate to an analytic transformation chain, say), not grinding indefinitely on how you scatter.

The antithetic gain can also be stated in one line of covariance algebra. Let $X, X'$ be the hit indicators of the two complementary configurations; the mean estimator $\bar{X} = (X+X')/2$ has variance:

With independent repeated sampling the covariance is zero and the mean estimate’s variance is $\sigma^2/2$.

Complementary configurations, one inside one outside, are strongly negatively correlated: when the point is inside the circle its mirror is more likely outside, so the covariance is negative and the variance is pressed below $\sigma^2/2$.

The cost is nearly zero: the same batch of random numbers run through two analyses; the sample count doubles, but the effective one more than doubles.

The one prerequisite is functional symmetry: once the complementary configuration’s correlation structure breaks (the integrand behaving very differently at $x$ and $1-x$, say), the negative covariance vanishes or even turns positive, and antithetic variables are all cost and no gain.

Every variance-reduction trick is sensitive to problem structure; there is no free lunch.

In the scattering experiments the randomness is manufactured by the experimenter; at the card table the house deals it — probability’s oldest laboratory was never the blackboard.

Card-Table Probability: Five Structures

Dice and cards are naturally equiprobable, repeatable, and settle win or loss on the spot, and humans used them to map out a good deal of probability theory long before calculus existed. Five card and board games here happen to cover five different probabilistic structures: Blackjack is a game with an open opponent policy; Texas Hold’em is odds arithmetic under incomplete information; Yahtzee is expected-value planning on a single score sheet; Backgammon is route search over random branches; and Solitaire puts the value of information on the table. Every rule quoted below comes from the source of the site’s widgets, so each piece of math can be verified by hand in the corresponding game.

Hands-on versions: Blackjack, Texas Hold’em, Yahtzee, Backgammon, Solitaire.

Blackjack

The rules of the site’s Blackjack come straight out of a textbook.

Each hand is dealt from a freshly shuffled 52-card deck (shuffling is a textbook Fisher–Yates, back to front, random swaps — that three-line loop is worth memorizing on its own; for the language basics see the early JavaScript notes). Ante 10, starting stack 100, a win pays 20 (net 10, i.e. 1:1), a push returns the bet.

In a hand you have only two actions: hit and stand. After revealing the hole card the dealer plays mechanically by “hit below 17”. The source loop condition is a total below 17, so soft 17 also stands.

If either side is dealt a natural 21 the hand settles immediately; if both are 21 it is a push.

Where does the house edge come from? Split it into three accounts.

First, order. The player acts first and busts first, and the chips change hands on the spot. The dealer wins without drawing a single card. Even with the worst possible strategy, “wait for you to bust” alone is worth most of the ticket price.

Second, asymmetric decisions. The dealer’s policy is public, fixed, and leaves zero room for expression. The player has freedom, and with it the room to err. Casinos do not fear experts; they fear people who cannot count, and the bulk of this second account is the expected value of “the opponent will make mistakes”.

Third, the payout. A player’s two-card 21 (blackjack) pays 3:2 in a casino; this implementation pays 1:1.

The chance of being dealt a blackjack is $2 \times \frac{4}{52} \times \frac{16}{51} \approx 4.8\%$, and dropping the payout from 3:2 to 1:1 throws away about 2.4 percentage points of expectation per hand on that item alone. The widget is for practicing strategy, not for simulating casino odds; keep that in mind before you play.

There is also one small rule in the player’s favor: a single deck.

Casinos usually shuffle 6–8 decks together, and the chance of a blackjack falls as the deck count rises (a small shoe makes an ace and a ten-value card more likely neighbors). The site plays a single deck, handing that subsidy back to the player, and then zeroes out card counting with a fresh shuffle every hand.

One shuffle per hand, the history carries no information, and every hand is a pure independent trial.

The site also has no side bets such as insurance, so the coach’s four actions — hit, stand, double, split — are its entire strategy space. Master the trunk first; the branches can wait.

Bust risk can be computed outright.

Approximate the card values as “2–9 at 1/13 each, ten-value cards (10/J/Q/K) at 4/13, ace counted as 1”; then the bust probability for a hard total $t$ on one more card is the chance of drawing above $21-t$:

For a hard 16, the bust probability is $1 - \frac{5}{13} = \frac{8}{13} \approx 61.5\%$. Six times out of ten you die on the spot.

This table explains why 12–16 are called “stiff”: every one of them hangs on the bust line.

Note that the table only holds for hard hands. An ace counts as 11 or as 1, so a soft hand never busts in one card. Soft 17 plus an ace is soft 18, plus a ten is hard 17; the bust rate of a soft hand is zero until it degrades into a hard one. That is exactly what “soft” means.

The textbook figure on the other side: with a dealer upcard of 5 or 6 the dealer busts about 40% of the time, and with an ace up it is lowest, just over 10%.

These two sets of numbers walk toward each other, and the whole logic of basic strategy hides in the gap between them.

Basic strategy

The definition of basic strategy is minimal: for every combination of player hand × dealer upcard, compare the expected return of hitting, standing, doubling, and splitting, and take the largest.

Starting in the 1950s people computed this table to exhaustion with computers. It is the most democratic application of expected-value maximization in probability theory: no talent required — memorize it and the house edge drops from the 2%–4% of random play to around 0.5% (under standard casino rules).

The hard-hand skeleton is the easiest to memorize.

17 and above: stand.

13–16: stand against upcards 2–6, hit against 7–A.

12: stand only against 4–6.

11: always double.

10: double against 9 and below.

9: double against 3–6.

8 and below: hit.

The physics behind it is plain. Against upcards 2–6 the dealer busts often, so a stiff 12–16 in your hand does not need to gamble on improvement — just wait for the bust. Against 7–A the dealer most likely reaches 17 or better, so you must improve to 17+ yourself and simply eat the bust risk. Hard 16 against an upcard of 10 is the most famous problem in blackjack precisely because both options hurt, and the table says hit.

The most counterintuitive row in the chart is hard 12: hit against 2 and 3, stand against 4–6.

A 12 busts only 30.8% of the time, which looks safe enough to stand on. But against 2 or 3 the dealer’s bust rate is not high enough — it will keep drawing to 17 or better — so rather than hoping it busts itself, improve while your own bust rate is still low. Against 4–6 the dealer’s chance of suffocating is already large enough that standing pat with a stiff hand is optimal.

Same 12, two ways to live, and the dividing line falls exactly between 3 and 4.

The soft-hand and pair branches have their reasons too.

Soft 18 (A,7) has three treatments: double against 3–6 (the dealer is weakest, so raise to press the advantage), stand against 2/7/8, and hit against 9/10/A.

Soft 13–16 only takes the doubling window against 5–6.

On pairs: A,A and 8,8 always split. The first charges at 21; the second turns the worst hand in the game, hard 16, into two chances. 5,5 never splits — that is a good ten, so play it as hard 10 and look to double. 9,9 splits against everything except 7/10/A. 7,7 splits against 7 and below. 4,4 splits only against 5–6.

Every line has an expected-value difference behind it; none of it is mysticism.

The site’s strategy coach turns the lesson into a graded quiz.

Besides the table, the blackjack page has a tab labeled coach. It deals a random hand, shows the dealer upcard and your cards, states a “suggestion: some action” up front, and grades you the moment you pick hit, stand, double, or split; a wrong answer tells you the best play.

The double button only appears with two cards, and the split button only on a pair.

The coach has one lenient rule: when the suggestion is double and you choose hit, that counts as correct. Doubling is illegal past two cards anyway, and hit is exactly the second-best choice a real player makes when they want to double and cannot.

Also, every hand is reshuffled and independent here, so card counting is useless; the coach trains the reflex of the chart itself, not the memory of the shoe.

Texas Hold’em

The site’s Texas Hold’em is poker without betting.

Three players (you plus two), dealing from hole cards through the flop’s three, the turn, and the river to showdown. At showdown each player picks the best five of their seven cards (2 hole + 5 community); the implementation enumerates all C(7,2) = 21 “discard two” combinations and evaluates each. Hand evaluation even covers the A-2-3-4-5 wheel as the lowest straight and split pots on multi-way ties.

Without betting it is not poker but a test bench for dealing and hand evaluation — which is exactly right for practicing two purely mathematical things: counting outs and computing odds.

An out is a card not yet seen that turns you into a winner.

After the flop there are 52 − 2 − 3 = 47 unseen cards.

Counting outs has one basic hygiene rule: no double counting. On a combo draw with a flush draw plus an open-ended straight draw, some of the nine suit cards also complete the straight, so a flat 9+8 counts the same card twice. Outs are the number of distinct cards that save you, not the sum of two wishes.

A flush draw after the flop (two in hand, two on board) has nine remaining cards of the suit; the chance of at least one arriving within two streets is:

Over the turn alone it is 9/47 ≈ 19.1%.

An open-ended straight draw has 8 outs, about 31.5% by the same arithmetic. A gutshot has only 4 outs, about 16.5%.

Nobody computes binomials at the table; the mental shortcut is the “rule of 2 and 4”: multiply outs by 4 with two streets to come, by 2 with one.

Against the exact values: 9 outs times 4 gives 36% versus a true 35.0%, a slight overestimate. One street times 2 gives 18% versus 19.1%, a slight underestimate.

The error stays within a point or two, and what it buys is a three-second decision at the table. The direction of the error is known, which is what makes the approximation usable.

Pot odds convert probability into price.

The decision in front of you is “call X to continue”, so the minimum equity required is $\frac{X}{\text{pot} + X}$.

Example: the pot holds 100, the opponent bets 50, you call 50, so the call costs 50/200 = 25% of the final pot.

Here the flush draw (35%) is far above the threshold, so calling is positive EV. The gutshot (16.5%) is below it: fold.

That is the controlled experiment of price against probability. The same draw is an asset in a cheap pot and a liability in an expensive one.

As for implied odds: money you can still extract on later streets loosens the threshold. That is a reasonable extrapolation of the model, but treating it as a universal excuse for every call turns an extrapolation into a theorem.

How to run the experiment in the widget: deal repeatedly and watch the drawing hands specifically. After the flop, count outs and estimate the probability first, then let the turn and river reveal the answer and calibrate your intuition against reality.

Hold’em without chips strips psychology out entirely and leaves a pure frequency calibrator. Once these numbers grow into intuition, you have earned the right to talk about “feel” in a game with betting.

Yahtzee

Yahtzee’s probabilistic structure is nothing like a competitive card game. No opponent applies pressure; you face five dice and a score sheet where each row can be filled once.

The rules in the site’s Yahtzee: three rolls per round, dice can be locked after the first, 13 rounds fill 13 categories. The upper section 1–6 scores the sum of matching faces. Three of a kind and four of a kind score the total of all five dice. Full house is 25 (the implementation counts a Yahtzee as a full house too; the source has a dedicated branch for it). Small straight 30 (sorted and deduped, containing 1234, 2345, or 3456). Large straight 40. Yahtzee 50. Chance scores the total.

After every roll the sheet previews in real time what each empty category would score right now. That preview moves part of the expected-value computation out of your head and onto the interface — the game does half the table lookup for you.

Single-roll probabilities are the foundation of all planning. Five dice give $6^5 = 7776$ equally likely outcomes:

Why 240 for the large straight? Two sequences (1–5, 2–6) with 5! arrangements each, $2 \times 120 = 240$. The probability is low enough that a whole game may not show one, which is exactly why it is worth 40.

And the 1/1296 of a Yahtzee has a way to fight back. Across three rolls, locking the most frequent face each time, the overall probability of a Yahtzee under optimal play is about 4.6%. The number of attempts is the best lever there is: three rolls are not three independent 1/1296 shots but a decision tree.

Expected-value maximization has an unusually clean example in this game.

The first roll is 4,4,4,x,y. Lock the triple and reroll only the other two: three of a kind scores the total, so the expectation is exactly $12 + 7 = 19$ (two dice average 7). In other words the move loses not one point of expectation in the three-of-a-kind category while collecting the free chance of upgrading to four of a kind, $1-(5/6)^2 = 11/36$, and to a Yahtzee, 1/36.

Expectation unchanged, upside variance for free — this kind of free option is lying around everywhere in dice games, provided you can do the arithmetic.

Conversely, with all three rolls spent, 4,4,4 in the three-of-a-kind row is exactly 12 + x + y, with no expectation to speak of, only the ledger.

The same idea, one more roll to check it. Lock (6,6) and reroll three dice: chance scores 12 plus those three dice whatever they are, expectation exactly $12 + 10.5 = 22.5$. “Score the total” averages luck away inside the expectation.

Meanwhile three of a kind has a $1-(5/6)^3 \approx 42\%$ chance of rising from zero, with four of a kind and Yahtzee further out in the tail.

The same dice landing in different categories are different random variables; choosing a category is choosing the shape of the variable.

There is also a superb case of rules shaping strategy.

Under classic Yahtzee rules the upper section (the six rows 1–6) pays a 35-point bonus at 63 total, which makes “protect the sixes and chase the bonus” part of optimal play; early on you may even sacrifice lower-section chances for the 63.

The site’s implementation has no such bonus, so simply be greedy on each row’s expected score.

Delete one rule and the structure of optimal play changes entirely. The most fascinating thing about expected-value problems is how violently they react to the wording of the rules.

The same thinking covers opportunity cost. Each of the 13 categories is filled once, so “9 points into sixes” versus “9 into chance” is not 9 against 9 but 9 against the expectation of chance over the rounds left.

The score sheet is a resource; filling a box wrongly hurts more than rolling badly.

Backgammon

Backgammon is the only one of the five where dice and movement interleave.

White moves from 24 toward 1, black from 1 toward 24. Each roll drives two moves (one checker twice or two checkers once, in either order), and doubles give four moves of the same pip count.

A lone checker (blot) is hit when the opponent lands on its point, and it goes back to the bar. Checkers on the bar must re-enter the opponent’s home board first; nothing else can move.

Only after all your checkers are in your home board can you bear off, and there is a strict closing rule: you may not skip a bear-off when the target point is empty and a higher point still holds your checkers. This “clear the high points first” rule is the biggest trap in the endgame, and the rejection logic in the source spells it out.

The widget also ships a four-card how-to (board direction, moving, hitting and the bar, bearing off), so a beginner can play straight from it.

The dice give 36 equally likely combinations; doubles are 6/36 = 1/6 of them but grant four moves. It is a variance-maximizing design: a double is roughly a free double turn.

The branching explodes in the moving. Different orders for the two dice and different intermediate points produce completely different positions.

Black in the widget has two engines. The default one plays greedily: hit whenever it can. The source also has a heuristic engine that enumerates the whole tree of legal move sequences, scores each resulting position, and plays the best.

Its evaluation function is worth copying: pip difference (progress) + 15 × checkers borne off (closeness to victory) + 20 per opponent checker on the bar (punish the opponent) − 4 × direct shots on each of your own blots (risk) + 3 per made point in the home board (defense), five terms summed.

Convert “progress” and “risk” into the same currency: that is the whole secret of position evaluation.

The direct-shot table is the entry point to backgammon probability. For a blot at distance d, the number of dice combinations (out of 36) that hit it next roll:

The table is not monotonic. d=2 is more dangerous than d=1 because (1,1) also makes 2. d=3 adds both orders of 1+2 and (1,1) as three steps. d=6 reaches 17/36 thanks to 3+3, 2+2+2, and a direct 6. More ways to combine, easier to hit.

At distance 7 and beyond the two dice must be used together, and the probability drops sharply to 6/36 or less.

So leaving a blot within six pips of the opponent is a risk with a price tag. The ×4 weight in the evaluation function is exactly the crude coefficient for that expectation account. A checker sent back to the bar has to travel 25 pips again (the bar counts as 25, the farthest distance from bear-off), so its expected cost ≈ hit probability × the distance it had already covered.

Risk pricing does not need to be exact; get the order of magnitude right and that is enough to win.

Two rules that did not make it into the widget are worth mentioning.

One is the doubling cube, the deepest layer of real-money play. “Do you dare offer a double” upgrades a pip race into a psychological war; the site has none of it, so the AI’s evaluation stops at movement.

The other is the bar blockade. With checkers on the bar you must re-enter in the opponent’s home board, and if the opponent makes all six entry points into pairs, there is no way in and the whole turn is forfeited. The source simply skips the turn when it finds no legal move; in extreme positions you sit on the bar watching the opponent clear the board.

Solitaire

Solitaire is the only one of the five that is single-player with fully hidden information.

The site uses the standard Klondike layout. Seven tableau piles, the stock turns one card at a time and recycles the whole discard pile when exhausted (unlimited passes). Tableau runs descend in alternating colors, and only a king may start an empty column. Foundations build by suit from A to K, and double-clicking a face-up card sends it there automatically. Win by filling all four foundations to 13.

A randomly dealt Solitaire raises a subtle question: a deal being “solvable in theory” and “solvable by you” are two different things.

Turn every hidden card face up and let a program solve with perfect information and statistically about 80% of deals are winnable. In real play the 24 face-down cards and the order of the stock are completely invisible to you, and an ordinary player’s long-run win rate is often one or two in ten.

What beats you is not luck but information. Solitaire is decision-making under partial observability: every step prices the trade between “moving more smoothly” and “seeing more”.

That also explains the hardest heuristic: turn hidden cards first. Flipping a hidden card adds information and legal moves at once — a direct investment in making hidden information public. Shuffling cards back and forth among the face-up ones, by contrast, only burns randomness and yields no cognitive return.

Unlimited recycling sounds generous, but the order of the stock never changes from start to finish. Turn it over, turn it back, and it is the same sequence. Recycling is a circular queue, not a reshuffle; after one lap it produces no new information.

That also makes card memory unusually valuable here: whoever has seen the stock through once is, on the second pass, reading a book they have already read.

The site’s implementation also differs from classic Klondike in one way you must know before playing: the foundations only take cards, never give them back. There is no code path that returns a card from a foundation.

Classic rules let you pull a foundation card back into play, and many deals survive on that maneuver. Here you cannot.

So the offhand double-click that sends a card to the foundation becomes a commitment that needs thinking: will this 3 still be there to park on later?

One small rule change flips the direction of greed outright.

Add the hard constraint that only a king starts an empty column (opening a column with no king in reserve just gives away a slot; empty columns are scarce, the king is their only ticket, which is why beginners love opening columns and veterans hoard them), and even though this deck uses the permissive one-card-draw, unlimited-recycle variant, deals that should jam still jam.

Constraints are the real skeleton of this game.

Beyond dice and cards, a board game’s rule sheet is itself a probability allocation: some games hand fate entirely to the dice, others leave them only a narrow gap. The next chapter puts five board-game widgets on one luck axis.

The Luck Curve: Distributing Chance in Board Games

Dice are the heart of a board game, but every design leaves that heart with vessels of a different bore. In some games the dice are fate itself (Snakes & Ladders); in others the dice are only the dealer, and what is really tested is how you respond (Battleship).

“Luck share” is not mysticism. It can be read out of the rules, and it directly determines how much a game makes you want a rematch. This chapter spreads that axis out with five board-game widgets from the site: two dice races, one information search, one pure specimen of game theory, one memory game. Every rules statement comes from the source.

Hands-on versions: Snakes & Ladders, Ludo, Battleship, Rock Paper Scissors, Reflex Games.

Luck share

How much of a board game is “decided by luck” can be measured with one operational definition: after the random events land, how much decision-making is left that can still change the distribution of outcomes.

Snakes & Ladders sits at the far left of that axis. Once the die is rolled there is no choice at all; the piece walks itself, the ladder climbs itself, the snake slides itself. Luck share is one hundred percent.

Ludo moves one notch right. The dice still dominate, but which of four pieces to advance is a real decision.

Battleship further right again. The dice leave the table entirely, and what is compared is search efficiency.

Rock Paper Scissors is the strangest case. Decision freedom is enormous, yet against a particular opponent the expectation is exactly zero.

Reflex Games has no opponent and no adversarial randomness; the randomness hides only in the sequence the system extends round by round, and everything else is memory.

Luck share directly determines a game’s rematch-desire structure.

A pure-luck game does not bruise when you lose. You lost to the dice, not to yourself, so a rematch carries no psychological cost — but the price is that a single game must be very short. Snakes & Ladders at one minute a game fits perfectly.

A high-decision game makes you review the loss, and a rematch hurts for a moment first, but the belief that “I can play better next game” keeps players around far longer.

One thought experiment calibrates the whole axis: record every random outcome of a game exactly, replay it with a different player, and does the ending change?

Snakes & Ladders ends identically; the random outcomes uniquely determine the result. Ludo changes, since different move choices can flip it. Battleship is barely recognizable, every shot a different world. Reflex Games keeps the same sequence, but the ceiling of human memory is the ceiling of the level.

A game’s sensitivity to its random seed is the definition of luck share.

The card table is probability’s oldest laboratory. The previous chapter took Blackjack and Texas Hold’em apart (Card-Table Probability); this one puts dice, boards and roshambo on the same dissecting table.

Snakes & Ladders

Snakes & Ladders in one sentence: roll a die and walk from the start to 100, land on a ladder foot and climb, land on a snake head and slide, a roll that overshoots 100 is void, and landing exactly on 100 wins.

The default board in the source carries 8 ladders and 8 snakes. The longest ladder runs 42 straight up to 63 (+21); the most vicious snake hangs from 95 down to 72, dragging you back 23 squares five short of the finish. One more ladder runs 88 to 97, letting you take off right beside the finish line.

The only thing a player can do is tap “roll”. In classic mode the blue side (the computer) rolls automatically.

Mathematize it and it is an absorbing Markov chain. The state is the number of the current square, and where you go next depends only on the current square — the Markov property. A 1 to 6 each advance with probability 1/6, and a landing on a ladder foot or a snake head is immediately remapped deterministically to another square. 100 is the only absorbing state.

The chain has not a single decision point, so every classic question becomes pure computation: how many games on average to reach 100, how big the variance, which snake contributes most to game length. A first-order analysis solves it with a linear system of about a hundred unknowns.

Snakes & Ladders never plays the role of “game” in a probability classroom. It is the teaching aid for “a random walk with deterministic remapping”.

One corner is still worth doing by hand: the geometric distribution of the endgame.

Standing on 99, only a 1 wins; the other five faces all overshoot and you stand still, a hit rate of 1/6. Standing on 98, only a 2 wins, again 1/6.

The closer to 100, the more faces go to waste. Waiting on the last square and waiting for a six in Ludo later on share one distribution. The difference is that in Snakes & Ladders even the waiting is passive: at the far-left end of the luck curve, waiting too is fully automatic.

Two details are worth picking at.

First, the opening hides a stroke of luck. Standing on 0, a 3 lands exactly on ladder foot 3 and jumps to 22 — a 1/6 chance, on the very first roll, of 22 free squares.

Second, the remapping in the source is one layer deep. After a landing is moved to a new square, that square is not checked again for another ladder foot or snake head. The default board’s wiring deliberately avoids chains: no ladder drops you into a snake’s mouth, no snake spits you onto a ladder. The transition matrix is therefore one-step, and the mathematics of the whole process stays clean.

The big variance is where Snakes & Ladders gets its entertainment. The expected game is not long, the variance is enormous. One 95 → 72 snake is enough to turn a tap-in into a marathon, and a player a full lap behind can still wait for the two ladders that flip it. In a game with 100% luck share, “never despair” is guaranteed by mathematics.

Advanced mode is where this widget actually gets interesting. Besides two-player hot seat it ships a board editor: tap any square to place or remove a ladder or a snake (ladders up 10 to 29 squares, snakes down 10 to 29), one button for a random layout, then “start game” to race on your own board.

Which amounts to handing the Markov chain’s transition matrix to the player to rewrite. Plant a 95 → 72 viper, or turn the exit into a direct ladder hugging the finish? Editing the rules is more addictive than playing. It turns the luck curve itself into material for making things.

Ludo

Ludo races around a ring: a 52-square loop, four sides with four pieces each, red played by you and the other three by AI.

The rule most worth computing is the takeoff condition: a piece needs a 6 to leave base.

That immediately gives a geometric distribution. The probability that the first 6 appears on roll $n$ is $\left(\tfrac{5}{6}\right)^{n-1}\cdot\tfrac{1}{6}$, expectation exactly 6.

So a waiting piece takes 6 rolls on average to launch. Opening with all four pieces stuck in base, the player will most likely eat several rounds of “no legal move, skipped”. The agony of Ludo’s first few minutes is not an experience problem; it is that distribution projected straight onto the screen.

The 6 has a second identity: rolling one grants an extra roll. The chained “roll again” is itself geometric. In this rulebook a 6 is simultaneously key, fuel and lottery ticket.

There is one more precise gate before the finish. After 51 squares on the ring each side turns into its own 6-square home lane, and the entry must be exact — overshoot and the move does not count. The endgame’s “wait for one number” shares its distribution with the Snakes & Ladders endgame once again.

But Ludo and Snakes & Ladders differ in one essential way: the multi-piece structure dilutes luck share. Once the die is cast, which piece to move is a real decision.

The source places 8 star safeties on the ring (all four starts among them), and a piece standing on one cannot be captured. Landing on a non-safe square occupied by an enemy sends that whole piece back to base to start over.

Dare to land right in front of an enemy piece? Push the piece furthest along, or launch a new one first? These choices are real every single turn.

The three AIs decide by an open, fixed greed: capture first (10 points), then launch (1), then compare progress, sort by score and take the highest. A predictable opponent lets every choice you make aim at something.

The same die is fate in Snakes & Ladders and merely a dealer in Ludo.

A few more trade-offs in the board’s micro-rules are worth noticing.

Eight star safeties in total, spaced in an alternating pattern of 5 to 8 squares. Wherever a piece is on the ring, a shelter is nearby.

A capture requires standing on exactly the same square; one square off is a near miss.

In the home lane you cannot force a big roll through; the excess pips simply void the move. Four pieces crowded at the door waiting for the same number is Ludo’s most honest lesson in luck.

The source also skips the “blockade” variant rule, so same-color pieces may sit peacefully on one square.

Every simplification does the same job: squeeze the arguable coincidences out of the board and concentrate the conflict on the single focal point of eat and be eaten.

An extra fuse hides in the AI’s turn: the chain of sixes is capped, at most six moves in a row, so an extreme hot streak cannot shred the rhythm of the game.

Battleship

In Battleship the dice vanish completely, and the residue of luck is one opening bet.

Both fleets are laid out at random: 5 ships of length 5, 4, 3, 3, 2, occupying 18 squares, random orientation, overlap forbidden, adjacency allowed. After that the whole game is a pure search problem under incomplete information. The 10×10 enemy grid is a uniform gray field to you, and every shot returns one of two words: hit or miss.

Start with the opponent. The AI in the source fires uniformly at random. It picks a square on your board, avoids the ones already fired, and that is all: no pursuit logic after a hit, no probability density map, and sinking a ship does not automatically exclude its neighbors.

A uniformly random opponent means its “strategy” is fixed, and all the variance in the game comes from the quality of your search. This is the far right of the luck axis, where luck is only the opening bet on the layout.

Half of the player’s strategy can be proved rigorously.

The smallest ship is 2 squares, and any ship of 2 or more placed horizontally or vertically necessarily covers one black and one white square of a checkerboard coloring. So firing only at one color (at most 50 squares) guarantees every ship takes at least one hit. That single cut takes the worst-case cost of first contact from 100 squares down to 50.

After a hit the strategy switches to extension: probe along the row or column, establish the ship’s orientation, keep going until it sinks. Then mentally cross off the squares the sunk ship might have occupied.

Note the turn structure too: each side fires one shot per round, and a hit grants no extra time. Battleship has no “press the advantage” bonus; an edge accumulates one round at a time.

Every answer to a shot shrinks the information set. Battleship’s teaching value is making “asking the right question beats asking more questions” into a playable interface: a shot is one bit either way, but land that bit on a cluster of possibilities and it is worth half a fleet.

That search advantage can be quantified as well.

An AI firing uniformly without repeats is equivalent to shuffling your 100 squares into a random order and turning them over one by one. You have 18 ship squares, and the AI needs all of them to win. The expected maximum position in a random ordering is $\tfrac{k(N+1)}{k+1}$, which gives $\tfrac{18\times101}{19}\approx96$ shots.

In other words, a uniformly random opponent needs about 96 shots on average to wipe you out. A player who uses parity plus extension usually finishes in a few dozen.

That gap of nearly a hundred shots is not luck; it is the compound interest of information-set management. Every shot wastes a little less possibility than a random one.

Rock Paper Scissors and Simon Says

The last two points on the axis belong together, each representing a limit.

Rock Paper Scissors has the computer draw uniformly from three throws each round. That is exactly the mixed-strategy Nash equilibrium of roshambo, $\left(\tfrac{1}{3},\tfrac{1}{3},\tfrac{1}{3}\right)$.

Game theory states the meaning of equilibrium precisely: against an equilibrium strategy, any pure or mixed strategy the opponent picks yields the same expected payoff (zero here), and cannot be exploited.

So this widget is a conversation destined to draw. You cannot read the computer’s mind, because it has none. Any pattern of yours — three rocks in a row, switch after a win, never switch after a loss — has expectation zero.

The win-streak counter therefore becomes a display window for pure random fluctuation. Against a uniform opponent, win, loss and draw are 1/3 each, the chance of three wins in a row is $\left(\tfrac{1}{3}\right)^{3}=\tfrac{1}{27}$, and five in a row about $\tfrac{1}{243}$. That number on screen has no technical content whatsoever, and it still raises your pulse.

The only roshambo with any substance to it happens between two humans. People are poor random sources: they avoid repeats and alternate too much, and deviating from equilibrium is what gets them exploited. A uniformly random AI simply confiscates the whole craft of reading the opponent.

The converse holds too. Once an opponent deviates from uniform — say the probability of rock rises to $p$ — an optimal response exists immediately and pays immediately. Switching to paper has expectation $p\cdot1-(1-p)\cdot1=2p-1$, positive as soon as $p>\tfrac{1}{3}$.

Uniform is the only unexploitable point in roshambo; deviate by a hair and it is gone. Pinning the AI to that point declares the conversation mathematically over, and what remains is a drawing ceremony.

The streak counter has one small personality: a draw does not reset it, only a loss does. The record is unusually forgiving about draws, as if it too knows a draw owes nobody an explanation.

Reflex Games is the other limit: no opponent, no turn-based confrontation, and randomness appears in exactly one place — each round appends one of four colors to the tail of a sequence. The player repeats the whole sequence, one mistake ends the run.

The probability of guessing blind past round $n$ is $\left(\tfrac{1}{4}\right)^{n}$. The sequence space $4^{n}$ grows exponentially with the round, and each added color presses exactly 2 more bits into your head.

The human counter is chunking: cut the color string into short groups by rhythm and store those. The classic psychology result (short-term memory holds about 7±2 chunks) becomes the level ceiling directly here.

The widget also hides a quadratic time tax. Every round replays the sequence in full, each color lit for 400 ms with a 650 ms step. By round $n$ you have spent roughly $0.65\times\tfrac{n(n+1)}{2}$ seconds just watching replays. At round 12 that is about 51 seconds, and at that moment one slip of the hand wipes all of it.

Time cost grows with the square of depth, memory pressure grows linearly, and failure settles instantly. Reflex Games has the strongest rematch pull of the five, because it leaves one hundred percent of the blame to you.

Four color pads each carry a pitch (E4, A4, C#5, E5), so the replay arrives through sight and sound at once. The same sequence takes one more sensory channel, which makes chunking more efficient. Multichannel encoding is a free memory amplifier; the widget uses it and never explains it in the interface.

First move, rematch, and that narrow band

The five widgets share one easily overlooked parameter: who moves first.

Snakes & Ladders has red roll first, Ludo has red move first, Battleship has you fire first. All three racing or searching games hand the first move to the player.

First move is a real advantage in a race, and it can be computed cleanly. Let the two sides’ finishing rounds be identically distributed random variables $X,Y$; the first mover’s win rate is $P(X<Y)+\tfrac{1}{2}P(X{=}Y)$, that is $\tfrac{1+\text{draw probability}}{2}$, always strictly above half.

Even in perfectly symmetric Snakes & Ladders, the first move is half a step for free.

Commercial board games invented a whole compensation toolkit for this: resources to the second player, rotating first player, bidding for the first move. The widgets here choose the cheapest and most likeable option: the first move is simply yours, and if you lose you have no excuse.

Where “shuffle” sits on the axis is equally deliberate.

Battleship hands the layout entirely to the random number generator. You cannot even bring a layout trick into the game; both sides get equivalent fleet distributions in expectation.

The “random layout” button in Snakes & Ladders advanced mode goes further, expanding the shuffle to the entire transition matrix.

The mathematical meaning of a shuffle is moving luck from process noise forward into sampling of the initial condition. The opening is fair in expectation, but a layer of strategic depth is shaved off. Every layout trick used to be the private property of experienced players.

Snakes & Ladders runs a minute a game, a loss is the dice’s fault, and “again” costs nothing psychologically.

Lose at Ludo and you can blame the dice or the moves; the review has material for half a session.

Lose at Battleship and it is almost entirely your search that was not good enough.

The lower the luck share, the heavier a single game weighs, and the more the game relies on the belief “I can get better” to keep people. Rock Paper Scissors hands the result entirely to noise, then gives the noise a storyline with a streak counter. Simon Says has no dice and no opponent, yet makes you start over and over, because every failure points at exactly one responsible party.

Designing a luck curve is ultimately not about distributing probability but about distributing attribution: the more the dice carry, the lighter the player feels; the more the player carries, the more hooked they get.

Everything above allocates and consumes randomness; information entropy answers the more basic question of what uncertainty itself is worth. The next chapter applies the same entropy ruler to two opposite problems — compression and guessing.

Entropy: Compression and Guessing

Information entropy H measures uncertainty: every possible value of a random variable contributes a “surprise” of log₂(1/p), and the probability-weighted average of that surprise is the entropy — on average, the minimum number of bits you need to express the variable or pin it down.

The same ruler measures two problems pointing in opposite directions. One is compression: the text’s distribution is known, so how far can you push code lengths down toward the entropy bound (Huffman coding). The other is guessing: the answer is unknown, so how few questions does it take to corner it (Wordle’s optimal strategy). This chapter does both in one sitting.

First Half: Huffman Coding

Where Fixed-Length Coding Wastes Space

ASCII hands every character 8 bits — equal length, tidy, and for natural language a waste.

In an article ‘e’ shows up hundreds of thousands of times and ‘z’ three times, yet they take up the same space.

The whole idea of compression is one sentence: give common characters short codes and rare ones long codes.

But that long-and-short pairing instantly hits a fatal problem: how does the decoder know where the boundaries are?

If A=0, B=1, C=10, is a received “10” B plus something, or C?

With A=0 and B=01, the string “01” never resolves.

To decode correctly, the code set must satisfy one property: no code is a prefix of another (the prefix-free property).

Then reading left to right, each complete code splits off unambiguously.

The Greedy Construction

In 1951 David Huffman, a graduate student at MIT, invented this construction for a course’s final assignment (reportedly to dodge the exam), and “high frequency, short code” went from intuition to a provably optimal solution.

Today ZIP, JPEG, and MP3 all carry it in their inner layers.

The construction is simple enough to dictate out loud:

1. Tally each character’s frequency and enqueue each as a single-node tree;
2. Take out the two trees with the smallest frequencies, merge them into a new tree (frequency = their sum), and put the new tree back in the queue;
3. Repeat until one tree remains. Every leaf of that tree is a character: go left for 0, right for 1, and the path from root to leaf is that character’s code.

Why is this greedy correct?

The core is an exchange argument, in two steps:

• The two rarest characters must sit at the deepest level. Suppose the least frequent character x in an optimal tree is not at the deepest level while some frequent character y is; swap the codes of x and y and the total length only shrinks or stays the same, contradicting optimality;
• The two deepest leaves are siblings. If the deepest level held a single leaf, deleting its sibling level and moving that leaf up one level would shorten the code, again contradicting optimality. So an optimal tree has at least two leaves at the deepest level, and pairing them as siblings costs nothing.

“Merge the two smallest” enforces exactly these two facts, so every step preserves the optimal substructure.

The greedy holds.

This is the standard template for proving a greedy algorithm: exchange argument plus optimal substructure.

A Minimal Example

Walk the process with four characters.

Take frequencies A=8, B=4, C=2, D=1 (15 in total):

1. The two smallest are D(1) and C(2); merge into 3. The queue holds A(8), B(4), new(3);
2. The two smallest are new(3) and B(4); merge into 7. The queue holds A(8), new(7);
3. Merge A(8) with new(7), and the tree takes shape.

Label every left edge 0 and every right edge 1, and the code table comes out A=0, B=10, C=110, D=111.

The most frequent character, A, costs 1 bit; the rarest, D, costs 3.

Average code length (8×1 + 4×2 + 2×3 + 1×3) ÷ 15 = 25/15 ≈ 1.67 bits.

Fixed-length coding of four characters needs 2 bits, so this saves about 17%.

The tree itself is worth a glance: the two rare characters get pushed to the deepest level sharing one subtree, and the exchange argument’s two conclusions — rarest at the bottom, deepest as siblings — are visible to the naked eye in the result.

While we’re at it, the entropy of this distribution: H = −Σp·log₂p ≈ 1.64 bits.

Huffman’s 1.67 sits only 0.03 above the physical bound. On a small alphabet the cost of rounding to integers is negligible.

The richer the distribution and the more characters there are, the larger the relative waste of “every code length must be an integer” — which is exactly where arithmetic coding and ANS get their edge on large alphabets.

Reconciling with the Entropy Bound

Information theory gives compression its physical lower bound: the average code length L̄ of a binary prefix code satisfies

H is the Shannon entropy of the character distribution.

Huffman coding lands inside that interval. It is optimal in the world of whole-character coding, but in general it cannot reach H, because:

• Huffman code lengths must be integers. The entropy-optimal allocation is usually fractional (say a character’s ideal length is 2.3 bits), and Huffman can only give it 2 or 3, leaking a little at every rounding;
• it only looks at single-character frequencies; correlations between characters (‘q’ is almost always followed by ‘u’) go entirely unused.

The techniques that close these two gaps came later: arithmetic coding allows fractional code lengths and pushes L̄ to nearly H; context modeling (PPM, the LZ family) exploits correlations.

Modern compressors such as DEFLATE are a combination punch: LZ77 finds the repeats, Huffman codes what’s left.

Huffman doesn’t fight alone, but it’s always on the field.

Recent news on that lower bound: arithmetic coding spread slowly because of patents, and once the patents expired it met a newer rival.

ANS (asymmetric numeral systems) matches arithmetic coding’s ratio at far lower computational cost, and it has become the core entropy coder of modern compressors like Zstandard.

The reason Huffman hasn’t been shoved aside is plain: small tables, fast decoding, simple implementation — where “good enough and fast” is the requirement, it’s still the handiest knife.

Engineering Details

Tree-shaped decoding is unfriendly to hardware and to high-speed decoders (you walk the tree bit by bit, and it’s cache-hostile).

What actually ships in engineering is canonical Huffman: store no tree, only each character’s code length, then reassign the codes by a fixed rule (equal lengths assigned consecutively in lexicographic order).

The decoder advances with a small “first code – offset” table, which is branch-prediction friendly — this is the form DEFLATE takes inside zlib.

Another engineering point: the code table itself has to travel with the data.

For short messages the table’s overhead can eat the compression gain.

That’s why a few dozen bytes of string often compress into something bigger (header overhead on top), and why every compression algorithm has a minimum worthwhile length.

Where the table comes from involves another trade-off.

The most direct route is two passes: count frequencies first, encode second — at the cost of reading the whole file up front, which streaming scenarios hate.

Adaptive Huffman (FGK, Vitter’s algorithm) goes single-pass instead: encoder and decoder start from the same initial tree and update the tree shape in lockstep after every character, dropping the pre-count at the cost of much more complex update logic.

DEFLATE picked the compromise. LZ77 kills most of the repeats first; the remaining byte stream gets frequency counts per block with a Huffman table per block, and the counting window stays small enough to accept.

Implementation Notes

Writing it yourself (a job under a hundred lines) runs into four concrete problems, so here’s the vaccination:

• Use a heap, not an array scan for the minimum. A min-heap pulls the two smallest trees in O(log n) per round and O(n log n) overall; a linear array scan is O(n²). It still runs on tens of thousands of characters, but there’s no reason to;
• How to order ties at equal frequencies. Different merge orders give differently shaped trees with the same average code length (the optimal tree isn’t unique), but encoder and decoder must use the same tree. Pin the rule down in writing (ties by character order, say), and carry enough information in the table for the decoder to rebuild that same tree. This is also the motivation for the next point;
• Store code lengths in the table, not codes. Store each character’s code length (canonical Huffman) and let the decoder rebuild the codes by the fixed rule; the table shrinks from “character plus binary code string” to “character plus one small integer”. This is why canonical Huffman is irreplaceable in engineering;
• Bit packing and tail padding. The code stream is a bit stream and must be packed into bytes before it hits disk. The slack in the last byte either records the valid bit count or follows an agreed padding value. Skip this step and the decoder reads ghost characters off the end of the file. DEFLATE caps code lengths at 15 bits so any code fits into a nibble-sized field.

Feed a real passage (this article, say) into the Huffman tree visualization and watch three things: whether high-frequency letters get the shortest codes, whether the tree puts lower frequencies deeper, and what happens when you swap in text with a flatter distribution — higher entropy, worse compression.

The only money compression can make is the unevenness in the distribution.

Second Half: Wordle

Compression spends a distribution’s unevenness on code length; guessing runs it backwards, actively manufacturing questions to eat the answer’s uncertainty bite by bite.

Wordle’s rules: six chances to guess a five-letter word, with three-color feedback after each guess. Green means the letter is right and in the right place, yellow means the letter is in the answer but elsewhere, gray means the letter isn’t in the answer.

The rules are simple, but “which word should I guess next” is a serious mathematical question.

First, Tell the Two Pools Apart

Half the strategic space comes from this: the answer pool and the guess pool are not the same pool.

The original Wordle’s answer list holds about 2300 common words, but roughly 13000 words are legal guesses.

You may guess any legal five-letter word; the answer is only ever drawn from the common ones.

So “spend a word that doesn’t look like an answer to buy information” (the off-pool play, later in this chapter) is legal by construction: a guess needs to cut finely, not to look like an answer.

Plenty of human players never learn this, keep treating candidates as guesses, and throw away nearly 6× the questioning space for nothing.

A Guess Is a Question

The key shift in perspective: a guess is not an attempt at the answer, it’s a question put to the answer pool.

The color combination in the feedback is that question’s answer, and it cuts the 2000-odd candidates into piles. Next round you only search the pile your feedback points at.

Say the pool holds guess and guest and you play gauge: if the answer is guess, the feedback is some green-green-gray-gray-gray pattern; if it’s guest, the feedback differs.

A good guess means this question cuts the answer pool as evenly and as finely as possible. Every pile small, fewer choices next round.

Entropy: A Ruler for How Finely It Cuts

Information entropy is exactly the tool for that.

For a candidate guess g that cuts the answer pool into k piles, with nᵢ words in pile i and N words in total, the expected information of this guess (in bits) is:

Reading it intuitively: if a guess splits 2000 words evenly in half, 1000 each, the entropy is 1 bit. All you gained was a coin flip.

If it cuts 100 piles of roughly equal size, the entropy approaches log₂100 ≈ 6.6 bits, and one move takes the candidates from over a thousand down to about 20.

Five-letter feedback has only 3⁵ = 243 patterns in total (three colors, five positions), so the theoretical single-guess ceiling is log₂243 ≈ 7.9 bits. In practice it falls well short, because letter patterns aren’t uniformly distributed.

Tallying the total budget shows how roomy the game is: the pool is about 2300 words, so the total uncertainty is log₂2315 ≈ 11.2 bits.

A good opener takes about 5 bits in one move; the second move, computed against the pool, takes about 4 more. In theory two guesses should leave single-digit candidates.

Reality wobbles, but this is why published solvers reliably finish at around 3.5 guesses on average: six chances aren’t six strokes of luck, they’re three times the information budget you need.

One implementation-level warning along the way: when you write the feedback comparison, repeated letters are the most common bug source.

If the answer has one R and the guess has two, the second R must not go yellow.

The official Wordle rule consumes greens left to right and then grants yellows by remaining count, so if you hand-roll it, build test cases with repeated letters on purpose.

Brute Force: The Opening-Word Leaderboard

The computation is mechanical: for every legal guess g and every candidate answer a, compute g’s feedback pattern against a, bucket by pattern, and apply the formula above.

That’s about 13000 × 2300 feedback comparisons, which any scripting language finishes in seconds.

The public analyses (answer lists differ by a few hundred words between authors, so the exact numbers drift) all reach the same conclusion:

• A good opener leaves an expected 60–100 candidates, corresponding to roughly 5 bits. One move cuts away over 95% of the possibilities;
• The top of the rankings holds words like SLATE, CRANE, SALET, TRACE, SOARE, and RAISE, and their common trait is obvious: they cover high-frequency letters, and no letter repeats. In English, E, A, R, O, T, S, I, L, and N are the most frequent; a word with five distinct high-frequency letters wins by nature;
• The counterexamples agree: words like JUJUS and FUFFY, all repeated and low-frequency letters, have pitifully low entropy. Against most answers they cut out only a sliver of information.

One emphasis: there is no unique answer to “which word is first”.

Shift the answer list by a few hundred words and the ranking reshuffles; weight “hit the answer” and “shrink the pool” differently and the result changes too.

But the direction — high-frequency letters, no repeats — is stable.

Fixed Combos vs. Recomputing from Feedback

One popular strategy is a fixed two-word combo: SLATE then ROUND (or CRANE plus POILS), covering a dozen or so high-frequency letters in two moves.

The appeal of that play is that it saves thinking. No actual computation, and two moves usually crush the remaining candidates to a few dozen.

But it isn’t optimal.

The strict approach under the entropy framework: at every step, recompute the next guess with the highest entropy against the current remaining pool.

The fixed combo wastes information. If the first word already eliminated every answer containing R, the R in the second word is pure waste.

Measured gaps usually stay within a few tenths of a guess, so for ordinary players the combo is actually good value.

Only for someone chasing the limit on average guesses does pool-based computation make sense.

One counterintuitive corollary: once the candidates are down to two or three, the maximum-entropy guess need not be one of them.

Say the remaining candidates are MATCH, CATCH, PATCH. They differ only in the first letter, so guessing an off-pool word containing M, C, and P separates all three in one shot, a better deal than betting a third on one of them (the cost is one extra move).

One Game, Walked Through (Illustrative)

String the framework into a complete game. The numbers are illustrative, there to show the rhythm rather than any real game.

Open with SLATE, and say the feedback cuts nine tenths of the candidates, leaving about 60 words.

For the second jump, recompute entropy against the remaining pool and pick the word that cuts those 60 most finely. It very likely isn’t any candidate word. After the feedback, single digits remain.

The third jump is either already the obvious unique answer, or one off-pool discriminator among two or three candidates.

Done inside four jumps, which is exactly the rhythm the 11.2-bit total predicts.

Two disciplines from real play are worth stressing: recompute against the current pool at every step (the best word for jump one is almost never the best for jump two), and cross out impossible words by hand the moment feedback arrives (the pool in your head has to stay in sync with the theoretical pool).

Otherwise the prettiest entropy number is computed against a stale pool.

Hard Mode

Hard Mode requires every confirmed hint to be reused.

That heavily restricts off-pool play. You can no longer freely ask the most informative question, only pick among words that satisfy the constraints.

So in hard mode:

• the opening word matters more, because the room to maneuver shrinks;
• when two vowels are confirmed but the candidates are still many, you get forced into guessing step by step;
• a practical compromise: even outside hard mode, prefer guesses that don’t create scattered constraints and keep your freedom, so switching back to hard mode doesn’t feel foreign.

To verify the conclusions hands-on, just start a game: Wordle.

Entropy prices uncertainty, while primes are number theory’s most deterministic objects — yet scattered into a grid, even they grow statistical structure. The last experiment started as a doodle during a dull academic talk.

The Ulam Spiral: Stripes of Primes

In 1963, the mathematician Stanisław Ulam doodled through a long, dull academic talk: he laid out 1, 2, 3, … in a square spiral, ring after ring, and circled the primes. He expected uniform noise, and saw diagonals instead — masses of primes lined up along the slant in clear stripes. Primes are defined by divisibility, with nothing to do with how they are arranged, yet they revealed structure in one of the plainest two-dimensional layouts there is. This chapter lays the phenomenon out: where the diagonals come from, how they connect to the quadratic $4n^2+2n+1$, what engineering a picture like this takes, and why a toy visualization keeps producing serious number-theory conjectures.

Hands-on versions: Ulam Spiral and Numeral.

Construction Rules

The construction rule fits in one sentence. Start from 1 at the center, go one cell right, one up, two left, two down, three right, … each length runs twice, then grows by one.

So the run lengths are 1, 1, 2, 2, 3, 3, 4, 4, … With the center as the origin, continuing this way gives every natural number exactly one cell.

The first 25 numbers lay out like this (asterisks mark primes):

1
  *  16  15  14   *
2
 18   5   4   *  12
3
  *   6   1   *   *
4
 20   *   8   9  10
5
 21  22   *  24  25

Nine primes in 25 numbers, and the eye already finds slants: 3 and 13 form one line, 5 and 17 another. With more numbers those lines keep extending.

The construction immediately yields a few provable geometric facts, and they are the foundation for everything below.

The $k$-th ring holds exactly the numbers from $(2k-1)^2+1$ to $(2k+1)^2$, and its side length is $2k+1$.

Squares of odd numbers land strictly on one diagonal. $9$ sits at $(1,-1)$, $25$ at $(2,-2)$, $49$ at $(3,-3)$, … so $(2k+1)^2 = 4k^2+4k+1$ lies on the ray $y=-x$.

Extend that diagonal through the center to the other side and the ray carries the sequence $1, 7, 21, 43, 73, 111, \cdots$, whose general term is exactly:

The third fact is worth verifying by hand. At $n=1$ it gives 7 (the lower left corner), $n=2$ gives 21, $n=3$ gives 43, $n=4$ gives 73. Count cell by cell along the construction rule and they really are strictly collinear.

This is no coincidence but necessity, and the next section spells the necessity out.

Every Diagonal Is a Polynomial

Why do diagonals and quadratic polynomials correspond one-to-one? Start with how the coordinates are computed.

Walking the right/up/left/down cycle at run lengths 1, 1, 2, 2, 3, 3, coordinates and values can be generated together:

1
x = 0, y = 0, n = 1, seg = 1
2
the direction cycles right → up → left → down
3
walk seg steps per direction, recording (x, y, n) each step and incrementing n
4
after every two directions, seg increments

Now stare at one ray out of the center. Its $r$-th cell necessarily sits on the $r$-th ring, and every number on the $r$-th ring is squeezed between $(2r-1)^2$ and $(2r+1)^2$ — an interval around $4r^2$ spanning less than $8r$.

So the value at the $r$-th cell of a ray must take the form:

an integer-coefficient quadratic. The leading term $4r^2$ is pinned by the ring structure; $b$ and $c$ are decided by the ray’s direction.

The spiral has as many such polynomials as it has rays. The Ulam spiral is essentially a machine for spreading the values of integer quadratics across a grid, and the prime marks let us see each polynomial’s prime output directly.

This view immediately yields two testable corollaries.

First, on a ray with odd $b$ (say the due-east one, $4r^2 - 3r + 1$: 2, 11, 28, 53, 86, …), values alternate with the parity of $r$, half of them are even, and the prime density is halved by construction. On the picture those rays look uniformly dim.

Second, a ray with the right $c$ has a fixed factor across the whole sequence. The line through $(2k+1)^2$, for instance, is all squares apart from 1, black the whole way down.

Bright lines and dark lines each have an algebraic explanation.

Diagonal Enrichment

Why One Diagonal Can Be Especially Bright

The reference frame for enrichment is the background density the prime number theorem supplies. A number of size around $4n^2$ is prime with probability roughly $1/\ln(4n^2)$, decaying slowly as $n$ grows.

If a polynomial’s values behaved like random numbers, its prime frequency along the diagonal should hug that background line. Enrichment means a departure from randomness, and the reason for the departure hides precisely in modular arithmetic.

The intuitive argument runs like this. A random integer escapes division by a prime $p$ with probability $1 - 1/p$. A polynomial $N(n)$ only visits some residue classes mod $p$; call $\rho_p$ the fraction of classes on which it avoids zero — then $N(n)$ escapes $p$ with probability $\rho_p$.

Multiply the correction factors of all small primes and you get the density multiplier of $N(n)$ relative to random numbers:

A multiplier above 1 makes a bright line on the picture; below 1, a dark one.

The conjecture has an earlier source. Bunyakovsky proposed in 1857 that if an integer-coefficient polynomial has a positive leading coefficient, is irreducible over the positive integers, and has no fixed prime divisor (no prime divides every value), then it should take infinitely many prime values.

$n^2+1$ is the simplest sample satisfying all three premises, and $n^2+n+41$ qualifies too. They became the central knot of the whole conjecture web, unresolved for more than a hundred and sixty years.

Hardy and Littlewood’s Conjecture F in 1923 pushed it to a quantitative form: the prime density of a quadratic equals the background density times a constant determined by the coefficients. They even gave the formula for how that constant multiplies out over modular arithmetic.

The statistics Ulam published with colleagues in 1964 confirmed it as well: diagonal enrichment is a measurable real phenomenon, not an optical illusion.

Dissecting $4n^2+2n+1$

Take the center diagonal’s polynomial for practice. List the first few terms and factor them:

A structural pattern shows up at once. Mod 3, $4n^2+2n+1$ is equivalent to $n^2 - n + 1$, which is identically 0 when $n \equiv 2 \pmod 3$. Every third value is divisible by 3 (rows 2, 5, and 8 of the table show the period neatly).

Interestingly, a random number also escapes 3 with probability $2/3$, so this line neither gains nor loses on the factor 3. Whether it gains or loses takes a prime-by-prime count: plug every residue class of $n$ into $N(n)$ mod $p$, tally the fraction $\rho_p$ landing on the zero class, then multiply out $\rho_p / (1-1/p)$ as correction factors.

For this line, the 3 factor breaks even; what actually lifts the density is the extra avoidance it earns on a handful of primes.

Walk the prime 5 through completely. For $n$ from 0 to 4, $4n^2+2n+1$ mod 5 gives $1, 2, 1, 3, 3$ in turn — the zero class is never touched. The equivalent algebraic test is the discriminant of $4n^2+2n+1 \equiv 0 \pmod 5$, namely $4 - 16 = -12 \equiv 3 \pmod 5$, and 3 is not a quadratic residue mod 5, so the equation has no solution.

Hence $\rho_5 = 1$, the correction factor is $\frac{1}{1-1/5} = \frac{5}{4}$, and the line picks up a free quarter of density on the prime 5.

Work through mod 2, mod 7, and the larger primes, multiply out the line’s total multiplier, and you can predict its brightness tier on the picture.

Every diagonal’s brightness can in principle be computed by hand this way. The mysterious stripes are, in algebraic language, a family of computable modular periodicities. Even which positions must be composite runs on a period, and that is the root of why the stripes look orderly.

The Extreme Case

The extreme case of enrichment is $n^2 + n + 41$, found by Euler in 1772: for $n$ from 0 to 39, every value is prime.

Why is it so strong? The modern explanation runs through algebraic number theory. 41 belongs to the Heegner number sequence tied to imaginary quadratic fields of class number 1 (1, 2, 3, 7, 11, 19, 43, 67, 163), and the discriminant of $n^2+n+41$, $1-164 = -163$, corresponds exactly to the last Heegner number.

The polynomial’s values avoid 0 mod every small prime $p < 41$. Every obstacle is pushed past 40, so the first 40 terms contain not a single composite.

Lay the spiral out again with 41 at the center and this polynomial’s values fall strictly on one diagonal, forming one of the brightest lines in the picture.

The famous Ramanujan near-integer, where $e^{\pi\sqrt{163}}$ misses an integer by about $10^{-12}$, has the same 163 behind it.

The brightest diagonal on an Ulam spiral shares one deep parameter with the class number problem for imaginary quadratic fields. Play with a toy long enough and you bump into the last chapters of the textbook.

Engineering the Picture

The other half of visualization is engineering: with tens of thousands to millions of cells, how do you test primality efficiently and draw it.

Trial division one number at a time won’t do. Testing $N$ numbers up to $\sqrt{N}$ costs $O(N\sqrt{N}/\ln N)$ overall, and a million cells already stutter.

The standard answer is the sieve of Eratosthenes. Allocate a boolean array of length $N$, start from 2, and strike out each prime’s multiples in batches: $O(N \log \log N)$ overall, milliseconds at the million scale. When memory is tight, use a bitset at one bit per number — a million numbers fit in a bit over a hundred KB.

When you need to test a single enormous number (say, whether one particular polynomial value is prime), switch to a probabilistic test like Miller–Rabin. The sieve handles batch marking of cells, the probabilistic test handles single-point checks; two tools, each owning its stretch.

Miller–Rabin in one sentence: use the contrapositive of Fermat’s little theorem, pick a random base $a$, and run a few modular-exponentiation checks. If the number is composite, each check exposes it with probability at least three quarters. After k rounds the miss probability is at most $4^{-k}$, and thirty rounds are already less likely than a hardware bit flip.

The deterministic variant more common in production: for integers up to 64 bits, run each of the first twelve primes (2 through 37) as a base once, and you get a rigorous verdict at the cost of one modular exponentiation per round.

One practical boundary remains: several-hundred-digit numbers go straight to Miller–Rabin, anything within 64 bits takes the deterministic bases, and batch cells below $10^{12}$ honestly take the sieve. Before choosing a tester, check whether the input is one number or a contiguous range.

The core rendering decision is not to give every number a DOM node. Tens of thousands of divs already drag the page into stutter; a million means a blank screen.

The right move is to draw onto a Canvas. $N$ numbers map to $N$ pixels, a million prime cells become one 1000×1000 bitmap, zooming goes through a coordinate transform, and the browser’s 2D rasterizer carries it without effort.

On the interaction side, dragging a slider to set the range and redrawing on any parameter change is state-driven, and the image itself stays a purely functional map from data to bitmap.

The combination of a sieve for data and a Canvas for pixels is the universal substrate of nearly every number-theory visualization; change the spiral and only the coordinate function changes.

Visualization as a Conjecture Engine

From “Looks Like” to “Can Be Falsified”

The real methodological value of the Ulam spiral is that it compresses the grand, shapeless question of whether primes are distributed regularly into a series of concrete, falsifiable little propositions.

“The diagonals are bright” is a visual impression. In mathematical language it becomes “the prime density of $4n^2+bn+c$ exceeds the background”. One question further and you are at the core of an open problem: does $n^2+1$ produce infinitely many primes — one of Landau’s four problems from 1912, still unresolved.

Visualization solved nothing, but it did something just as important: it pointed attention at the right object.

That is the shared recipe of nearly every successful visualization. Find a coordinate system that naturally throws structure in your face, let the eye pre-filter for attention, and the remaining questions turn into propositions you can actually test.

A Control Group

The same primes, laid out differently, give a completely different picture.

The Sacks spiral (1994) places $n$ on an Archimedean spiral of radius $\sqrt{n}$ and angle $2\pi\sqrt{n}$. The effect is that perfect squares line up strictly on one ray: at $n = k^2$ the radius is exactly $k$ and the angle exactly $k$ full turns, so the direction returns home. Primes, meanwhile, cluster along a family of inward-curling curves, each of which again corresponds to the values of a quadratic.

Neither picture is more right; they are shadows of the same arithmetic facts under different projections. The Ulam spiral is good at exposing linear-arrangement patterns, the Sacks spiral at exposing square-law patterns.

Reading anything serious out of these pictures takes several coordinate systems as basic literacy. A line that appears in only one layout tells you about the layout. One that recurs in different guises across many layouts is more likely a property of the numbers.

Beware the Reverse Error

The reverse error needs guarding too. Evolution tuned the human eye’s sensitivity to straight lines and continuity extremely high, so it draws connections in noise by instinct.

The Ulam spiral’s diagonal enrichment is a statistically testable real phenomenon (count primes along a diagonal, compare against random segments of the same length, and the ratio is significantly above 1). But the size of the enrichment is not as dramatic as a screenshot suggests. Even the brightest diagonals usually run only one to two times the background density; the visual system amplifies the difference into stripes.

So the rigorous stance is: the eye nominates candidates, the counter delivers the verdict. Visualization proposes, statistics disposes; neither step substitutes for the other.

A Little History

Ulam’s own account of the discovery is notably restrained. At a conference talk in 1963 his attention drifted, he scribbled the integers out in a spiral and marked the primes offhand, and the diagonals showed up at once.

He and his colleagues Stein and Wells soon did the quantitative work, counting prime density by angular sector and confirming the enrichment exceeded random fluctuation. The results appeared as a paper in 1964 with a title as plain as a lab notebook.

What really brought the pattern to a wide audience was Martin Gardner. In March 1964 his Mathematical Games column in Scientific American devoted a whole installment to the spiral, with illustrations from hundreds of pages of computation, and reader letters poured into the editors.

One detail from that history is worth keeping: Ulam’s doodle, the quantitative work by Stein and Wells, and Gardner’s column — remove any one of the three and the pattern would have stayed one man’s distraction.

What takes one drag of a range slider in the tool today needed hundreds of cells computed by hand in 1964 to draw a single corner. Compute dropped the barrier to seeing structure to zero; the barrier to explaining it has not moved in over half a century.

Beyond the Spiral

Any discussion of what primes look like runs into a more fundamental question: what does a random distribution look like?

In 1936 Cramér gave a famous null model, now called the Cramér model. Assume each integer $n$ is “prime” independently with probability $1/\ln n$; the artificial prime set so generated should statistically reproduce the prime number theorem.

Lay the Cramér primes into an Ulam spiral too and you get an almost convincing picture. There are speckles, there are short streaks, but no long diagonals cutting across the whole frame the way the real spiral has them.

This control experiment sharpens the definition of enrichment: structure is not looking tidy, but long-range correlation beyond the random model. And the source of that long-range correlation is precisely modular arithmetic — the periodic behavior of polynomials mod p — which the Cramér model lacks, which is why it cannot draw stripes.

The same reasoning explains why twin primes are often treated as the spiral’s advanced observation target.

The candidate density of twin pairs (p and p+2 both prime) is corrected by the twin prime constant $2C_2 \approx 1.32$. Another constant defined by a product over modular arithmetic, from the same machine as the quadratic density constants.

Mark the smaller member of each twin pair into the spiral and the stripes come out sharper than primes alone. The reason is plain: apart from (3, 5), a twin pair’s members must have the form $6n-1$ and $6n+1$, so their positions mod 6 are completely pinned.

Once that layer is clear, any bright or dark patch on the spiral makes you ask first: what is this picture’s random baseline, and which modulus decides the departure from it. That instinct is worth more than any single result.

Try It Yourself

In the Ulam Spiral, crank the range up, look at the stripes as a whole, then pick the brightest diagonal, copy down its value sequence, and try three things: guess the general term (the leading coefficient is almost certainly 4), test the modulus against each small prime, and find the period where every k-th value is divisible by p.

Walk that once and the Hardy–Littlewood heuristic turns from a noun into a feel.

The three conjectures below step up in difficulty, and all of them can be checked by hand or with ten lines of script.

Extreme case of a dark line: the diagonal through the odd squares ($4k^2+4k+1 = (2k+1)^2$), where every value except the central 1 is a perfect square. That line should be black all the way. See the picture above.

The center line’s mod 3 beat: $4n^2+2n+1$ is divisible by 3 when $n \equiv 2 \pmod 3$. List the first 50 terms of this line, mark every third position as necessarily composite, then compare the phase of the beat against its neighbor $4n^2-2n+1$ (dark at $n \equiv 1 \pmod 3$).

Odd-coefficient rays halve: pick any ray with odd $b$, count the primes in its first 500 terms, and compare with a neighbor having even $b$. The ratio should come out near 1/2 (the parity alternation eats half the candidates).

One idea is worth nailing down before you start: primality has nothing to do with the numeral base, and the pattern only sees the numbers themselves.

Some suspect the diagonals are an artifact of decimal notation. They are not. Rewrite every number on the grid in another base (switch freely among binary, octal, and hex with Numeral) and the number is still the same number, not one divisibility relation changes, and the spiral pattern does not change either.

What visualization exposes is a property of the numbers themselves, and that is what separates it from numerology.

From rounding error to prime stripes, the shared motif of this long read is this: deterministic answers can emerge reliably from mass random sampling, and the price of error and uncertainty is printed on the label.

Thanks for reading! Follow me if you'd like~

Numbers, Randomness, and Probability

Sun May 10 2026

24778 words · 125 minutes

Algorithms & Data StructuresGame MathAlgorithmsProbabilityStatistics

---

© MuxiaoWF | CC BY-NC-SA 4.0

Share

Share this article

X (Twitter)TelegramRedditFacebookEmailQQ

Close

Close