In an adaptive arithmetic coder, how does the decoder's probability model stay identical to the encoder's?

## The coder is not where the compression comes from An interval coder is a mechanical device: give it a probability, it spends `log2(1/p)` bits. All the compression comes from the **model** — the component that says how likely each symbol is next. An adaptive model is one that starts nearly ignorant and sharpens as it reads, so an archival text stream ends up coded under probabilities learned from that very document rather than from a generic table. That creates the obvious question: the decoder needs the same probabilities, and they change every symbol. Shipping them would cost more than they save. ## Code first, update after The invariant that makes it work is an ordering rule: 1. The encoder codes symbol `s` using the model's **current** probabilities. 2. The encoder then updates the model with `s`. 3. The decoder decodes `s` using its own model's current probabilities — which match, because it has applied the same updates from the same history. 4. The decoder then applies the identical update. The update at step 2 depends only on symbols that are already in the stream, so by the time the decoder needs it, it has them. Nothing about the model travels on the wire. Reverse the order on either side — update before coding — and the encoder is coding under probabilities the decoder cannot yet have, and the stream is unreadable from the first symbol. ## What determinism actually requires "Same update" is a stronger requirement than it reads: - **Integer arithmetic only.** Frequency counts and the slice computation are integers precisely so that both sides compute the identical boundaries. Floating-point probabilities can differ in the last place depending on how expressions are ordered or evaluated, and one differing boundary is enough. - **Same starting state.** Initial counts, the alphabet's order along the line, and the presence of an escape symbol are all part of the format. - **Same rescaling.** Models periodically halve all counts to bound the total and to weight recent history. The threshold and the rounding of that halving must match exactly on both sides. - **Same handling of the unseen.** A symbol with zero probability has a zero-width slice and cannot be coded at all. Either every symbol begins with count 1, or the model reserves an escape symbol that means "the next symbol comes from a fallback distribution". ## The failure mode Desynchronisation is total and silent. If the two models disagree by one count, the decoder picks a slice boundary the encoder did not use, decodes a different symbol, and then updates its model with that wrong symbol — so the divergence compounds. There is no self-synchronising structure in the stream, no codeword boundary to resume from, and the output after the divergence point is plausible-looking garbage rather than an error. Practical defences are external to the coder: decode-after-encode verification on write, a checksum over the decoded content, and framing the stream into independently coded blocks so a fault's blast radius ends at a block boundary. ## Where the stream ends The same lockstep argument applies to termination. The digit string carries no end marker of its own, and a decoder that keeps going will happily turn the flush bits into extra symbols. Two options, and a format must pick one: | approach | cost | notes | |---|---|---| | transmit the symbol count | a few bits or bytes of header | needs the length known before writing, awkward for streaming | | reserve an end-of-message symbol | a few bits, charged as its probability | self-terminating; the symbol needs a permanent non-zero slice | ## What adaptation buys, and what it costs - **Buys:** no table shipped, and probabilities that track local statistics — a document that changes character partway through is coded well in both halves. - **Costs:** the first few hundred symbols are coded under a poor model (the learning cost), the model update is on the hot path for every symbol on both sides, and the decoder now depends on the exact update rule forever, which makes that rule part of the archival format rather than an implementation detail. Ecosystems differ in how they express the shared model — some implementations share one routine compiled into both roles, others specify it in prose and implement it twice — but the requirement is the same either way: one definition of the update, exercised by round-trip tests rather than by review.