Information Theory

A rare symbol tells you more than a common one. Price each symbol at minus log2 of its probability, weigh the prices by how often they are paid: the average is the entropy, the bits a source is worth.

Code words that decode without separators are paths in a tree. Kraft's inequality says which lengths fit, and the cost of any such code sits above the entropy; Shannon's lengths come within a bit.

Count the symbols, heap them, merge the two lightest until one root remains. The paths down the tree are the code words: short for common symbols, long for rare ones, never one a prefix of another.

Give each symbol a slice of the unit interval, keep each symbol's slice of what is left, and send the shortest fraction inside: the message costs its information plus two bits, never a bit a symbol.

A code built for the wrong distribution charges the wrong prices. The bits it wastes per symbol is the KL divergence: cross-entropy minus entropy, never negative, zero only when the model is right.

How far a joint table is from the product of its margins: the bits one variable tells you about another. Zero when they are independent, and the overlap of their entropies otherwise.

A wire that flips bits at random still carries information, and how much has a formula: the mutual information of input and output at its peak, 1 minus H(f) for a wire that flips with probability f.

Three parity bits guard four data bits, each over a different group of positions. Any single flip fails exactly the groups that spell its position, so the receiver can put it back without asking.