Information and entropy
Tonight's idea
Claude Shannon asked: how much information is in a message? If I think of a number from 1 to 16, you can find it with four yes/no questions, each halving what is left, because \(2^4 = 16\). One yes/no answer is a bit, and a choice among \(N\) equally likely things is worth \(\log_2 N\) bits (the number of halvings from \(N\) down to 1).
A coin that lands heads 90% of the time is less surprising than a fair one, so its flips should need fewer bits to write down. Shannon set the information in an outcome of probability \(p\) at \(\log_2(1/p)\); the average per symbol is the entropy:
\(\displaystyle H = \sum_i p_i \log_2 \frac{1}{p_i}\) bits per symbol.
A fair coin has \(H = 1\) bit; the 90% coin has \(H \approx 0.469\). One flip at a time still costs a whole bit. Code blocks of flips instead, giving the common heads-heavy blocks short codewords: for independent flips from a known 90% source the average can approach 0.469 bits per flip, about 469 per thousand, though some blocks must take longer. For this source, entropy is a lower bound on average lossless code length. Long block codes can get arbitrarily close, but a finite code need not hit it exactly.
Watch one: a Huffman code
Five letters have frequencies A 40%, B 30%, C 15%, D 10%, E 5%. A fixed 3-bit code costs 300 bits per 100 letters. Huffman's recipe: repeatedly merge the two least likely symbols. \(D + E = 15\%\); then C and DE make 30%; then B and CDE make 60%; then A joins. Label left edges 0 and right edges 1 and read codewords down from the root: A = 0, B = 10, C = 110, D = 1110, E = 1111.
No codeword starts another, so 0100110 splits only one way: A B A C. Average length \(0.4(1) + 0.3(2) + 0.15(3) + 0.1(4) + 0.05(4) = 2.05\) bits, so 205 per 100 letters. The entropy \(H \approx 2.009\) is a floor no lossless code can beat on average; this one-letter Huffman code sits 0.041 bits above it.
Your turn
- With twenty yes/no questions, how many equally likely possibilities can you tell apart? How many questions identify one of 52 cards for certain, and why isn't the answer \(\log_2 52\) exactly?
- Compute the entropy of a fair six-sided die, to three decimal places, and of a coin that lands heads 75% of the time. Which is more uncertain?
- A weather station reports sunny \(\tfrac12\), cloudy \(\tfrac14\), rain \(\tfrac18\), snow \(\tfrac18\). Build a Huffman code, then compute its average length and the entropy. Why do they agree exactly here when they did not in the example?
- Twelve coins. One of twelve coins is counterfeit, heavier or lighter; a balance scale has three outcomes per weighing. How many possibilities are there? Compare with the number of results of two weighings to show two cannot be enough.
Demos: mathdetours.com/demos/guess.html and mathdetours.com/demos/hamming.html.
Stretch: why no program can compress everything
(a) A company advertises a compressor that shrinks any file. Count the files of exactly \(n\) bits and those shorter than \(n\) bits: why does the pigeonhole principle sink the advertisement? (b) Generator A flips the 90% coin 1000 times; B flips it once and copies the result 1000 times. Both are heads 90% of the time at every position: whose output needs more storage? (c) How does the 469-bit average survive (a)?
Answers
- \(2^{20} = 1{,}048{,}576\). For 52 cards, \(\log_2 52 \approx 5.70\), so five questions (32 outcomes) are not enough and six (64) are. Questions come in whole numbers, so round up; the fraction means some branches of your question tree finish early.
- Die: \(\log_2 6 \approx 2.585\) bits. The 75% coin: \(0.75\log_2(4/3) + 0.25\log_2 4 \approx 0.311 + 0.5 = 0.811\) bits. The die is far more uncertain.
- Merge rain and snow (\(\tfrac14\)), then with cloudy (\(\tfrac12\)), then with sunny. Code: sunny 0, cloudy 10, rain 110, snow 111. Average length \(\tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75\), and the entropy is also 1.75. They agree because every probability is a power of \(\tfrac12\), so each ideal length \(\log_2(1/p)\) is a whole number and Huffman can hit it exactly.
- \(12 \times 2 = 24\) possibilities (which coin, heavy or light). Two weighings have \(3^2 = 9\) outcomes and \(9 \lt 24\), so some outcome would cover several possibilities. Three weighings give \(27 \ge 24\), so the bound allows it, and a strategy does exist. In bits: \(\log_2 24 \approx 4.58\), each weighing gives at most \(\log_2 3 \approx 1.58\), so at least three.
Stretch. (a) There are \(2^n\) files of length \(n\) and \(1 + 2 + \cdots + 2^{n-1} = 2^n - 1\) shorter files. A compressor that shrinks every \(n\)-bit file sends \(2^n\) inputs into \(2^n - 1\) outputs, so two inputs share an output and cannot both be recovered. (b) B has only two possible outputs, so one bit encodes the whole block; A has \(2^{1000}\) and averages about 469. Same frequencies, different dependence: entropy belongs to the source, not to the symbol counts. (c) It is an average, not a promise. Block coding gives the common heads-heavy blocks short codewords and the rare balanced ones long codewords, so it beats 1000 bits on average while some files grow. Compression works in practice because photos and text live in that small, common corner.