Information theory · interactive

From surprise to compression

Five live simulations that take you from the information in a single event to codes that squeeze a message down to its entropy. Every number is computed exactly, in bits, from distributions you control.

 
▌
5
Concepts
5
Live simulations
6
Quiz questions

The path

Each idea builds on the one before it. Work through them in order, then test yourself in the quiz.

Concept 1

Surprise: information in one event

An event with probability p carries −log₂ p bits of information. One bit is one halving of the possibilities. Learning that a 1-in-8 event happened cuts the possibilities in half three times, so it's worth 3 bits. Events that were nearly certain tell you almost nothing.
01234567800.250.50.751probability pbits
The slider moves on a log scale, so rare events are as easy to reach as common ones.
Probability p
0.1250 ≈ 1 in 8.0
Surprise −log₂ p
3.000 bits
Halving the possibilities
1
1/2
1/4
1/8
p
It takes 3.00 halvings to shrink the whole space (top bar) down to the event (yellow).
Why a logarithm? Because information from independent events should add.
P(both) = 0.1250 × 0.50 = 0.0625
I(both) = 4.000 = 3.000 + 1.000 bits
❯ I(x) = −log₂ p(x)  ·  independent: p(x,y) = p(x)·p(y) ⇒ I(x,y) = I(x) + I(y)
Key idea
Surprise depends only on the probability, not on what the event means. A certain event (p = 1) carries 0 bits. As p → 0, surprise grows without limit. Up to the choice of base, the logarithm is the only continuous function that turns multiplied probabilities into added information.
Concept 2

Entropy: average surprise

Entropy is the expected surprise, the average over all outcomes weighted by how often they happen. It measures how uncertain you are before the outcome is revealed. It is also the fewest bits per outcome, on average, that any lossless code can achieve. It is largest, log₂ n, when every outcome is equally likely.
Each block: width = probability, height = surprise. Total area = Σ p·(−log₂ p) = entropy, so the dashed line (the average height) sits at H.
0123A 1.00B 2.00C 3.00D 3.00H = 1.750bits
A0.500
B0.250
C0.125
D0.125
Entropy H(p)
1.750 bits
Maximum log₂ n
2.000 bits
Relative H / log₂ n
87.5 %
Binary entropy H(q, 1−q)
0½1
Use two outcomes to see your coin here. The curve peaks at 1 bit when q = ½.
❯ H(p) = Σ p(x) · (−log₂ p(x))  ·  0 ≤ H(p) ≤ log₂ n
Key idea
Try the dyadic preset (½, ¼, ⅛, ⅛). Every surprise is a whole number of bits, H = 1.75, and in Concept 4 a Huffman code reaches exactly 1.75 bits per symbol. With "Almost certain", the rare outcome is very surprising (6.6 bits) but happens so seldom that H is only 0.08 bits.
Concept 3

Cross-entropy & KL divergence

Reality draws outcomes from p, but you measure surprise with your model q. Your average surprise is the cross-entropy H(p,q). It is never below H(p); the excess is the KL divergence — the cost of believing the wrong distribution. This is exactly the loss used to train classifiers and language models.

True distribution p

A
0.50
B
0.25
C
0.15
D
0.10

Model q

