Entropy (information theory)

In information theory, entropy tells you how much uncertainty or information is wrapped up in a random variable’s possible outcomes. It’s the average amount of information you’d need to describe which state the variable is in, given the probabilities of all its possible states. For a discrete random variable that can take values from a set according to a probability distribution, entropy is calculated as the sum over those values of the probability times the logarithm of one over that probability. The base of the logarithm changes the unit: base 2 gives bits (also called shannons), base e gives nats, and base 10 gives dits, bans, or hartleys. Another way to think of it is as the expected value of the variable’s self-information.

Claude Shannon introduced this concept in his 1948 paper “A Mathematical Theory of Communication,” and it’s often called Shannon entropy. He described a communication system with three parts: a data source, a channel, and a receiver. The core problem, as Shannon put it, is for the receiver to figure out what data the source produced based on the signal coming through the channel. He looked at ways to encode, compress, and transmit messages, and his source coding theorem proved that entropy sets an absolute mathematical limit on how much you can losslessly compress data from a source over a perfectly noiseless channel. He then extended this to noisy channels with his noisy-channel coding theorem.

Information entropy directly parallels the entropy used in statistical thermodynamics. The link appears when the random variable’s values represent the energies of microstates, making Gibbs’ formula for entropy formally identical to Shannon’s. This idea also shows up in other math fields like combinatorics and machine learning. The definition can be built from a set of axioms that say entropy should measure how informative a variable’s average outcome is. For a continuous random variable, differential entropy plays a similar role, and its definition generalizes the discrete one.

The basic insight of information theory is that a message’s informational value depends on how surprising it is. If a likely event happens, the message carries little information; if a very unlikely event happens, it carries a lot. For example, knowing that a specific number won’t win the lottery gives almost no information, since any chosen number almost certainly won’t win. But knowing that a particular number will win is highly informative because it’s a very low-probability event. The information content, or surprisal (also called self-information), of an event increases as its probability decreases. When the probability is close to 1, surprisal is low; when close to 0, it’s high. This is captured by the function that takes the logarithm of one over the probability, which gives zero surprise when the probability is 1. In fact, this is the only function that meets certain conditions. So the information of an event can be defined as the negative logarithm of its probability, or equivalently as the logarithm of one over the probability.

Entropy is the expected, or average, amount of information you get when you learn the outcome of a random trial. That’s why rolling a die has higher entropy than flipping a coin: each die outcome has a smaller probability (one-sixth) than each coin outcome (one-half). Take a coin with probability p of heads and 1-p of tails. Surprise is maximized when p equals 0.5, because neither outcome is expected over the other. In that case, a coin flip has an entropy of one bit. (Similarly, a three-sided die with equal probabilities gives about 1.58496 bits of information.) The minimum surprise happens when p is 0 (impossible) or 1 (certain), and entropy is zero bits. Zero entropy means no uncertainty, no freedom of choice, no information. Other values of p give entropies between zero and one bit.

Information theory helps find the smallest amount of information needed to send a message, which is useful for data compression. For instance, imagine transmitting sequences of the four characters A, B, C, and D over a binary channel. If all four are equally likely (25% each), the best you can do is use two bits per letter—say, A as 00, B as 01, C as 10, D as 11. But if the probabilities are unequal—say A occurs 70% of the time, B 26%, and C and D 2% each—you can use variable-length codes: A as 0, B as 10, C as 110, D as 111. Then 70% of the time you send just one bit, 26% of the time two bits, and only 4% of the time three bits. On average, fewer than two bits are needed because the entropy is lower, thanks to the high prevalence of A and B (together 96% of characters). The sum of probability-weighted log probabilities captures this effect.

English text, treated as a string of characters, has fairly low entropy—it’s pretty predictable. For example, you can be fairly sure that ‘e’ will appear far more often than ‘z’, and that the combination ‘qu’ will be much more common than any other combination with a ‘q’.