Algorithm R: how often each of 32 positions is sampled, 40,000 runs

Algorithm R: how often each of 32 positions is sampled, 40,000 runs

A uniform sampler chooses every position of the stream with probability k/n = 0.125, whatever order the items arrive in. The shaded band is four standard deviations of the estimate at 40,000 runs, which is what a correct sampler looks like at this trial count. The largest departure measured here is 3.3%. Each run costs 166 random bits, which is the other axis this sampler is measured on.

Drawn at 690 × 370, wide on the page. Everything above is what reservoir-frequency returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

1 essay calls reservoir-frequency. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.