Information theory

Which lens this is. Two spokes hold a page under this name, and they are not duplicates. This one is the learning lens — the part of the theory that bears on fitting models, kept beside bayesian-inference because information-theory-inference-learning-algorithms argues the two subjects are one. ../mathematics-wiki's mathematics-wiki/information-theory is the subject: the measures, the two coding theorems, and the constructive half (mathematics-wiki/coding-theory) that this page has never covered. Cite that one for the theory, this one for the identity with inference.

Shannon's account of how much information a message carries, how far it can be compressed, and how reliably it can be sent through a channel that corrupts it. The page exists in a machine-learning spoke for one reason: information-theory-inference-learning-algorithms argues the two subjects are one subject, and when it was routed here on 2026-08-02 no spoke in the hub owned information or coding theory.

The two problems

Compression. How few bits can represent a source without losing it. The answer is its entropy; the source coding theorem sets the floor and symbol and stream codes (Huffman, arithmetic coding) approach it.

Noisy-channel coding. How much can be sent through a channel that flips bits. MacKay opens on a disk drive rather than an abstraction: one flipping 10% of bits, against the roughly 10⁻¹⁵ error rate you need to read and write a gigabyte a day for ten years. Two responses are available.

• The physical solution buys incremental reliability at ever-increasing cost. Better components, an evacuated enclosure, larger magnetic patches, colder circuitry.
• The system solution accepts the channel as it is, adds an encoder and a decoder, and uses deliberate redundancy to infer both the message and the noise.

Shannon's noisy-channel coding theorem says the second works, and says how far: reliable communication is possible at every rate up to the channel's capacity and impossible beyond it. For that 10%-error channel capacity is about 0.53, so a rate-½ code reaches an arbitrarily small error rate with two noisy drives, where naive triple repetition needs sixty to do worse information-theory-inference-learning-algorithms.

Why it sits next to learning

MacKay's claim is that compression, error correction and inference run on the same machinery, and his book's structure is the argument:

• The decoder for a low-density parity-check code is the sum–product algorithm — belief propagation on a factor graph — which is the same message passing used to marginalize a probabilistic model. Optimal decoding is NP-complete; approximate inference is what makes the codes work.
• Compression is prediction. A code assigns short strings to what the model expects, so a better model of the source is directly a better compressor.
• Chapter 19 runs the accounting the other way, on evolution: natural selection's teaching signal is at most one bit per offspring, since all it reports is whether an individual had more descendants or fewer.

The modern restatement, that a language model is a compressor, descends from this identity. That argument's home spoke would be ../llm-inference-wiki, which has no page on it; the derivation stays here.

Scope note

This page covers only what the ingested book establishes and what bears on learning. Coding theory proper — hash codes, binary codes, turbo and fountain codes, constrained channels — is roughly half that book and was unowned across the hub when this page was written.

That changed on 2026-08-15. At the curator's instruction the coding half was built out in ../mathematics-wiki, which had already claimed information and coding theory as a growth edge: mathematics-wiki/information-theory, mathematics-wiki/coding-theory, entropy, source-coding-theorem, noisy-channel-coding-theorem, error-correcting-code, low-density-parity-check-code and fountain-code. The book itself did not move — it is still sourced here, and those pages cite it across the spoke boundary. A separate spoke turned out not to be needed.

Related

information-theory-inference-learning-algorithms · bayesian-inference · monte-carlo-methods · machine-learning · synthesis