ISEGORIA / MATH ENCYCLOPEDIA
Information theory: uncertainty and codes
Entropy, noisy channels, and information distance.
Before you begin: Probability and logarithms
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Entropy
Tune a binary source. On the left each outcome is a block whose width is its probability and whose height is its surprise −log₂ p(x), so the total shaded area is the entropy, the average surprise. On the right, the entropy peaks at one bit for a fair coin.
Worked example. For p = 0.9, H = 0.9·log₂(1/0.9) + 0.1·log₂(10) ≈ 0.469 bits.
Watch out. Entropy measures uncertainty in a distribution, not the meaning of a message.
When is binary entropy maximal?
At p=1/2.
2. A noisy channel
Each bit is flipped with probability f. The mutual information is the output uncertainty H(Y) minus the part caused by noise, H(Y | X) = H(f). Drag the input probability: the gap is widest for a uniform input, and that maximum is the capacity 1 − H(f).
Worked example. The noiseless binary channel (f = 0) has one bit of capacity; at f = 0.1 the capacity is about 0.531 bits.
Watch out. Capacity is an asymptotic coding limit, not the success rate of one short message.
What happens at a flip probability of one half?
The output is independent of the input and mutual information is zero.
3. Divergence
Compare an observed two-outcome distribution P with a model Q. The left panel shows the two terms of the sum; one can be negative, yet the total is never negative. The right panel shows D(P ‖ Q) and the reverse D(Q ‖ P) as the model moves, both zero only at q = p.
Worked example. \(D_{\mathrm{KL}}(P\|Q)\) is zero only when the two distributions agree: for p = 0.7 and q = 0.5 it equals 0.7·log₂(1.4) + 0.3·log₂(0.6) ≈ 0.119 bits.
Watch out. It is not symmetric and is not a metric.
Why can a tiny Q(x) be costly?
Underestimating an event that occurs makes log(P/Q) large.