The model is the compressor

Every other floor on this site is a number. $\log_2(4096!) = 43{,}250$ comparisons. $n\log_2(1/\varepsilon) = 6.64$ bits per key at a 1% false-positive rate. Compute it, quote it, measure the distance to it.

The entropy floor is not a number until somebody makes a choice, and the choice can move it by a factor of four on a stream nobody has touched.

What conditioning means #

The zeroth-order entropy asks: given nothing, how surprising is the next symbol? It is computed from the symbol frequencies and nothing else.

The first-order entropy asks: given the previous symbol, how surprising is the next one? Group the stream by what preceded each symbol, compute an entropy inside each group, and average the groups by how often each occurs.

$$H_k = \sum_{c} P(c) \cdot H(\text{next} \mid c)$$

over all contexts $c$ of $k$ preceding symbols. That is all it is: a weighted average of the entropies of the sub-streams that follow each context.

Conditioning cannot increase entropy — knowing something extra cannot make the next symbol more surprising on average — so $H_0 \ge H_1 \ge H_2 \ge \cdots$ always. The gate asserts it on every source it draws, because a violation would mean the estimator is wrong rather than that the world is interesting.

Three streams, and what each of them hides #

The three sources in the hero figure were constructed to make three different points, and each is generated from a stated rule so the measured floor can be checked against the rule rather than only against itself.

The uniform source draws eight symbols with equal probability, independently. Its true entropy is exactly 3 bits per symbol at every order, because there is nothing to condition on. Measured: 3.000, 2.999, 2.990, 2.918, 2.269.

Those numbers fall, and the fall is entirely fictitious. It is the estimator’s bias and the next section is about it.

The Markov source steps to the next symbol 85% of the time and jumps at random otherwise. Every symbol appears equally often, so $H_0$ is 3.000 — a coder that looks at symbols one at a time sees a uniform stream and can do nothing whatever with it. $H_1$ is 0.936.

A drop of 2.064 bits per symbol, from one symbol of context. The stream did not change. It was always almost perfectly predictable, and the zeroth-order model was blind to all of it.

The text source is words from a fixed vocabulary. It falls steadily: 3.886, 2.243, 1.186, 0.991, 0.909. Text has structure at every scale — letter frequencies, letter pairs, word boundaries, whole words — so every additional character of context finds some more of it.

One context, opened up #

It is worth seeing what a context actually holds, because the arithmetic above is a summary of eight small tables.

Take every position in the Markov stream where the preceding symbol was a, and count what followed:

The entropy of that distribution is 0.973 bits. Seven other contexts look the same with the labels rotated, and averaging the eight gives $H_1 = 0.936$.

Now look at the same stream ignoring context: a occurs an eighth of the time, b an eighth, and so on — 3.000 bits, and completely uninformative. Both tables are correct descriptions of the same 32,768 symbols. The second is a marginal of the first, and marginalising threw away everything worth knowing.

Where the estimate stops being an estimate #

The uniform source’s fall from 3.000 to 2.269 is not a discovery about the data. It is a defect of measuring an entropy from a sample, and it is worth understanding because it is the failure mode of every model-order argument.

At order 4 over eight symbols there are $8^4 = 4{,}096$ possible contexts and 32,768 observations, so each context holds about eight. An entropy estimated from eight observations of an eight-symbol alphabet is always below the truth: with eight draws some symbols will not have appeared, the empirical distribution looks concentrated, and its entropy comes out low.

Push it further and it goes to zero. A context that occurs exactly once has an empirical entropy of exactly zero — one observation, one outcome, no uncertainty — and has learned nothing at all.

So $H_k$ falls toward zero for every source, given enough $k$, and past some point the fall is the estimator running out of data rather than the model finding structure. The figure reports where that is: the deepest order of the uniform source has 4,092 contexts of which 10 occur once, and the Markov source at order 4 has 1,120 contexts of which 509 occur once — nearly half.

That is why the gate’s check on the uniform source is comparative rather than absolute. A first version asserted that a structureless source loses less than 0.35 bits to conditioning, and it failed at 0.73. The assertion was the thing that was wrong: 0.73 bits is exactly what an unbiased estimator does not do and a maximum-likelihood one always does. What is asserted now is that the bias is a fraction of the drop a real order-1 structure produces — 0.73 against 2.06 — which is the claim that distinguishes signal from artefact instead of pretending the artefact is not there.

