The sampler that cannot alias

A block window has already been shown, here, to be a sampler.

Its boundary fires when a fixed number of arrivals have gone into the block, so the sequence of boundary times is the arrival times at positions $s, 2s, 3s, \ldots$ — a sampler whose sampling instants are chosen by the signal being sampled. Against a stream whose burst repeats every sixty-four arrivals, a block of five hundred and twelve holds exactly eight cycles and reports every block as covering the same duration to the tick, on arrivals whose index of dispersion is 0.57. The essay that measured it is the boundary that hides the burst, and it closed by naming the obvious next case and not taking it.

The next case is this one. A quantile summary compresses every $\lfloor 1/2\varepsilon \rfloor$ updates, which is an arrival-counted schedule by any reading, so a periodic feature of the values ought to be aliasable against it in exactly the same way.

It is not, and the interesting part is why not.

What a sampler needs in order to alias #

Aliasing is not a property of a schedule. It is a property of a schedule plus a discard.

A block boundary retires a block. The arrivals in it leave the structure, and which arrivals those are is decided entirely by where the boundary fell. When the boundary is commensurate with a period in the stream, the same phase of that period is retired every time, and the structure’s account of the stream is an account of one phase repeated — which is what a flat spread on a visibly uneven stream means.

A compression retires nothing. Merging a tuple into its neighbour adds the tuple’s $g$ to the neighbour’s, so

$$\sum_i g_i \;=\; n$$

before and after every compression, at every instant of the run. What a compression discards is resolution — where inside a gap an arrival sat — and never an arrival.

A sampler that misses nothing has nothing to alias against. That is the argument, it is one line, and everything below is corroboration rather than evidence.

The corroboration, and why it needs a shuffle #

Arguments of that form are how mistakes get made, so the sweep is worth running.

Three periodic value processes were built for it, because every value distribution this site had was drawn independently per arrival and therefore carried no order at all — a stream a sampler cannot alias against for the trivial reason that there is nothing periodic in it. The three are a ramp sweeping the whole value range every $p$ arrivals; a quiet stream with a spike into the top of the range every $p$; and a sinusoid of period $p$, which is the same period with no discontinuity in it.

Each is run against a summary compressing every fifty updates, at cycle lengths from twenty-five to five hundred, and — this is the part that makes it a measurement — each is run beside a random permutation of its own values. The shuffle has the identical multiset and no order, so anything the ordered stream does that the shuffle does not is order, and anything they both do is the distribution.

The statistic is the mean ordered-against-shuffled departure at the commensurate cycle lengths divided by the mean at the rest. A structure that aliased would lift it. It reads 1.035 on the ramp, 0.931 on the spike train and 0.843 on the sinusoid — scattered around one, on both sides of it, which is what no effect looks like.

The processes had to be built, and that is a finding of its own #

Something turned up while assembling the sweep that is worth more than a footnote.

Every value distribution this site has ever drawn a quantile summary against — uniform, log-normal, Pareto, bimodal — is generated by drawing each value independently. The sequence carries no information beyond its histogram. Reordered any way at all, every quantile of it is unchanged, because a quantile is a statement about the multiset.

So this collection has spent a long run of essays asking whether various quantile structures behave well, on inputs that could not possibly have exercised the one property under test here. That is not a defect in those measurements — they were about tolerances and tail behaviour, and for those questions order-free inputs are the right control — but it means the aliasing question had never been askable, and the reason it had never been asked is that nothing in the input could have answered it.

The histogram that cannot see the order makes the counterpart observation on the counter side: a whole-shard histogram has no order in it, so a prediction computed from one is blind to a stream whose favourites move, and the failure is real and measurable. Both essays are about the same gap between what a statistic contains and what a structure experiences, approached from opposite ends.

A negative result is a statement about the instrument until it is not #

Here is the failure this essay was most exposed to. A sweep that reports “no effect” reports the same thing whether there is no effect or whether the sweep cannot see effects, and those are not the same finding at all.

So the statistic is pointed at a structure where the answer is known. The block window measured in the boundary that hides the burst aliases, and it aliases in the direction that a commensurate block reports a flatter stream, so the statistic runs the other way there. Commensurate blocks spread by exactly 1.00 and incommensurate ones by 1.48. The statistic fires.

