FRUGAL STREAMING estimate a quantile with a single integer of memory — and a nudge
How little state can estimate the median of a stream? Frugal-1 answers: one integer. It holds a single estimate and nudges it — up by one when a sample lands above it, down by one when below. Over a stationary stream the estimate random-walks to the median and stays, because above and below balance there. No histogram, no reservoir, no sorted buffer — a correct exact quantile must store (or sort) the whole stream; Frugal-1 stores one number and still converges. It is the extreme point of the streaming discipline: the smallest possible summary that still answers a question about the whole distribution.
THE TECHNIQUE one estimate; x>est → +1, x<est → −1; walks to the median
A stream centred on a value. The demo nudges a single integer toward the median, up or down by one per sample: live demo
HISTORY & CREDIT Ma, Muthukrishnan & Sandler, 2013
“Estimating a quantile needs a buffer.” — Frugal-1 uses one integer and a ±1 nudge; the estimate walks to the median because above and below cancel there. The whole distribution, summarized in a single number. cited
2013 · Qiang Ma, S. Muthukrishnan & Mark Sandler — “Frugal Streaming for Estimating Quantiles: One (or Two) Memory Suffices.” Frugal-1 · a single stored estimate, nudged ±1; Frugal-2 adds a step size for faster convergence. now · quantile estimation on constrained devices; a limiting case beneath t-digest and the P² algorithm.
One integer, a nudge each way; equilibrium sits at the median because that is where up and down agree. The least memory that still knows the middle. Frugal-1, 2013
RECOMMEND FOR I-13 the one-integer median tracker, on the compiler
On the canonical compiler, a stream at 5 nudges the single estimate up to 5 and holds — the state carried is one number:
$ i13 run op_frugal.i13 # est +/- 1 per sample; walks to the median
RUN OK · 189 step(s) · peak stack 6 · call depth 6
estimate = 5 -- one integer of state tracked the median of the stream
Recommend — the batch's second keeper shot, and the one i13 fully enacts. Unlike Morris, Frugal-1's mechanism needs no randomness to demonstrate on a stationary stream: i13 threads a single integer, nudges it ±1 per sample, and it climbs to 5 and stops. The supplement to correctness is stark: a correct exact quantile must retain the entire stream (to sort or select); Frugal-1 retains one number and still locates the median — a property no exact selector can have. And it is load-bearing: the equilibrium sits at the median because the ±1 nudges balance there — alter the mechanism (bias the nudge, or store more) and either the answer moves or the one-integer property dies. This is the closest the batch comes to the B39 bar with the mechanism actually running. The honest caveat for the panel: convergence is statistical (the walk approximates), and “one integer” is again a memory claim, which the panel may judge a resource property rather than a structural axis distinct from the five.