Peak state against passes, for two splitting rules on two distributions

Peak state against passes, for two splitting rules on two distributions

Exact selection of the 0.5 quantile of 32,768 values, in p passes, with the state measured at its peak during the run. Every point is an exact answer — a run that returned anything else stops the build — so the vertical axis is the price of exactness rather than a price paid for being approximately right. The line at the top is what one pass costs: 1,048,576 bits, because an exact one-pass selector has to keep the stream, and the floor under that is a counting argument this collection performs rather than quotes. The equal-width rule needs no knowledge of the data and gets 37 times smaller as passes are added — on data spread evenly. On a heavy tail it collapses, because an equal-width cut of a range containing almost no data narrows the range and not the count; the sampled rule, which spends half its passes finding out where the data is, is barely affected. Both axes are logarithmic.

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

3 essays call pass-state. 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.