Week 54: TAOCP 3.4.1 Numerical Distributions

Turning uniform random numbers into other distributions: random integers in a range, general discrete distributions (including the alias method), the normal distribution via the polar method and others, and exponential, gamma, binomial and Poisson distributions.

Time About 9 hours this week

Why it matters

Every simulation, game loot table and load generator needs non-uniform randomness. The modulo-bias trap for random integers is one of the most common bugs in real code.

Before you start

3.2 Generating Uniform Random Numbers
Basic probability distributions

How to approach it

Implement: unbiased random integer in [0, k), the alias method for a weighted die, and the polar method for normals. Histogram each to check. Skim the more exotic distributions.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Using rand() % k, which is biased when the generator range is not a multiple of k.
Taking the low bits of a weak generator for small ranges.