The floor under a window

This site has three kinds of lower-bound argument and this essay is the fourth application of the third.

Leaf counting floors comparison sorting: a decision tree with $n!$ leaves has depth at least $\log_2 n!$, which is computable exactly. An adversary floors graph connectivity: whatever an algorithm has not looked at, an adversary can make decisive. Counting memory states floors exact distinct counting: if two inputs leave the algorithm in the same state and can be extended so their answers differ, the algorithm is wrong on one of them.

The windowed count falls to the third, and it falls more cleanly than the distinct count did.

The claim #

Any algorithm that reports, after every arrival, the exact number of ones among the last $W$ items of a bit stream must use at least $W$ bits of state.

Not $W$ bits up to a constant. Exactly $W$, because there are $2^W$ possible windows and every one of them needs its own state.

The argument, in three sentences #

Take two distinct bit strings $u \neq v$ of length $W$ and suppose the algorithm is in the same state after reading each of them.

Let $d$ be the oldest position at which they differ — the leftmost one — so that $u_d \neq v_d$ and $u_i = v_i$ for all $i < d$. Now feed both continuations $W - d$ zeros. The window after $u$ holds $u_d u_{d+1} \dots u_W$ followed by zeros, and the window after $v$ holds $v_d v_{d+1} \dots v_W$ followed by the same zeros. Those two windows agree everywhere except in the single position $d$, so their counts differ by exactly one.

An algorithm in the same state after $u$ and after $v$ is in the same state after both continuations, so it reports the same number for both, and one of the two reports is wrong. Therefore no two distinct windows may share a state, there are $2^W$ of them, and the state needs $W$ bits.

That the differing position must be the oldest one is the load-bearing detail. Choose the newest instead and the continuation pushes both differing bits out of the window together, the two windows become identical, and no contradiction follows. It took a wrong first version of this proof to notice.

Performed, not quoted #

At $W = 10$ there are 1,024 windows, which is few enough to run the pigeonhole rather than invoke it.

A candidate algorithm keeping the last eight bits is offered all 1,024, and the first collision is reported with everything the argument needs:

The eight-bit state cannot distinguish them — both end in the same eight bits — and after nine zeros the correct answers are 0 and 1. The candidate reports one number and is wrong about one of the two.

The second half of the check is what makes the first mean anything. The same exhaustive search is run against a candidate holding the full ten bits, and it is required to find no collision — 1,024 windows, 1,024 states. A floor that fired on everything, including the structure that meets it, would be a bug in the search rather than a theorem about the problem.

Why this floor is tidier than the last one #

The distinct-counting floor needed care. It counts only the half-sized subsets of a universe, because for two arbitrary sets of different sizes the obvious continuation leaves the true answers equal and the argument fails. The bound that comes out is $\log_2 \binom{u}{u/2}$, which is $u - \tfrac{1}{2}\log_2 u - O(1)$ — close to $u$ and not equal to it.

Here there is no such restriction. Every pair of distinct windows separates, the count of distinguishable inputs is exactly $2^W$, and the bound is exactly $W$. It is one of the few floors on this site that is tight, achieved, and stated without an asymptotic.

The reason is the shape of the question. A window is the state — the last $W$ bits are precisely what determines every future answer — so the input space and the state space are the same object. Where the answer depends on less than the whole input, as it does for distinct counting, the counting argument has to work harder and gets less.

What the approximate case gets, and what is quoted #

The floor above is about an exact answer. Allow a relative error of $\varepsilon$ and the state collapses: 1,656 bits at $W = 8{,}000$ rather than 8,000, a saving of 4.8 times, and the ratio improves without limit as the window lengthens.

There is a matching lower bound for the approximate problem — $\Omega\!\left(\frac{1}{\varepsilon}\log^2(\varepsilon W)\right)$ bits — and this site is not going to pretend to have demonstrated it. It is a communication-complexity argument, it is not one a small exhaustive search performs, and quoting it while implying otherwise is the failure this site exists to avoid. It is stated here as somebody else’s theorem, with its shape named, and that is all.

What can be measured is whether the structure that exists sits on that shape. The exponential histogram’s bucket count should be about $k \log_2(N/k)$, where $k = \lceil 1/\varepsilon\rceil$ and $N$ is the number of ones in the window — $k$ buckets of each size, sizes doubling from 1 to about $N/k$.