That is the hero plate above, and it is the one that makes the near-one readings mean something. The instrument that returns 1.03 for a compression returns 1.48 for a boundary on the same kind of question.

Ruling out the other explanation #

There is a second candidate reason a compression might fail to alias, and it has nothing to do with conservation: a compression scans the whole list. Perhaps what protects the structure is that every tuple is reconsidered at every pass, so no tuple’s fate depends on which pass it happened to be near.

That is a testable alternative, and the way to test it is to build the structure that does not have the property. A compression reviewing only the tuples inserted since the last one is the shortcut a first implementation reaches for — it is where the merges are, and rescanning the whole array to find them looks wasteful. It is a genuine sampler in the sense the analogy meant: a tuple outside the batch is never looked at, and a tuple that could not merge while it was fresh is never offered the chance again.

It costs almost exactly twice the tuples — 152 against 77 — so it is a real shortcut with a real price rather than a straw one. And it does not alias either: 1.03, 0.93 and 0.84 on the same three processes, the same as the full compression to within the noise.

So it is the conservation and not the scan. That is worth having, because the conservation is a property of the merge rule and the scan is a property of one implementation, and the two would have given different advice to anyone writing a variant.

One thing the sweep did show, and it is not aliasing #

The sweep was not entirely quiet, and the noise in it has a shape worth naming so that nobody rediscovers it as a finding.

An early version used a ramp with only $p$ distinct values — a clean sawtooth, no jitter — and the ordered stream kept far fewer tuples than its shuffle: 52 against 90, 58 against 81, 58 against 91. That looked like a large order effect and it is not one. It is a duplicate effect: with only a hundred distinct values in twenty thousand arrivals, most inserts land on an existing value, and the insert rule places a duplicate at the end of its tie run, where its $\Delta$ is computed differently from a value landing in open space. Adding jitter so that every value is distinct removes the gap entirely — 74 against 76, 76 against 76, 73 against 72 — while leaving the periodic structure exactly as it was.

The distinction matters because the two are easy to confuse and only one is about the schedule. A duplicate-heavy stream really does produce a leaner summary, at any compression period, on ordered and shuffled inputs alike. It is a fact about ties and not about sampling, and a sweep that had not included the jittered control would have reported it as an alias.

That is the second thing a shuffle earns beyond its stated job. It holds the multiset fixed, which is what makes it a control for order — and holding the multiset fixed also means the tie structure is identical on both sides, so anything caused by ties cancels rather than showing up as a difference.

What this settles about the analogy #

The analogy that essay drew was good and it was not close enough. Two structures both do periodic housekeeping on an update count; only one of them is a sampler; and the thing that separates them is not the schedule but what the housekeeping does.

Set out as a question a reader can carry to a third structure: does the housekeeping remove information the structure would otherwise still have, and is what it removes chosen by where the boundary fell?

• A block window: yes and yes. The retired block’s arrivals are gone, and which ones they were is the boundary’s choice. It aliases.
• A quantile compression: no. $\sum g = n$; the resolution lost is the resolution the invariant already permitted losing, and it would have been lost at any other schedule too.
• An exponential histogram’s merge, which a register that became a list is about: no, on the same grounds — buckets combine and their counts add.
• A Space-Saving eviction: yes. A key leaves the table and never comes back, and which key it was depends on what the table held at that instant. Nothing here measures whether an eviction schedule can be aliased against, and the machinery to ask is now built.

The last of those is the one to be careful with, because Space-Saving’s schedule is not periodic. It evicts when a key arrives that is not in the table, which is a data-dependent instant rather than a counted one — so there is no fixed period for a stream’s period to be commensurate with. Whether that makes it immune or merely makes the question harder to pose is open. A promise about the rank and the summary that has to forget mark out the two families this question has to be asked separately of.

Where the resolution does go #

It is worth being clear that a compression does lose something, and saying what, so the negative above is not read as a claim that compressing is free.

What it loses is the ability to say where inside a merged band an arrival sat. That is exactly the quantity $\Delta$ is a bound on, it is what the promise is a promise about, and it is why an error measured against the answer has to distinguish a rank error from a value error at all. A summary that has compressed heavily around the median still answers the median’s rank to within its tolerance and no longer answers which of forty stored values was the fifty-first.

