Information theory studies how uncertainty, data, and communication can be measured with mathematics. This cheat sheet helps students connect probability to ideas such as surprise, compression, and reliable message transmission. It is useful in applied math, computer science, statistics, and physics because many systems involve uncertain outcomes and noisy data.
The main goal is to quantify how much information is present, shared, lost, or transmitted.
Key Facts
- Self-information measures surprise with I(x) = -log2(P(x)), so rarer events carry more bits of information.
- Entropy measures average uncertainty with H(X) = -sum p(x) log2(p(x)) over all outcomes x.
- For n equally likely outcomes, entropy is H(X) = log2(n), so a fair 8-outcome variable has 3 bits of entropy.
- Conditional entropy measures remaining uncertainty after observing another variable with H(X|Y) = H(X,Y) - H(Y).
- Mutual information measures shared information with I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X).
- KL divergence compares two probability distributions with D_KL(P||Q) = sum p(x) log2(p(x)/q(x)), and it is always at least 0.
- Channel capacity is the maximum mutual information over input distributions, C = max I(X;Y), measured in bits per channel use.
- Changing the logarithm base changes the unit: base 2 gives bits, base e gives nats, and base 10 gives bans.
Vocabulary
- Entropy
- Entropy is the average amount of uncertainty or information in a random variable.
- Self-information
- Self-information is the information gained from one outcome, calculated as I(x) = -log2(P(x)).
- Mutual information
- Mutual information is the amount of information two variables share, or how much knowing one reduces uncertainty about the other.
- Conditional entropy
- Conditional entropy is the uncertainty left in one variable after another variable is known.
- KL divergence
- KL divergence measures how different one probability distribution is from another reference distribution.
- Channel capacity
- Channel capacity is the greatest reliable information rate a communication channel can support.
Common Mistakes to Avoid
- Using probability instead of log probability in entropy is wrong because entropy depends on p(x) log2(p(x)), not just p(x).
- Forgetting the negative sign in H(X) = -sum p(x) log2(p(x)) is wrong because log2(p(x)) is negative when 0 < p(x) < 1.
- Treating mutual information as always equal to entropy is wrong because I(X;Y) equals H(X) only when Y fully determines X.
- Assuming KL divergence is symmetric is wrong because D_KL(P||Q) usually does not equal D_KL(Q||P).
- Mixing logarithm bases without changing units is wrong because base 2 gives bits while base e gives nats.
Practice Questions
- 1 A fair coin has outcomes heads and tails. Calculate H(X) in bits.
- 2 An event has probability 1/8. Calculate its self-information I(x) in bits.
- 3 A source produces A with probability 1/2, B with probability 1/4, and C with probability 1/4. Calculate H(X) in bits.
- 4 If two variables have high mutual information, explain what that means about using one variable to predict the other.
Understanding Information Theory & Entropy
Entropy has a practical link to coding. A message made from common symbols can be stored using short binary codewords, while rare symbols can use longer codewords. This is the idea behind many compression methods.
A file containing repeated patterns, such as a simple black and white image, often shrinks well because its next parts are fairly predictable. A file made from random-looking measurements usually shrinks much less. Entropy gives a limit on the average number of binary digits needed per outcome when coding is efficient.
Real compression programs must include rules for decoding, so their final file size can be above this limit. They cannot reliably compress every possible file, since some files already have nearly no predictable structure left to remove.
Conditional uncertainty is useful when information arrives in stages. Suppose a weather forecast says rain is likely. The uncertainty about whether many students carry umbrellas may fall after hearing that forecast, even before seeing anyone outside.
The forecast does not determine every person's choice, but it changes the probabilities. Joint probability tables help track such relationships because they show how pairs of outcomes occur together. Shared information measures how much one observation reduces uncertainty about another.
It shows association, not necessarily cause. Ice cream sales and sunburn cases may share information because both rise on hot days. That pattern alone does not show that buying ice cream causes sunburn.
Comparing probability models matters whenever predictions guide decisions. A weather model might assign probabilities to sunny, cloudy, and rainy days, while actual observations produce a different pattern. Divergence measures the cost of treating one distribution as if it were another.
Its direction matters. Measuring the penalty for using model Q when reality follows model P is generally different from reversing those roles. This is important in statistics and machine learning, where a model is adjusted to match observed data.
A serious warning occurs when a model gives an outcome zero probability even though that outcome can happen. Such a model is overconfident, and the coding penalty for that missed outcome becomes unbounded in the ideal mathematical model.
A communication channel includes more than a wire or radio signal. It includes any process that turns an input message into a received output with possible errors. Capacity describes a theoretical ceiling for dependable communication when very long messages and carefully designed codes are allowed.
Error correction works by adding planned redundancy, which lets a receiver detect or repair some corrupted bits. More redundancy improves reliability but reduces the useful message rate. Noise level, signal strength, bandwidth, and the chosen input probabilities can all affect the result.
When studying these ideas, keep random variables separate from their individual outcomes. State what distribution is being used before calculating anything.
Check the logarithm unit, since mixing bits with other units causes mistakes. Remember that independent variables have no shared information, while a strong relationship can still leave uncertainty.