In 1948 Claude Shannon published A Mathematical Theory of Communication and did something audacious: he made information a measurable quantity — something you can count, trade, and run out of, like energy or water. Two moves made it work. First, he declared meaning out of scope: whether a message is a love letter or a weather report is, in his words, “irrelevant to the engineering problem.” Second, he identified information with the resolution of uncertainty — you gain information exactly when something you weren’t sure about gets settled.
From those two moves an entire theory unfolds, and it keeps landing on the same astonishing answers: how far any file can be compressed; how fast any wire, cable, or radio band can carry data; why your Wi-Fi renegotiates its speed when you walk behind a wall; why the loss function training a language model is, quite literally, a compression objective. This page walks the whole arc — surprise, entropy, codes, typicality, mutual information, noise, and the channel — with every idea both proved and playable. Everything below is interactive: drag the bars, flip the bits, corrupt the images.
Start with a single event. A friend tells you the sun rose this morning: you have learned nothing, because you were already certain. She tells you a fair coin came up heads: you have learned a little. She tells you the exact order of a shuffled deck of cards: you have learned a great deal. The less probable the event, the more it tells you — so the information in an event should be a decreasing function of its probability $p$. Which one?
Three innocent requirements pin it down completely. Certainty should carry nothing ($p=1$ gives $0$). The measure should vary smoothly with $p$. And independent surprises should add: learning two unrelated facts should inform you by the sum of the parts. Since independent probabilities multiply, we need a function that turns multiplication into addition — and that is the logarithm, and nothing else.
The surprise (self-information) of an event of probability $p$ is $$h(p) \;=\; \log_2 \frac{1}{p} \;=\; -\log_2 p .$$
The base of the logarithm sets the unit. Base 2 gives bits — the information in one fair coin flip; base $e$ gives nats. The name bit (binary digit) was coined by John Tukey and first appeared in print in Shannon’s 1948 paper.
One fair coin flip is worth exactly 1 bit; one roll of a die, $\log_2 6 \approx 2.58$ bits; drawing the ace of spades from a full deck, $\log_2 52 \approx 5.70$ bits. The curve below is steep near zero — and that steepness is the whole drama of the subject. Rare events are enormously informative; near-certain ones are almost silent.
Drag the slider — or drag directly on the curve. For a sense of scale beyond the plot: a specific 13-card bridge hand has probability $1/635{,}013{,}559{,}600$, a surprise of about 39.2 bits. A six-number lottery jackpot is worth about 24 bits. Both fit in a few bytes — surprise grows only logarithmically, which is why astronomical improbability is still cheap to write down.
A single event has a surprise; a source of events — a random variable — has an expected surprise. That average is the celebrated quantity.
For a discrete random variable $X$ with probabilities $p_1, \dots, p_n$, the entropy is $$H(X) \;=\; \sum_{i=1}^{n} p_i \log_2 \frac{1}{p_i} \;=\; -\sum_{i=1}^{n} p_i \log_2 p_i \quad \text{bits},$$ with the convention $0 \log 0 = 0$ (an impossible outcome contributes nothing).
Two bounds frame it: $\;0 \le H(X) \le \log_2 n$. The minimum is attained exactly when one outcome is certain; the maximum exactly when all $n$ outcomes are equally likely. Uniform ignorance is the most expensive state of ignorance.
Entropy is best understood with your hands. Below is a distribution over eight outcomes. Drag the bars — or focus the chart and steer with the arrow keys — and watch $H$ respond: it rises as you flatten the distribution, collapses as you concentrate it, and tops out at $\log_2 8 = 3$ bits when all bars are equal. The meter underneath decomposes the total outcome by outcome — each segment is one outcome’s contribution $p_i \log_2(1/p_i)$. Notice how outcomes with tiny probability contribute little despite their huge surprise: they almost never happen, so they barely move the average.
The readout also shows $2^{H}$, the perplexity: the size of the uniform distribution with the same entropy. A source with entropy 2.3 bits is “as unpredictable as” a fair $2^{2.3} \approx 5$-sided die — the standard yardstick for language models.
The special case of two outcomes deserves its own curve. The binary entropy function $$H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$$ will reappear constantly — it prices biased coins, noisy channels, and error rates alike. It peaks at 1 bit for a fair coin and falls off steeply: a 90:10 coin is worth only 0.47 bits per flip, and an 11:89 coin almost exactly half a bit.
The logarithm is concave, so Jensen’s inequality gives $$H(X) = \sum_i p_i \log_2 \frac{1}{p_i} \;\le\; \log_2 \sum_i p_i \cdot \frac{1}{p_i} \;=\; \log_2 n,$$ with equality iff all $1/p_i$ are equal, i.e. $p_i = 1/n$. The same one-liner, applied with a second distribution inside the logarithm, will prove Gibbs’ inequality below — concavity of the log does a remarkable share of this field’s heavy lifting.
Here is the interpretation that makes entropy concrete. You must identify an unknown outcome by asking yes/no questions. How many questions do you need, on average, if you ask cleverly?
Take tomorrow’s weather in a town where $p(\text{sun}) = \tfrac12$, $p(\text{cloud}) = \tfrac14$, $p(\text{rain}) = p(\text{snow}) = \tfrac18$. The naive strategy asks two questions no matter what (“is it sun or cloud?”, then which). The clever strategy asks about the likely half first: “is it sun?” — done in one question half the time. On average it uses $$\tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \ \text{questions},$$ and the entropy of the weather is $$H = \tfrac12\log_2 2 + \tfrac14 \log_2 4 + \tfrac18\log_2 8 + \tfrac18\log_2 8 = 1.75 \ \text{bits}.$$ Not a coincidence: each outcome sits at depth $\log_2(1/p)$ in the question tree, and no strategy can beat the entropy on average.
Draw a day and watch it fall through both trees; the shaped tree spends its questions where the probability is. Over many days its average converges to 1.75 — the entropy — while the balanced tree stays pinned at 2.
Now the pivotal observation. Write down the answers you receive — yes, no, no, yes… — as 1s and 0s. The question strategy has turned each outcome into a binary codeword, and the expected number of questions is the expected length of the code. Guessing games and data compression are the same subject, and entropy is about to become the law that governs both.
A code assigns each symbol a string of bits. If no codeword is a prefix of another (a prefix code), the receiver can decode a stream instantly, without separators — exactly as a question tree needs no punctuation between rounds: codewords are the leaves of a binary tree. Short codewords use up the tree fast; the accounting is exact and is called the Kraft inequality.
A prefix code with codeword lengths $\ell_1, \dots, \ell_n$ exists if and only if $$\sum_{i=1}^{n} 2^{-\ell_i} \;\le\; 1 .$$ McMillan showed the same holds for any uniquely decodable code — allowing cleverer-than-prefix codes buys nothing.
Grow the complete binary tree of depth $\ell_{\max} = \max_i \ell_i$; it has $2^{\ell_{\max}}$ leaves. A codeword of length $\ell_i$, being a node at depth $\ell_i$, claims all $2^{\ell_{\max}-\ell_i}$ leaves beneath it, and the prefix property says no two claimed sets overlap. So $\sum_i 2^{\ell_{\max}-\ell_i} \le 2^{\ell_{\max}}$; divide through. Conversely, if the lengths satisfy the inequality, assign codewords greedily from shortest to longest and the budget never runs out.
Given the budget, the best code spends it the way the clever questioner did: short words for common symbols, long words for rare ones — ideally length $\log_2(1/p_i)$ for a symbol of probability $p_i$. Minimizing average length $\sum_i p_i \ell_i$ subject to Kraft lands, at the optimum, exactly on the entropy. This is Shannon’s first great theorem.
Every uniquely decodable binary code for $X$ has expected length $L \ge H(X)$, and there is a prefix code with $L < H(X) + 1$ (take $\ell_i = \lceil \log_2 (1/p_i) \rceil$). Encoding blocks of $n$ symbols drives the overhead per symbol below $1/n$: $$\frac{L_n}{n} \;\longrightarrow\; H(X).$$ Entropy is not a metaphor for the size of data — it is the size of data, in bits per symbol, and no compressor of any design, present or future, can beat it on average.
The optimal symbol-by-symbol code is constructed by Huffman’s algorithm (1952, a term-paper assignment): repeatedly merge the two least probable symbols into one, building the tree from the leaves up. Try it — the box below Huffman-codes whatever you type, live.
In the chart, the dot on each row marks the ideal length $\log_2(1/p)$; the bar is the Huffman codeword actually assigned. Huffman must round to whole bits — that rounding is the gap between its average and the entropy. Arithmetic coding (and its modern descendant in every video codec) removes even that, encoding the whole message as one long binary fraction and paying fractional bits per symbol; its output length is the entropy to within two bits total.
Why is the entropy bound achievable at all? The deep reason is a concentration phenomenon, and it is the least known of the field’s great ideas. Flip a 90:10 coin 100 times. There are $2^{100}$ possible sequences — but you will essentially never see most of them. You will see a sequence with about 90 heads, and all such sequences have roughly the same probability. Chance, at scale, is not wild; it is monotonously predictable.
For i.i.d. $X_1, \dots, X_n$ with entropy $H$, the law of large numbers applied to the random variable $-\log_2 p(X_i)$ gives $$-\tfrac{1}{n} \log_2 p(X_1, \dots, X_n) \;\longrightarrow\; H \quad \text{in probability}.$$ Consequently, for large $n$ the outcomes split in two: a typical set of roughly $2^{nH}$ sequences, each with probability close to $2^{-nH}$, which together carry almost all the probability — and everything else, which is individually possible and collectively negligible.
That is compression, explained in one sentence: to describe $n$ flips you need not name one of the $2^n$ possible sequences, only one of the $2^{nH}$ plausible ones — and naming one of $2^{nH}$ things takes $nH$ bits. Below, watch the typical set become a vanishing fraction of all sequences while swallowing all of the probability.
The figure computes the set exactly, and honesty pays: at $n=100$, $p=0.9$ the smallest collection of sequences covering 99% of the probability numbers about $2^{65}$ — already a $2^{-35}$ sliver of the $2^{100}$ possible, one sequence in thirty-four billion. The theorem’s cleaner promise of $2^{nH} = 2^{47}$ is the $n \to \infty$ limit; at finite $n$ the overhead is $O(\sqrt{n})$ bits in total — $O(1/\sqrt{n})$ per flip — so drag $n$ up and watch the naming cost per flip sink toward $H_2(p)$. Every lossless compressor, from ZIP to PNG to FLAC, is at heart a naming scheme for typical sets.
Natural language is a random source too — a stupendously structured one. English text over 26 letters and a space could carry $\log_2 27 \approx 4.75$ bits per character if letters were uniform and independent. They are neither: e outnumbers z a hundred to one, q is glued to u, and after “informatio” the next letter is hardly random at all. Each layer of structure lowers the entropy. For a source with memory the right per-character measure is the entropy rate, $$H \;=\; \lim_{n \to \infty} \tfrac{1}{n} H(X_1, \dots, X_n) \;=\; \lim_{n \to \infty} H(X_n \mid X_1, \dots, X_{n-1}),$$ the average uncertainty of the next character given everything before it — and each model below reports exactly that conditional uncertainty for its own memory length, stepping down toward the true rate as the context grows.
Shannon’s 1948 paper contains a famous party trick: generate text from models that know progressively more about English. The generator below performs it live. Its statistics are learned, on the spot, from the very page you are reading — order 0 knows only which characters occur, order 1 knows their frequencies, order 2 knows pairs, order 3 knows triples.
By order 2 the gibberish grows word-shaped; by order 3 it is haunted by almost-English. Shannon pushed further with human subjects: ask a person to guess the next character of a text, count the guesses, and the guesser’s success rate bounds the entropy. His 1951 estimate: printed English carries roughly 0.6–1.3 bits per character — meaning ordinary text is about 73–87% redundant, which is why crossword puzzles are possible and why your damaged texts remain readable.
| model of English | bits/char | flavor of output |
|---|---|---|
| uniform over 27 characters | 4.75 | xfoml rxkhrjffjuj |
| letter frequencies (order 1) | ≈ 4.0 | ocro hli rgwr nmielwis |
| digram statistics (order 2) | ≈ 3.3 | on ie antsoutinys are |
| trigram statistics (order 3) | ≈ 3.1 | in no ist lat whey cratict |
| word frequencies | ≈ 2.1 | representing and speedily is an good |
| human prediction (Shannon 1951) | 0.6 – 1.3 | English |
| large language models (2020s) | < 1 | English |
Read the last two rows together: prediction and compression are the same act. A model that assigns probability $q(\text{next char} \mid \text{context})$ can drive an arithmetic coder that spends $-\log_2 q$ bits on that character — better predictions, shorter files. A large language model is, mathematically, the best compressor of text ever built, and its training loss is precisely the cross-entropy we meet two sections from now.
So far, one source. The field opens up when there are two random variables, because then we can ask the question underneath all measurement, inference, and communication: how much does observing $Y$ tell you about $X$?
Joint entropy $H(X,Y)$ is the entropy of the pair. Conditional entropy $$H(X \mid Y) \;=\; \textstyle\sum_y p(y)\, H(X \mid Y{=}y)$$ is the uncertainty about $X$ that survives observing $Y$. They obey the chain rule $H(X,Y) = H(Y) + H(X \mid Y)$, and conditioning never hurts: $H(X \mid Y) \le H(X)$.
The mutual information is the reduction: $$I(X;Y) \;=\; H(X) - H(X \mid Y) \;=\; H(X) + H(Y) - H(X,Y).$$ It is symmetric — $Y$ tells you exactly as much about $X$ as $X$ tells you about $Y$ — nonnegative, and zero precisely when the two are independent.
Below, a town where it rains 30% of days, and a commuter who carries an umbrella — reliably on rainy days, rarely on dry ones, with sliders for both habits. The left panel is the joint distribution drawn as areas. The right panel shows the entropy accounting: two bars for $H(\text{rain})$ and $H(\text{umbrella})$, overlapping by exactly $I$ — the shared information.
Slide the two habits toward each other and the overlap dies: when the umbrella no longer depends on the weather, seeing it tells you nothing — $I=0$. Make the habit perfect and the bars merge to the extent the two variables can share uncertainty. Mutual information is the honest currency of evidence: it is what a test tells you about a disease, a pixel about a scene, a received signal about a transmitted one.
One more property completes the toolkit. If $X \to Y \to Z$ form a chain — $Z$ is computed from $Y$ alone, never seeing $X$ — then $I(X;Z) \le I(X;Y)$. This data-processing inequality is the conservation law of the field: no algorithm, however ingenious, can extract from data more information about the world than the data contains. Processing can distill information; it cannot create it.
Compression needs a model: the code lengths are chosen to fit some distribution $q$. But messages arrive from the true distribution $p$. If your model is wrong, every symbol costs $-\log_2 q(x)$ bits but occurs with frequency $p(x)$ — you pay, on average, the cross-entropy, and the excess over $H(p)$ is the price of your wrong worldview.
$$H(p, q) = \sum_x p(x) \log_2 \frac{1}{q(x)}, \qquad D(p \,\|\, q) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)},$$ so that $H(p,q) = H(p) + D(p\,\|\,q)$: the unavoidable entropy, plus the overhead. Gibbs’ inequality states $D(p\,\|\,q) \ge 0$, with equality iff $q = p$ — the shortest average description of reality is the one written in reality’s own probabilities.
Below, reality $p$ in blue and a model $q$ in orange, over eight symbols. Drag either — switch which one you’re editing, or focus the chart and use the arrow keys; the red caps show the per-symbol overhead $p(x)\log_2\frac{p(x)}{q(x)}$ where the model underestimates, and the readout totals the damage.
Two things to try. Press q writes off a symbol: the model assigns (nearly) zero to something that keeps happening, and the divergence explodes — assign zero probability to the possible and you owe unbounded bits. And press swap: $D(p\|q) \ne D(q\|p)$. KL is not a distance; direction matters, because it always bills the coder’s surprise against reality’s frequencies.
This quantity now runs the world’s server farms. Training a classifier or a language model by “cross-entropy loss” means: make the model’s $q$ cheap to encode reality with. Since $H(p)$ is fixed by the data, minimizing cross-entropy is minimizing $D(p\|q)$ — machine learning’s central objective is literally “compress the training distribution well.” Maximum likelihood estimation, too, is KL minimization in disguise.
Everything so far assumed the bits arrive intact. Shannon’s paper is titled a theory of communication because its destination is the opposite case: a sender, a receiver, and between them a medium that garbles. His schematic of the problem has become the field’s coat of arms:
The simplest interesting channel is the binary symmetric channel (BSC): each transmitted bit arrives flipped with probability $\varepsilon$, independently. Send an image through it and you can watch information die:
Every received bit still carries some news about the sent one — until $\varepsilon = \tfrac12$, where the output is independent of the input and the wire might as well be cut. The capacity curve in the inset quantifies it: of each transmitted bit, $H_2(\varepsilon)$ bits are spent describing the noise, and only the remainder describes your message.
For a channel with input $X$ and output $Y$, the capacity is the mutual information between what goes in and what comes out, maximized over how you use the input: $$C \;=\; \max_{p(x)} I(X;Y) \quad \text{bits per channel use}.$$ For the BSC the best input is a fair coin and $C = 1 - H_2(\varepsilon)$: at $\varepsilon = 0.11$, almost exactly half a bit per use; at $\varepsilon = 0.5$, zero.
Capacity would be a mere curiosity if noise doomed communication anyway. The obvious defense is repetition: say every bit three times and majority-vote. It helps — and it is a terrible deal. To push the error rate toward zero you must repeat more and more, and your data rate drowns:
Before 1948, engineers assumed this trade was a law of nature: perfect reliability must cost the rate itself. Shannon’s second great theorem says it does not — and it is one of the most counterintuitive true statements in engineering.
For any transmission rate $R < C$ there exist codes of long enough block length whose error probability is as small as you please — while the rate stays at $R$. Conversely, at any rate above $C$, the error probability is bounded away from zero for every code. Noise does not set a limit on quality; it sets a limit on speed.
Shannon’s proof is itself a jewel: he showed that a random code achieves capacity — long random codewords land far apart in Hamming distance, so the noise sphere around each received word almost surely contains just one plausible codeword. Finding practical codes that do what randomness promised took another fifty years.
One corollary completes the architecture in Shannon’s schematic: a source with entropy rate $H$ can be sent reliably over a channel of capacity $C$ exactly when $H < C$ — and doing it in two independent stages, compress to bits, then protect the bits, loses nothing. This source–channel separation theorem is why the bit is a universal interface: the same ZIP file travels unchanged over Wi-Fi, fiber, or a Mars relay, each link running its own code, none needing to know what the bits mean.
The first constructive step came from Shannon’s Bell Labs office mate. Richard Hamming’s 1950 code packs 4 message bits into 7 transmitted bits so that the three added parity bits triangulate any single error. Each parity bit watches an overlapping trio of message bits — draw them as circles and every bit sits in a distinct region. Flip any bit below (message or parity) and watch the failed checks point straight at the culprit:
Rate $\tfrac47 \approx 0.57$, one guaranteed correction per block — already a better bargain than triple repetition (rate 0.33, same single-error protection). Modern LDPC and polar codes, the descendants of this idea, run your phone, your SSD, and the Mars relays within a few percent of the Shannon limit. Below, the same corrupted channel as before — but now the image travels Hamming-coded:
The code loses only when two flips land in the same 7-bit block. At small $\varepsilon$ that is rare — the residual error falls like $\varepsilon^2$ — so a modest 75% overhead buys orders of magnitude in fidelity. Longer, cleverer codes push this all the way to Shannon’s promise.
The theory built above is discrete, but its reach is not. A short tour of where these seven or eight definitions turned out to run things:
Real channels. For a channel corrupted by additive white Gaussian noise of power $N$, with average signal power at most $S$ and bandwidth $B$ hertz, the Shannon–Hartley theorem gives $$C \;=\; B \log_2\!\Bigl(1 + \tfrac{S}{N}\Bigr) \ \text{bits/second},$$ the equation your router lives by — and the capacity-achieving input is itself Gaussian-distributed: the best signal is indistinguishable from noise, just as Shannon’s best codes were random. Every trick of modern radio — spreading power across bandwidth, adapting the rate as you walk behind a wall, MIMO’s multiple antennas — is an attempt to move along this curve:
Physics. The name “entropy” is no accident: Shannon’s formula is Boltzmann and Gibbs’ statistical-mechanics entropy, $S = -k_B \sum p_i \ln p_i$, in different units. The bridge is load-bearing. Landauer’s principle (1961) says erasing one bit of information in any physical memory must dissipate at least $k_B T \ln 2$ of heat — about $3 \times 10^{-21}$ joules at room temperature — and this is precisely what exorcises Maxwell’s demon: the demon’s measurements fill a memory, and the thermodynamic bill for wiping it repays every joule the sorting gained. Information is physical.
Lossy compression. When the reconstruction is allowed to differ from the original — JPEG, MP3, streaming video — the same machinery still governs the trade: Shannon’s rate–distortion theory prices bits against fidelity, which is how a photo can ship in far fewer bits than its entropy. Lossless coding is the special case of zero tolerated distortion.
Shortest descriptions. Kolmogorov (1965) redefined the complexity of an individual object — not a random source — as the length of the shortest program that prints it. The two theories agree where they meet: for data drawn from a random source, the expected Kolmogorov complexity per symbol converges to the entropy rate. Randomness and incompressibility turn out to be the same property, and “science” acquires a crisp caricature: finding the short program behind long data. Occam’s razor, with units.
Gambling. Kelly (1956) showed that a gambler with side information about an event — a private wire ahead of the bookmakers — can grow capital faster, and the increase in the optimal doubling rate is exactly the mutual information between the wire and the outcome, in bits per bet (at fair odds, that increase is the whole growth rate). Information has a market price, and it is paid in the doubling rate of your money. Modern portfolio growth theory descends from this observation.
Learning. Cross-entropy loss, we saw, is compression. But the connections run deeper: the minimum description length principle says the best model of data is the one minimizing model-bits plus residual-bits — a formal Occam’s razor; the information bottleneck frames representation learning as keeping $I(\text{representation};\text{label})$ while shedding $I(\text{representation};\text{input})$; and the data-processing inequality quietly disciplines every pipeline: features can only lose information about the world, never add it.
A century that began by asking how many telegraph clicks a message needs ended by measuring language models in bits per character. The field’s whole apparatus — surprise, entropy, divergence, capacity — turned out to be the accounting system for every process that predicts, compresses, transmits, or learns. Not bad for a theory that started by refusing to say what anything means.