And across tolerances at a fixed window:

The formula is right to within 15% everywhere and to within 5% over most of the range, and the excess has a name: the invariant permits $k+1$ buckets of each size rather than $k$, so the true coefficient is a little above $k$. The closed form is not a bound being respected, it is a prediction being met, which is a different and stronger kind of agreement than most of the comparisons in this field.

The state is sublinear in the tolerance, and that is not obvious #

That last observation deserves its own paragraph because it contradicts the natural reading of the bound.

Going from $\varepsilon = 0.2$ to $\varepsilon = 0.02$ is a factor of ten in $1/\varepsilon$. The state goes from 615 bits to 2,835 — a factor of 4.6, not ten.

The formula explains it exactly. The bucket count is $k\log_2(N/k)$: raising $k$ raises the first factor and lowers the second, because with more buckets of each size the sizes need not grow as far to cover the window. At $k = 5$ the largest bucket is around 64 and there are seven distinct sizes; at $k = 50$ the largest is around 8 and there are three.

So accuracy in this structure is cheaper than linear, and it gets cheaper the more of it is bought — the reverse of every other trade in this field, where error falls as the square root of the state and each halving costs four times as much. The reason is that the guarantee here is deterministic rather than statistical, exactly as it was for the quantile summary, and a deterministic structure is not paying for a variance.

The distinction matters enough to state once more in the language of the model. A floor of $W$ bits is a claim about the worst stream, an exponential histogram’s measured 1,394 bits is a claim about one stream, and the number that would let the two be compared directly — the entropy of the window distribution a particular deployment actually produces — is almost never known and almost never estimated. Sizing a structure from a worst-case floor is therefore conservative by an unmeasured factor, and the only defensible response is to say so rather than to pretend the factor is one.

What the floor does not forbid #

A floor is a statement about a precisely specified problem, and every clause of the specification is load-bearing. Four things this one permits, each of which somebody has built.

Approximation. The whole of the previous section. Allowing a relative error of $\varepsilon$ takes the state from $W$ to something logarithmic, and the argument above says nothing about it, because two windows whose counts differ by one may quite properly share a state in a structure allowed to be wrong by more than one.

Amortisation over queries. The floor assumes an answer after every arrival. A structure asked only occasionally may delay work, though it may not delay remembering — the information has to be kept whether or not the answer is computed, so this buys time and not space.

A different question. The count of ones is the easiest windowed statistic there is. The floor for the windowed sum of integers, or the windowed distinct count, is at least this one and generally worse, because the set of distinguishable inputs is larger.

A stream that is not adversarial. The pigeonhole is over all $2^W$ windows. A stream that only ever produces windows from some small family needs only enough states for that family — which is why a run-length representation of a mostly-zero window is small, and is not a counterexample to anything.

The fourth is the one worth care. Every state bound in this field is a worst-case statement, and the structures are then run on real streams that are nothing like worst case. The exponential histogram’s own state on the bursty stream measured here is a good deal smaller than the bound would allow at the same $N$, for exactly this reason.

The crossing is not a constant either, and what moves it is the stream rather than the structure. A summary’s size is set by the number of ones it has to keep buckets for, so a denser stream pushes the summary up while the exact structure’s $W$ bits do not move at all.

A structure chosen from the first plate and deployed on this stream is the larger of the two over twice the range it was meant to be smaller on.

The other windowed questions #

The count of ones has the tidiest floor and the other questions are worth naming, because the distances between them are large and are not obvious.

A windowed sum of $b$-bit integers. Each of the $2^{bW}$ possible windows separates by the same argument, so the floor is $bW$ bits: exact windowed sums cost the window, whatever is in it. The approximate version is the same exponential histogram with bucket sums instead of counts, at the same accuracy and the same shape of state.

A windowed distinct count. Harder than either. The structure has to know not merely how many distinct keys are in the window but when each was last seen, because a key leaving the window changes the answer only if it has not reappeared. The published constructions keep a timestamp per register, and the state is the cardinality estimator’s state multiplied by a logarithm — which is worse than the ratio between the exact and approximate cases here.

