Why can an arithmetic coder spend about 0.15 bits on a symbol whose probability is 0.9?
answer
- cost is a multiplication, not a string
- widths multiply, so bit costs add
- log2(1/p) per symbol
- rounding happens once per message
- 0.9 narrowing costs 0.152 bits
basics
~20 sBecause a symbol costs a multiplication of the interval, not an appended codeword. Narrowing by 0.9 consumes log2(1/0.9) = 0.152 bits of the final number, and the rounding to whole bits happens once for the message, not per symbol.
solid answer
~40 sA symbol's cost in an interval coder is how much it shrinks the interval: coding a symbol of probability `p` multiplies the width by `p`, and the digits needed to name a point inside a width-`w` interval is about `log2(1/w)`. So a 0.9-probability symbol adds `log2(1/0.9) = 0.152` bits to the eventual total. Nothing is written for it on its own — the costs accumulate in the width and are converted to whole bits **once**, at the end, with under two bits of slack for the whole message. Code ten such symbols and the width is `0.9^10 = 0.349`, about 1.52 bits in total, where any scheme that emits a whole codeword per symbol must spend at least 10. That per-symbol rounding is what an interval coder removes.
go deeper
Recall the headline: a symbol's cost is log2(1/p), which can be far below one bit, because nothing is written for the symbol on its own.
Explain the mechanism: widths multiply, so log-costs add, and the conversion to whole bits happens once at the end of the message instead of once per symbol.
Quantify it on a skewed stream and state where the advantage disappears — short messages, near-dyadic probabilities — and that the model, not the coder, sets the ceiling.
Weigh the win against what it costs: per-symbol arithmetic, a model both sides must reproduce exactly, and a stream with no codeword boundaries to resume from.
## Where the cost of a symbol actually lives In a scheme that writes a codeword per symbol, the cost of a symbol is visible: it is the length of the codeword, and a length is a whole number of bits. Whatever the model believes, no symbol can be written in less than one bit, because there is nothing shorter than a one-bit string. In an interval coder the cost of a symbol is not a string at all. It is a **multiplication**. Coding a symbol of probability `p` replaces the current interval with a sub-interval `p` times as wide. Since the digits eventually needed to name a point inside an interval of width `w` is about `log2(1/w)`, and widths multiply, the costs **add** in exactly the fractional amounts you would want: - `p = 0.9` costs `log2(1/0.9) = 0.152` bits. - `p = 0.5` costs exactly 1 bit. - `p = 0.1` costs `log2(10) = 3.32` bits. No individual symbol ever causes a fractional digit to be written, because no individual symbol causes a digit to be written at all. Digits appear only when the accumulated narrowing has settled a leading bit of the final number. ## The rounding is paid once This is the whole answer in one sentence: **an interval coder rounds to a whole number of bits once per message; a per-symbol code rounds once per symbol.** Work it through on a skewed archival source. Suppose the model gives the next symbol probability 0.9, and ten such symbols arrive in a row: 1. The interval width becomes `0.9^10 = 0.3487`. 2. Naming a point inside it takes about `log2(1/0.3487) = 1.52` bits. 3. Add the small constant for making the string self-delimiting and terminating the message — call it under two bits — and the whole run costs three or four bits. Any scheme that emits a whole codeword per symbol spends **at least ten** bits on the same ten symbols, because it must write at least one bit ten times. The gap is not a subtle constant factor; on a strongly skewed binary source it is most of the file. If the ten symbols are a typical mix from that source rather than all the likely one, the interval coder's cost tracks the source's own per-symbol content of `0.469` bits, so about 4.7 bits against a floor of 10. ## What this does and does not buy - It matters most where **one symbol dominates**: log files, sparse bitmaps, a model that has learned the next character almost exactly, or a binary decision that is usually the same way. - It matters least where the model's probabilities are already close to negative powers of two. If every probability is 1/2, 1/4, 1/8, a whole-codeword scheme can match the ideal exactly, and the interval coder may even come out a bit or two behind on its termination overhead. - It is not free. Each symbol costs a multiply and a division or reciprocal on both sides, against a table lookup and a shift for a codeword scheme, which is precisely the pressure that produced numeral-system coders. - It moves the compression burden onto the **model**. An interval coder can spend 0.02 bits on a symbol the model is 99 per cent sure about — but only if the model really is that sure. A badly calibrated model is punished symmetrically: a symbol the model gave 0.001 costs 10 bits. ## The comparison in one table | | whole-codeword scheme | interval coder | |---|---|---| | minimum cost of one symbol | 1 bit | unbounded below; `log2(1/p)` | | cost of `p = 0.9` | 1 bit | 0.152 bits | | rounding overhead | once per symbol | once per message, under ~2 bits | | per-symbol work | table lookup and shift | multiply plus divide, or a table-driven equivalent | | where the win comes from | short codes for frequent symbols | probabilities the model can push toward 1 | ## The trap in the claim The statement "a symbol cost 0.15 bits" describes an accounting identity, not a physical event. Nobody wrote 0.15 of a bit. The interval narrowed, and the final number needed 0.15 bits more precision than it would have without that symbol. Candidates who cannot say that clearly usually reveal it in the next sentence, by claiming that the coder can compress a single symbol below one bit in isolation — it cannot. A one-symbol message still costs a whole number of bits, and there the interval coder has no advantage at all. The advantage is amortised across the message, which is why it shows up on long, skewed streams and vanishes on short ones.
- On what kind of message does this advantage nearly vanish?On short messages, where the fixed termination overhead of a couple of bits is a large fraction of the output, and on sources whose probabilities are already close to negative powers of two, where a whole-codeword scheme is already near-ideal. The win grows with message length and with how skewed the model's probabilities get.
- If the model is badly calibrated, what happens to the output size?It grows, symmetrically. Cost is `log2(1/p)` under the model's own number, so a symbol the model rated 0.001 costs about 10 bits even if it is actually common. An interval coder faithfully spends whatever the model's probabilities say, which is why calibration, not the coder, sets the compression.
- Does coding a single isolated symbol of probability 0.9 really take 0.15 bits?No. A one-symbol message still has to be written as a whole number of bits, so it costs at least one. The 0.152 figure is the marginal contribution that symbol makes to a longer stream's final precision; the saving is amortised across the message, not realised per symbol.
A per-symbol code is a shop that rounds every single item up to the next whole dollar. An interval coder rings the whole basket through once and rounds only the total.
saying these in an interview costs you the question
- Claims a single symbol is physically written as a fraction of a bit
- Reads probability 0.9 as a cost of 0.9 bits
- Says an interval coder beats a whole-codeword scheme on every input
- Thinks the fractional saving applies to one-symbol messages too
- Believes the coder, not the model, decides how small a symbol gets
- Assumes the rounding overhead is charged per symbol