A
0.15
B
0.15
C
0.35
D
0.35
xp(x)q(x)−log₂ p−log₂ qp·log₂(p/q)
A0.5000.1501.0002.7370.868
B0.2500.1502.0002.7370.184
C0.1500.3502.7371.515-0.183
D0.1000.3503.3221.515-0.181
p-weighted sum1.7432.4310.689
Individual KL terms can be negative where q over-estimates p, but the total is never negative (Gibbs' inequality).
n = 0
KL
Running averages of −log₂ q(x) (pink) and −log₂ p(x) (blue) converge to the dashed lines by the law of large numbers.
Entropy H(p)
1.743
Cross-entropy H(p,q)
2.431
KL D(p‖q)
0.689
Reverse KL D(q‖p)
0.689
❯ H(p,q) = Σ p(x)·(−log₂ q(x)) = H(p) + D(p‖q)  ·  D(p‖q) ≥ 0, = 0 iff p = q  ·  in general D(p‖q) ≠ D(q‖p)
Why machine learning cares
A classifier or language model is a model q. Training minimises the average −log q(true label) over the data, which is an empirical cross-entropy. H(p) is fixed by the data, so minimising cross-entropy is the same as minimising D(p‖q): pulling the model's beliefs toward reality. Try "q confidently wrong". When q puts tiny probability on outcomes that actually happen, the cost explodes.
Concept 4

Huffman coding: bits ≈ surprise

The ideal code gives each symbol a codeword about −log₂ p bits long: short codes for common symbols, long codes for rare ones. Huffman's algorithm builds the best possible prefix-free code by repeatedly merging the two least-likely nodes. Its average length L satisfies H ≤ L < H + 1. It can't do better than that because every codeword must be a whole number of bits.
sympcodelength vs −log₂ p
a0.4550
1 bits · ideal 1.14
b0.182111
3 bits · ideal 2.46
r0.18210
2 bits · ideal 2.46
c0.0911100
4 bits · ideal 3.46
d0.0911101
4 bits · ideal 3.46
Encoded stream (23 bits)
01111001100011010111100
No codeword is a prefix of another, so the stream decodes unambiguously from left to right with no separators.

Building the tree

  1. 1.c 0.091+d 0.091→cd 0.182
  2. 2.cd 0.182+b 0.182→cdb 0.364
  3. 3.r 0.182+cdb 0.364→rcdb 0.545
  4. 4.a 0.455+rcdb 0.545→arcdb 1.000
At each step the two lightest nodes join, the left side gets a 0 and the right side a 1. A symbol's code length is the number of merges it takes part in.
Entropy H
2.040 b/sym
Huffman L
2.091 b/sym
Overhead L − H
0.051 b/sym
Fixed-length
3 b/sym
Total bits
23 vs 33
❯ H(p) ≤ L_Huffman < H(p) + 1  ·  Kraft: Σ 2^(−ℓᵢ) ≤ 1
Key idea
Try "aaaaaaab". The entropy is only 0.54 bits per symbol, but Huffman can't go below 1 bit per symbol, so it wastes almost half its output. That rounding loss is what arithmetic coding removes.
Concept 5

Arithmetic coding: fractional bits

Instead of one codeword per symbol, the whole message becomes a single interval inside [0, 1). Each symbol shrinks the current interval to its own slice, so the final width is Π p(xᵢ). Naming a binary point inside that interval takes about −log₂(width) = Σ surprise bits. That is the total information in the message, with at most 2 bits of overhead for the whole message rather than per symbol.
abracadabra
0.0000000step 0 · width 1.000e+01.0000000
a
b
r
c
d
0.0000000step 1 · width 4.545e-10.45454545
a
b
r
c
d
0.20661157step 2 · width 8.264e-20.28925620
a
b
r
c
d
0.25920361step 3 · width 1.503e-20.27422990
a
b
r
c
d
0.25920361step 4 · width 6.830e-30.26603374
a
b
r
c
d
Each row is the previous row's highlighted slice, zoomed to full width. Slice boundaries come from the cumulative distribution 0.00 · 0.45 · 0.64 · 0.82 · 0.91 · 1.00.
Σ surprise (4 sym)
7.19 bits
Arithmetic code
23 bits
Huffman
23 bits
Info, whole message
22.44 bits
code = 0.01000011110110101010100₂ ∈ [0.2650551279, 0.2650553031)
❯ width = Π p(xᵢ)  ⇒  bits ≤ ⌈−log₂ width⌉ + 1 = ⌈Σ I(xᵢ)⌉ + 1
Key idea
The decoder knows the same model p, so it can replay the zooms. At each step it checks which slice contains the code's number. This version uses a model fitted to the message itself. In practice the probabilities have to be sent too, or learned adaptively as symbols arrive. Pairing arithmetic coding with a strong model is how modern compressors, including those driven by language models, get close to the entropy.
Check yourself

Quiz

0 / 6 correct
Q1

You roll a fair 8-sided die. How much information does learning the result give you?

Q2

A coin lands heads 90% of the time. Its entropy is about…

Q3

Your model q is exactly the true distribution p. What is the KL divergence D(p‖q)?

Q4

Is KL divergence symmetric, i.e. D(p‖q) = D(q‖p)?

Q5

For p = (½, ¼, ⅛, ⅛), the Huffman code's average length is…

Q6

A symbol has p = 0.9. Why can arithmetic coding beat Huffman here?