That loss is not schedule-dependent in the way an alias would need. It is capped by the invariant at $2\varepsilon n$ wherever the compressions fell, and the measurements in the period that is not a promise show the realised loss flat across a thousand-fold sweep of the period.

Why this is worth a whole essay #

A run of essays establishing that nothing happens should say why that was worth doing, and there are three reasons.

The first is that the mechanism was named and priced in a published plan. An open question with a plausible mechanism attached is a liability: somebody eventually builds a defence against it, or worse, explains a real result by it. Closing it costs one sweep and one invariant.

The second is that the reason it does not happen turns out to be a useful classifier. “Does the housekeeping discard, and is the discard chosen by the boundary?” separates the structures this site holds into two groups cleanly, and it is a question a reader can ask of a structure they meet somewhere else. That is worth more than the answer for this particular pair.

The third is the calibration habit. This site’s standing position is that an assertion that has never rejected anything proves nothing, and the same is true of a statistic that has never fired. Pointing the commensurability measure at the block window before believing its silence about the compression is the same discipline applied to a measurement rather than to a check, and it is the part of this essay most worth copying.

What the sweep could have detected #

The essay is careful to say that the calibration is one known case rather than a characterisation of the instrument’s sensitivity. The three null readings characterise it, and it is worth doing, because a negative result without a detection threshold is a claim of unknown strength.

The three processes return 1.035, 0.931 and 0.843. They are three independent estimates of the same nothing, so their spread is the statistic’s own noise: a mean of 0.936 and a standard deviation of 0.096.

That gives the threshold directly. An effect has to lift the statistic about three standard deviations above the null mean to be distinguishable, which is 1.22. And the block window, at 1.48, sits 5.7 standard deviations out — comfortably clear, which is why the calibration works.

So the negative result has a size. Any aliasing in these compression schedules is under about a fifth of the departure scale, because a fifth is roughly where the instrument stops being able to tell. An effect at 1.5 would have been unmissable; one at 1.1 would have been invisible, and nothing here rules it out.

That is a materially better statement than it does not alias, and it is the statement the argument actually supports. The one-line proof — $\sum g = n$, nothing is retired, there is nothing to alias against — is what rules out an effect of any size; the sweep confirms it down to about twenty per cent and no further. Two claims of different strengths, and separating them is what stops the corroboration being read as the proof.

The null mean is also worth a sentence, because 0.936 is not 1.000. Three readings with a standard deviation of 0.096 have a standard error of 0.055, so the mean sits about a standard error below one — consistent with one, and not evidence of an anti-alias. A reader tempted to explain the shortfall has three numbers to explain it from, which is not enough.

The obvious caution is the sample size. Three processes is three, the standard deviation of three numbers is a poor estimate of anything, and the threshold above should be read as an order of magnitude rather than a bound. What makes it worth computing anyway is that the alternative is no threshold at all: a sweep reporting “around one” invites a reader to imagine it would have caught anything.

Which is the discipline one pass, k slots, and two randomness budgets applies to a biased sampler — a test whose noise floor is above the effect it is looking for passes on the broken version and proves nothing about the correct one, and the fix is to measure both the floor and the effect before choosing a tolerance. Here the effect was measured first, on the boundary that hides the burst’s structure, and the floor comes free from the nulls that were run anyway.

The limit of the negative #

Three things this does not establish, stated because a negative result attracts more weight than it can carry.

It does not establish that no quantile structure can alias. It establishes that these two cannot, and gives the property — mass conservation — that a third would have to lack.

It does not establish that the sweep would find every alias. It establishes that the sweep finds the one alias available to test it on, at 1.48 against a 1.03 null, which is a calibration on a single known case rather than a characterisation of the instrument’s sensitivity.

And it does not establish anything about a windowed quantile summary, which is the structure that would have both properties at once — a compression that conserves and an expiry that does not. Nothing here builds one. The prediction the argument here makes is that such a structure aliases through its expiry and not through its compression, and that the two can be told apart by watching whether $\sum g$ tracks the window occupancy or falls short of it. That is a measurement and it is not this one.