For a lossless scheme, what fraction of fixed-length inputs can shrink by at least 10 bits?

## From 'some input loses' to 'almost every input loses' The plain pigeonhole statement is weak-sounding: among the `2^n` inputs of length `n`, at least one cannot shrink, because only `2^n - 1` shorter strings exist. A margin of one invites the reply 'so it fails on a handful of inputs, who cares'. Counting the **winners** instead turns the same argument into something much stronger, and it is the version worth carrying into a review. ## The count, step by step Ask how many inputs can shrink by at least `k` bits, meaning the output has length at most `n - k`. 1. An input wins only if its output is one of the strings of length at most `n - k`. 2. Those strings number `1 + 2 + 4 + ... + 2^(n-k) = 2^(n-k+1) - 1`. 3. Compression is injective, so no two winners share an output: the number of winners is at most the number of available short strings. 4. The fraction of the `2^n` inputs that can win is therefore below `2^(n-k+1) / 2^n = 2^(1-k) = 1 / 2^(k-1)`. | Bits saved, k | Short-enough outputs | Fraction of inputs that can win | Reading | |---|---|---|---| | 1 | 2^n - 1 | under 1 | almost everything might save a single bit | | 4 | 2^(n-3) - 1 | under 1 in 8 | a nibble's saving is already a minority | | 10 | 2^(n-9) - 1 | under 1 in 512 | barely a byte of saving, and 99.8% cannot get it | | 20 | 2^(n-19) - 1 | under 1 in 524,288 | two and a half bytes is a one-in-half-a-million event | The bound halves with every extra bit demanded, which is why 'shrinks everything by even a little' collapses so fast. Halving a 1,000-bit input means `k = 500`, available to under one input in `2^499`. ## The thing people misread - **The fraction does not depend on `n`.** Bigger inputs are not looser; `2^(1-k)` has no `n` in it. Intuition says a megabyte has more slack than a kilobyte, and for *real* megabytes it usually does, but that is a fact about real data, never about the space of all inputs. - **Count outputs of length at most `n-k`, not exactly `n-k`.** Forgetting the shorter ones is the usual slip, and it changes the answer by a factor of two. - **The bound is an upper limit on winners, not a prediction.** A scheme may do far worse than the bound on a given corpus; it can never do better. - **It is a statement about the whole input space.** It is not contradicted by a benchmark where everything shrank. ## Why real archives still average large savings The files anyone actually stores are not drawn uniformly from all `2^n` strings. They are outputs of processes with heavy structure: repeated field names, aligned records, long runs, a small effective alphabet, text in one language, numbers in narrow ranges. That population is an unimaginably small subset of the input space, and a coder is engineered to spend the short outputs precisely on it. Both facts are true at once: - Almost no inputs, counted over the whole space, can shrink meaningfully. - Almost every input anyone stores does shrink meaningfully. There is no tension. The coder has chosen where to spend its short outputs, and the inputs nobody stores pay for it. That is the counting bound not as an obstacle but as a design budget. ## Where the number earns its keep In a review, the sharp form answers a claim that the plain form cannot. 'Guaranteed 20% smaller on any input' is refuted by the plain argument, but so is 'guaranteed one byte smaller on any input', and the sharp form tells you how far the second claim is from reality: an eight-bit saving is available to under one input in 128. It also gives the right question for any ratio claim, which is always *on which corpus*, since a ratio without a population named is not a claim that can be checked. And it explains why the interesting engineering question is never 'how do we shrink everything' but 'which inputs are worth spending short outputs on, and what do we do with the rest' — which is what block-level fallbacks and per-class compression policies exist to answer.