Glossary

The unit of information from using base-2 logarithms — one bit is the information in a single fair coin flip.

The largest number of bits per use a channel can carry reliably, found by choosing the best possible input distribution.

The specific string of symbols a source code assigns to one outcome.

A function whose chord between any two points lies on or below the curve.

How much uncertainty about X remains, on average, once Y is known.

A function whose chord between any two points lies on or above the curve.

The average number of bits it costs to code outcomes drawn from the true distribution P, using a code built for a different distribution Q.

The continuous-variable analogue of entropy — unlike ordinary entropy it can be negative, since it isn't literally a count of bits.

The average self-information of a random variable — how uncertain its outcome is, in bits, before it's revealed.

The number of positions where two equal-length bit-strings disagree.

An algorithm that builds the shortest possible prefix code for a source, by repeatedly merging the two least-probable symbols.

For a convex function g, E[g(X)] is at least g(E[X]); the inequality reverses for concave g.

The entropy of a pair of random variables treated as one combined outcome.

The exact condition on a set of proposed codeword lengths that tells you whether a prefix code with those lengths can actually exist.

A random process where the next state depends only on the current state, not on how it was reached.

How many bits learning one variable's value tells you about another — the shared information between them.

A code where no codeword is the beginning of another, so a decoder always knows the instant a codeword is complete.

The fewest bits per source symbol needed to reconstruct it within a given amount of allowed error (distortion).

A measure of how different one probability distribution is from another, never negative and zero only when they match.

How surprising a single outcome is, in bits — rarer outcomes carry more.

The long-run probability split across states that a Markov chain settles into, unchanged by one more step.

A table of probabilities for moving from each state to each other state in one step of a Markov chain.

The (relatively small) set of length-n sequences a source is overwhelmingly likely to actually produce, each occurring with probability close to 2^{-nH(X)}.