Information theory

Which lens this is. Two spokes hold a page under this name, and they are not duplicates. This one is the subject: what information is measured in, what the two coding theorems say, and what they leave unbuilt. ../machine-learning-wiki's machine-learning-wiki/information-theory is the learning lens — the part of the same material that bears on fitting models, kept next to bayesian-inference because the book both pages rest on argues the two subjects are one. Cite this page for the theory, that one for the identity with inference.

The measure of how much a message tells you, and the two limits that follow from it: how far a source can be compressed, and how fast it can be sent through a channel that corrupts it. Founded by claude-shannon in 1948, and the one body of theory in this corpus whose central results are negative — they say what no method can beat, and were proved before anyone could build a method that came close.

Everything on this page comes from one book, and the book is not held in this spoke. information-theory-inference-learning-algorithms (MacKay, Cambridge University Press 2003) was routed to ../machine-learning-wiki on 2026-08-02, hours before this spoke existed, on the ML half of its substance. The routing stands; the source page stays there and the PDF stays in that spoke's raw/. What lives here is the subject the routing note flagged as homeless. This spoke still holds no information-theory text of its own — growth edge 6 is opened, not closed.

The two quantities

The Shannon information content of one outcome, h(x = aᵢ) = log₂(1/pᵢ), measured in bits. The less probable an outcome, the more its occurrence tells you. The logarithm is not a convention picked for convenience: it is what makes the measure additive over independent variables, since P(x,y) = P(x)P(y) gives h(x,y) = h(x) + h(y) directly.

The entropy of an ensemble, H(X) = Σᵢ pᵢ log₂(1/pᵢ), is the average information content of its outcomes. Its binary special case H₂(p) = p log₂(1/p) + (1−p) log₂(1/(1−p)) runs through every result on this page. See entropy for the joint, conditional and mutual quantities built on it.

The two theorems

They point in opposite directions and are proved by the same machinery.

source-coding-theorem — N outcomes drawn independently from an ensemble of entropy H can be compressed into a little more than NH bits and no fewer. Entropy is a floor on compression, reached in the limit of long blocks.
noisy-channel-coding-theorem — every channel has a capacity C = max I(X;Y), and reliable communication is possible at any rate below C and impossible above it. Capacity is a ceiling on communication, and the surprise is that it is not zero: a channel that corrupts every tenth bit still carries 0.53 error-free bits per use.

Both are asymptotic, both are proved by looking at long blocks, and both are about what exists rather than about what to do.

The gap the subject spent fifty years closing

Shannon's proof of the channel theorem is an averaging argument: he showed the mean error probability over all randomly chosen codes is small, so good codes must exist. MacKay's analogy is weighing all the babies in a class at once to prove one of them weighs under 10 kg — you learn that a light baby exists, and nothing about which one. Random codes are good; encoding and decoding them costs resources exponential in the blocklength.

"Unfortunately we have not found out how to implement these encoders and decoders in practice; the cost of implementing the encoder and decoder for a random code with large N would be exponentially large in N."

That gap is what coding-theory is: the constructive half, which took until the 1990s to produce codes that both approach capacity and can actually be run (low-density-parity-check-code, fountain-code).

Where the subject sits relative to this corpus

It is the corpus's first body of theory whose object is a communication system rather than a space of functions or a sample space, and it is built almost entirely out of probability-theory — ensembles, independence, the law of large numbers, Chebyshev's inequality. The proofs of both theorems are laws of large numbers wearing different clothes: the typical set in the source theorem and the jointly-typical set in the channel theorem are the same construction, applied once to a source and once to a source-and-output pair.

The other prerequisite is abstract-algebra — a linear code is a subspace over the field F₂, and the parity-check matrix that defines it is linear algebra over that field.

Where this is used across the hub

../machine-learning-wiki — machine-learning-wiki/information-theory holds the learning lens and information-theory-inference-learning-algorithms the source page. The seam is real rather than nominal: the decoder of an LDPC code is the sum–product algorithm, the same message passing used to marginalize a probabilistic model.
../cryptography-wiki — that spoke owns codes as construction material: Reed–Solomon inside a polynomial commitment, proximity gaps, list decoding. The coding theorems are here; a scheme built over them is there. Reed–Solomon appears on both sides and means the same thing.
../llm-inference-wiki — compression is prediction, so a better model of a source is directly a better compressor. MacKay states the extreme form of it in 1999 terms: "A general purpose compressor that can discover the probability distribution of any source would be a general purpose artificial intelligence!"

entropy · source-coding-theorem · noisy-channel-coding-theorem · coding-theory · error-correcting-code · claude-shannon · probability-theory · mathematics · information-theory-inference-learning-algorithms · synthesis