The source coding theorem gives a floor of bits for a block of symbols, on the assumption that the distribution of the source is known in advance. In practice you learn the distribution from the same data you compress: you count symbol frequencies, build a Huffman tree or a model, and write the model's description alongside the encoded message. On a source that changes over time, yesterday's model is wrong today, and a model fitted to the whole message may describe the message better than it describes the next one.
The chapter's tools point in several directions: send the model's description, fix the model in advance and amortise its cost over many messages, or let the decoder learn the model while it reads. No rule in the chapter says what a single reported compressed length promises when the model is learned from the message. Take a position: when the source is unknown, what should a compressed length promise, and how should the cost of the model be counted?
In your answer: say what the encoder builds its code from and what the decoder is told; say how the model's description enters the bit count; say what the reported number is a promise about, such as this message, this source, or the next block; say what happens when the source changes; and name one way a reported compression ratio can mislead even when the encoder and the decoder are both correct.
Rubric. Tick each criterion your answer meets, then save the self-assessment. The platform does not grade it.
Worked solution
There is no single correct answer, so this is a model of the shape a complete answer takes, not a key.
A complete answer begins by fixing the object being measured. One target is the length of one encoded message, model included, for a decoder that receives the model description. A second target is the average length of a procedure over many messages from a stated source class, model-learning included. A third target is the length of the next block after the model has been learned on earlier blocks. These are different quantities. A level-3 answer says which one it reports and refuses to slide between them.
The accounting then separates model from data. If the encoder sends a Huffman tree, the tree's description costs bits, and those bits belong in the total. If the encoder and decoder agree on a fixed model in advance, the model's cost is paid once and can be amortised over many messages, but the reported length must say so. If the model is adaptive, the decoder updates it as it reads, and no model description is sent; the price appears as a longer code on the early part of the message. In every case the total is the sum of the parts, and a ratio that omits one part is not a compression result for the whole message.
The promise comes next. A length for one message is a fact about that message, not an estimate of the source entropy. An average over a test set is an estimate for the procedure on that set, and its uncertainty shrinks with the number of messages, not with the length of one message. A claim about the next block needs a model of how the source changes, and that model is itself an assumption that can fail. Section 16.5 says the theorem is a promise about long blocks from a known distribution; the honest report says how far the experiment is from that ideal.
Non-stationarity belongs in the answer. A source whose probabilities drift makes the empirical frequencies of the whole message a weighted average of several regimes. A single code built on that average can be worse than an adaptive code on every regime, even though its average length on the training message looks good. A change-point detector, a sliding window or a mixture of models is a response, and each adds its own cost and delay. A level-3 answer names the regime it assumes and says what evidence would show that the assumption is false.
The named failure should be concrete. A model fitted to the message and then scored on the same message can overfit: the fitted frequencies assign high probability to what happened and look efficient, while a new message from the same source costs more. A ratio that compares a compressed size to the raw size without counting the model can exceed the entropy floor and appear to beat it. A test set drawn from a different period than the deployment period makes the number describe the wrong source. A level-3 answer chooses one of these, says how it would show up in the numbers, and says what check would catch it.
Rubric: - 0 — Restatement. The answer repeats that entropy is the floor and that a code can approach it, but names no accounting, no target and no model cost. No distinction between the message and the source appears. - 1 — One number, one confusion. The answer reports a compression ratio or a bits-per-symbol figure without counting the model description, or treats the empirical entropy of the message as the true entropy of the source, or compares a code to a floor computed from the same fitted model and calls the result optimal. It does not say what the number is a promise about. - 2 — Model and data separated. The answer counts the model's description in the total, or uses an adaptive code and explains that the decoder learns as it reads. It states whether the promise is about this message, this source class or the next block, and it says what happens when the source changes. It names at least one way the report can mislead, such as overfitting the model to the scored message or quoting a ratio that omits the model. - 3 — Accounting defended. The answer does everything at level 2 and also argues why its accounting matches the target it claims. It distinguishes the length of one message from the average length of a procedure, gives the finite-sample cost of learning the model, such as the description bits, the early-message penalty or the delay, and explains how the report changes as the message or the sample grows. It names a concrete failure that the accounting cannot detect, states the assumption about the source that the whole report rests on, and says what evidence would make it abandon that assumption.