A windowed heavy hitter. Worse again, and this is where the model stops being a variation and becomes a subject. It is named here and not built, on the same principle the previous phase used for the approximate distinct floor: the constructions are real, they are not implemented here, and a comparison against published figures would be an assertion wearing a measurement’s clothes.

The answer is ten bits and the state is a thousand #

A quantity worth putting beside the floor, because the ratio between them is the whole reason this problem is interesting.

The thing being reported is a count of ones in a window of $W$ arrivals. It is an integer between 0 and $W$, so it fits in $\lceil \log_2 (W+1) \rceil$ bits — ten of them at $W = 1{,}000$, thirteen at $W = 8{,}000$. The state proved necessary above is $W$ bits. The structure is a hundred times the size of the thing it exists to report at a window of a thousand, and six hundred times at a window of eight thousand.

Nothing is being stored inefficiently. The answer is small and the state is large because the state is not holding the answer; it is holding everything needed to produce the next answer, and the next one after that. A window count changes by at most one per arrival, and knowing the current count says nothing about which way it will move — that depends on the bit about to expire, which is $W$ arrivals old, and the identity of that bit is not recoverable from the count.

So the floor is really a statement about the derivative rather than the value. What the algorithm must retain is the schedule of future decrements, and a schedule of $W$ future one-bit events is $W$ bits however it is written down. Seen that way the theorem stops being surprising: the sliding boundary is a promise to remember, in order, everything that will need to be forgotten, and the count that outlives its arrivals is the structure that makes the schedule explicit instead of implicit.

It also explains where the approximate structure gets its savings, which is not where a reader would first look. The exponential histogram does not store a coarser count; the count it reports is an integer of the same ten bits. It stores a coarser schedule — a bucket says “these thirty-two arrivals expire around now” instead of naming each one — and the tolerance is the resolution of the timetable rather than the resolution of the answer. Everything in the plots above is bought there.

What the floor becomes when the stream is not uniform #

The fourth permission above — a stream that is not adversarial — is stated in a sentence and deserves more, because it is the one a practitioner will actually meet and because the sharpened version of the floor is exact.

The pigeonhole counts the windows that can occur. If only $m$ distinct windows ever appear, only $m$ states are needed and the floor is $\log_2 m$, which can be far below $W$. A stream of a million arrivals that is zero except for a hundred ones produces windows from a family vastly smaller than $2^W$, and a run-length representation of the window is a perfectly good encoding of the family.

The exact form is the entropy. Let the window contents be drawn from some distribution; then any correct algorithm needs, on average, at least $H$ bits of state, where $H$ is the entropy of that distribution — the same counting argument run against a code rather than against a state map. The floor proved above is that statement with the distribution set to uniform, where $H = W$ exactly, and the reason a worst-case bound is stated over the uniform case is that a uniform window is precisely the one no encoding compresses.

Which makes this floor the same object the compression field measures, arriving from the other side. The bits a coder emits is a statement about how few bits a source can be written in; this is a statement about how few bits a source can be remembered in, and they are the same number because remembering and writing down are the same operation performed against different deadlines.

Two consequences follow and both are worth having.

A run-length window structure is not a counterexample to anything above, and it is also not a free lunch: it is small on the streams whose window entropy is small and it is larger than $W$ bits on a stream of coin flips, because run lengths of one cost more than the bit they encode. That is the same accounting an index that charges by the block does, and it fails in the same place.

And the measured state of a structure on a real stream is not evidence about a bound. The exponential histogram’s own size on the bursty stream here is comfortably under what the worst case permits, and reading that as slack in the theorem would be an error — the theorem is about the family of streams, and one stream is not the family. A bound is worst case, a measurement is one case, and the only honest comparison between them is one that says which is which.

The three floors, side by side #

It is worth putting them together, because the differences between them are the interesting part.

Three of those four rows are computed and checked here. The fourth is a citation, it is marked as one, and the essay does not lean on it — every claim made above about the approximate case is a measurement of a structure, not a claim about what no structure could do.

That distinction is the one this site keeps returning to and it costs nothing to maintain. A measurement can refute a claim and can pin a constant; it cannot establish a limit, and a floor that has been performed on 1,024 inputs is a different object from a floor that has been read.