This has a name outside this subject. Deepening the model until the estimate collapses is overfitting, and a compressor that used a model chosen this way would produce a beautiful floor and no compression at all, because the decoder needs the model and the model is now as large as the data.

Which is why the model has to be transmitted, or learned #

A floor computed from a stream’s own statistics assumes the decoder knows those statistics. It does not. Something has to give it them, and there are exactly two options.

Send the model. Measure the stream, transmit a header describing the frequencies, then code at the floor. The header is a fixed cost that amortises.

Learn the model. Start both encoder and decoder from the same ignorant model, and have each update it identically after every symbol. No header at all, and the early symbols are coded under a model that knows nothing.

At 64 symbols the static coder spends 8.984 bits per symbol against the adaptive coder’s 4.344 — the header is larger than the message. At 65,536 the static coder spends 3.893 and the adaptive 3.890.

The adaptive coder wins at every length measured, and it is worth being clear that this is a result about these particular coders rather than a law. The header here is a plain 16 bits per symbol frequency, which is generous; a header that coded its frequencies well would be smaller and would eventually win. What the figure establishes is the shape — a fixed cost against a decaying one — and where the crossing falls depends on how well the header is packed.

That shape is the reason essentially every general-purpose compressor written since about 1990 is adaptive. The header can be made small, and a coder with no header at all can start emitting bits before it has seen the end of the input, which matters more: it can compress a stream.

What the learning actually costs #

The adaptive coder’s excess over the floor is a measurable quantity and it has a known form.

Starting from a uniform model over $\sigma$ symbols and updating by one count per observation, the total excess over the true entropy is about $\frac{\sigma - 1}{2}\log_2 n$ bits for a stream of $n$ symbols — a cost that grows only logarithmically in the stream length, which is why it amortises so fast.

Measured on the text source, with 21 symbols: the excess over $H_0$ is 0.404 bits per symbol at $n = 64$, 0.183 at 256, 0.065 at 1,024, 0.021 at 4,096, 0.006 at 16,384 and 0.002 at 65,536. Each quadrupling of the length roughly thirds the excess, which is what a $\log n$ total divided by $n$ does.

Two sources where the curve does something else #

The periodic source is the extreme case of the essay’s claim and it makes the point without any interpretation. Its zeroth-order entropy is 2.705 bits per symbol and its second-order entropy is 0.0002. A coder using the first model spends 44,000 bits on 16,384 symbols; a coder using the second spends about four. Same stream.

The skewed source is the opposite case, and it is worth having because it is the one where conditioning does nothing: 0.757, 0.756, 0.752, 0.744, 0.731. All of its structure is in the marginal distribution — one symbol at 0.9 and seven sharing the rest, drawn independently — and there is nothing whatever for a context model to find. The small fall across those five numbers is the estimator’s bias, exactly as with the uniform source.

Put beside each other, the three cases say that the right model order is a property of the source and cannot be guessed from the data’s size, its alphabet, or how compressible it looks. A stream with $H_0 = 3$ can be worth three bits per symbol or two ten-thousandths, and telling the two apart requires actually conditioning and looking.

Two floors that move, and they do not move for the same reason #

This site has one other floor that changes, and the difference between the two is worth pinning down because they look alike from a distance.

The floor when the values repeat shows that $\log_2(n!)$ is the wrong floor for sorting a multiset, and that the right one — 738.7 bits rather than 1,684 for 256 values from eight distinct — is less than half of it. That floor moved.

It moved because the question was restated. Sorting a multiset genuinely has fewer distinct answers than sorting distinct keys, so the number of outcomes an algorithm must distinguish is smaller and the decision-tree bound follows it down. Once the question is stated precisely there is one correct floor, and quoting the other one was an error.

The entropy floor is not like that. There is no error in quoting $H_0$ rather than $H_3$, and no restatement of the question makes one of them the right one. Both describe the same data, both are achievable, and choosing between them is choosing what the coder is allowed to look at — which is a decision about the algorithm, on the bound side of the line where algorithms are not supposed to appear.

A floor that depends on the algorithm’s design is a strange object, and it is the reason this field behaves differently from the rest of the site. Everywhere else, the floor is fixed and the work is closing the gap. Here the gap was closed in the second essay of the field — arithmetic coding sits a hundredth of a bit above whatever floor it is given — and all the remaining work is in moving the floor.

Two more readings of the floor say what the order sweep is a statement about. Drop the control and the two real sources can be read against each other; shorten the stream and the estimator’s own bias starts eating into the drop.

And the control belongs back on the plate once, because the reason to keep drawing it is that it is the only line on any of these that is supposed not to move.

Where this leads, and what is not built here #

The obvious next move is to use several orders at once: predict from a long context where there is evidence for it, fall back to a shorter one where there is not, and blend the two by how much evidence each has.

That is PPM — prediction by partial matching — and its descendants are context mixing and the neural predictors that top the compression benchmarks. They are among the best-compressing programs that exist, and they are all built on exactly the observation this essay measures: the floor is set by the model, so build a better model.

None of it is implemented here, and the reason is the site’s own rule rather than a lack of interest. A PPM implementation has an escape mechanism whose several published variants differ in ways that change every number it produces, and quoting a result from one of them without measuring the alternatives would be asserting rather than measuring. What this file has instead is the two ends of the range — a static context model whose floor can be computed exactly, and an adaptive coder whose learning cost can be measured — and the honest statement that the space between them is where the working compressors live.

The two limits are one limit #

The essay names two reasons a model cannot simply be made deeper — the estimate stops meaning anything, and the model has to be paid for — and treats them as separate. They are governed by the same ratio, which means there is one number to check rather than two.

An order-$k$ model over $\sigma$ symbols has $\sigma^{k}$ possible contexts. Write $C$ for how many of them actually occur, which is at most $\min(n, \sigma^k)$.

The estimator’s bias is what happens when the observations per context, $n/C$, gets small. At eight observations of an eight-symbol alphabet the empirical entropy is well below the truth; at one observation it is exactly zero.

The learning cost is about $\frac{\sigma-1}{2}\log_2(n/C)$ bits per context, so the total divided by $n$ is

$$\frac{C}{n}\cdot\frac{\sigma-1}{2}\log_2\frac{n}{C}$$

which is small when $C \ll n$ and becomes the whole cost when $C$ approaches $n$.

Both expressions are functions of $n/C$, and both go wrong at the same place: when the contexts outnumber the observations that would fill them. The estimator’s collapse and the coder’s overhead are two readings of one condition, and the condition is $n \gg \sigma^k$.

That gives a single sizing rule with a number in it. The text source here has $\sigma = 21$ and $n = 32{,}768$, so $\sigma^k \ll n$ holds comfortably at $k = 2$ (441 contexts), marginally at $k = 3$ (9,261), and not at all at $k = 4$ (194,481). Reading the measured floors against that — 1.186 at order 2, 0.991 at order 3, 0.909 at order 4 — says the first is trustworthy, the second is at the edge, and the third is mostly the estimator running out of data. Which is precisely what the singleton-context counts in the essay’s own diagnosis say, arrived at from the other direction.

So the honest maximum order is $\log_\sigma n$ minus a margin, and it depends on the alphabet as much as on the stream length. Over four symbols and thirty thousand observations that is order six or seven; over twenty-one symbols it is order two or three; over a byte alphabet it is order one. That last figure is the reason general-purpose compressors do not simply raise the order and instead go to variable-length contexts, blending and escape mechanisms — the fixed-order table hits this wall almost immediately on real data, and everything interesting in the field is a way around it.

The result this puts on the table #

Three statements, and the third is the one worth carrying.

A quoted entropy without a stated model order is not a quantity. The same stream is 3.886 bits per symbol and 0.909, and neither number is more correct than the other.

A compressor that beats an entropy floor has used a better model, and has not beaten Shannon. Every result in the two essays that follow is of that form: the dictionary that builds itself uses a window of recent text as its model, and the transform that emits nothing rearranges the stream so that a weak model becomes a good one.

And the model cannot simply be made deeper. The floor keeps falling and the estimate stops meaning anything, the model has to be transmitted or learned, and both costs grow with the model’s size. Every real compressor is a position on that trade, and the interesting ones are the ones that found a model whose cost does not grow the way a context table’s does.

That is what makes this a field rather than a technique. The floor moves when the question does established that a lower bound belongs to a question rather than to an algorithm; this field’s floors belong to a model, which is a thing the algorithm designer chooses. The bound and the algorithm are no longer separate objects, and choosing well is the entire subject.