The Central Idea
An uncertain variable carries information because we do not yet know which outcome will occur.
When an outcome is learned, some uncertainty disappears.
Information theory gives us numerical tools for measuring:
- how surprising one outcome is;
- how uncertain a probability distribution is overall;
- how much uncertainty remains after observing another variable;
- how much one variable tells us about another.
Information and Surprise
Rare events generally carry more information than common events.
Learning that a nearly certain event occurred tells us little.
Learning that a very unlikely event occurred is much more surprising.
Self-Information
The self-information of an event with probability \(p\) is
\[ \boxed{I(p)=-\log p}. \]The logarithm base determines the unit of information.
Bits
When logarithms use base \(2\),
\[ \boxed{I(p)=-\log_2 p}, \]information is measured in bits.
One bit corresponds to the information gained from resolving one equally likely binary choice.
Nats
When the natural logarithm is used,
\[ \boxed{I(p)=-\ln p}, \]information is measured in nats.
Rare Events Carry More Self-Information
Compare probabilities
\[ p=0.5 \]and
\[ p=0.125. \]In bits,
\[ I(0.5)=-\log_2(0.5)=1 \]while
\[ I(0.125)=-\log_2(0.125)=3. \]The rarer event carries more information when it occurs.
Certain Events Carry No New Information
If
\[ p=1, \]then
\[ I(1)=-\log_2(1)=0. \]An event that was already certain produces no surprise.
Why the Logarithm Appears
Independent probabilities multiply, while information adds.
If independent events A and B have probabilities \(p_A\) and \(p_B\),
\[ P(A\cap B)=p_Ap_B. \]Their information is
\[ -\log(p_Ap_B) \] \[ =-\log p_A-\log p_B. \]The logarithm converts multiplication of probabilities into addition of information.
Entropy
Entropy is the expected self-information of a random variable.
For a discrete random variable \(X\),
\[ \boxed{ H(X) = -\sum_x P(X=x)\log P(X=x) }. \]With base-2 logarithms, entropy is measured in bits.
Entropy Is an Average Uncertainty Measure
Self-information applies to one realized outcome.
Entropy averages self-information across all possible outcomes.
It therefore describes uncertainty before we know which outcome will occur.
Example: Fair Coin
For a fair coin,
\[ P(H)=0.5,\qquad P(T)=0.5. \]Therefore,
\[ H(X) = -0.5\log_2(0.5) -0.5\log_2(0.5). \] \[ =0.5+0.5. \] \[ \boxed{H(X)=1\text{ bit}}. \]Example: Biased Coin
Suppose
\[ P(H)=0.9,\qquad P(T)=0.1. \]Then
\[ H(X) = -0.9\log_2(0.9) -0.1\log_2(0.1). \]Numerically,
\[ \boxed{H(X)\approx0.469\text{ bits}}. \]The biased coin is less uncertain than the fair coin.
Maximum Entropy for Two Outcomes
A binary variable has maximum entropy when its two outcomes are equally likely.
\[ P(A)=P(B)=0.5. \]Then
\[ \boxed{H=1\text{ bit}}. \]Minimum Entropy
If one outcome is certain, entropy is zero.
\[ \boxed{H=0}. \]There is no uncertainty left to resolve.
Uniform Distributions Maximize Entropy
For \(n\) equally likely outcomes,
\[ P(X=x_i)=\frac{1}{n}. \]Entropy is
\[ H(X) = -n\left(\frac{1}{n}\log_2\frac{1}{n}\right). \]Therefore,
\[ \boxed{H(X)=\log_2 n}. \]Example: Four Equally Likely Outcomes
If there are four equally likely outcomes,
\[ H(X)=\log_2 4. \] \[ \boxed{H(X)=2\text{ bits}}. \]Two binary questions can distinguish among four equally likely possibilities.
Entropy Depends on the Distribution, Not the Labels
Entropy depends on the probabilities assigned to outcomes.
Renaming the outcomes does not change entropy.
What matters is how probability is distributed across the possibilities.
Entropy and Prediction
Low entropy means one or a few outcomes dominate the distribution.
High entropy means probability is spread more evenly.
A lower-entropy variable is generally easier to predict before observing additional information.
Joint Entropy
For two discrete random variables \(X\) and \(Y\), the joint entropy is
\[ \boxed{ H(X,Y) = -\sum_x\sum_y P(x,y)\log P(x,y) }. \]It measures uncertainty in the pair \((X,Y)\).
Conditional Entropy
Conditional entropy measures how much uncertainty remains about one variable after another variable is known.
\[ \boxed{ H(X\mid Y) = -\sum_y P(y) \sum_x P(x\mid y)\log P(x\mid y) }. \]Interpretation of Conditional Entropy
If \(Y\) tells us a great deal about \(X\), then
\[ H(X\mid Y) \]is small.
If knowing \(Y\) tells us nothing about \(X\), then conditional entropy remains as large as the original entropy.
Chain Rule for Entropy
Joint entropy can be decomposed:
\[ \boxed{ H(X,Y)=H(Y)+H(X\mid Y) }. \]Equivalently,
\[ \boxed{ H(X,Y)=H(X)+H(Y\mid X) }. \]The total uncertainty in two variables can be separated into uncertainty in one plus remaining uncertainty in the other.
Mutual Information
Mutual information measures how much knowing one variable reduces uncertainty about another.
\[ \boxed{ I(X;Y)=H(X)-H(X\mid Y) }. \]Symmetrically,
\[ \boxed{ I(X;Y)=H(Y)-H(Y\mid X) }. \]Another Formula for Mutual Information
Mutual information can also be written
\[ \boxed{ I(X;Y) = \sum_x\sum_y P(x,y) \log \frac{P(x,y)}{P(x)P(y)} }. \]This compares the observed joint distribution with what would occur under independence.
Independent Variables Have Zero Mutual Information
If \(X\) and \(Y\) are independent,
\[ P(x,y)=P(x)P(y). \]Therefore,
\[ \frac{P(x,y)}{P(x)P(y)}=1, \]and
\[ \boxed{I(X;Y)=0}. \]Perfectly Informative Variables
If knowing \(Y\) determines \(X\) completely, then
\[ H(X\mid Y)=0. \]Therefore,
\[ I(X;Y)=H(X). \]The observation removes all uncertainty about \(X\).
Information Gain
Information gain is often described as the reduction in entropy produced by an observation or partition.
\[ \boxed{ \text{Information Gain} = H(\text{before}) - H(\text{after}) }. \]This is closely related to mutual information.
Example: Perfectly Revealing Signal
Suppose a fair binary state has entropy
\[ H(X)=1\text{ bit}. \]A perfect signal reveals the state exactly, so
\[ H(X\mid Y)=0. \]Therefore,
\[ I(X;Y)=1-0 \] \[ \boxed{1\text{ bit}}. \]Example: Useless Signal
Suppose the same binary state has entropy
\[ H(X)=1. \]If the signal is independent of the state,
\[ H(X\mid Y)=1. \]Therefore,
\[ I(X;Y)=1-1 \] \[ \boxed{0}. \]Entropy and Value of Information Are Different
Entropy measures uncertainty.
Value of information measures decision improvement.
A signal can remove substantial entropy while having little decision value if the optimal action does not change.
Conversely, a small amount of information near a decision threshold can be economically valuable.
More Information Does Not Automatically Mean More Value
Information theory measures statistical dependence and uncertainty reduction.
Decision theory also cares about:
- available actions;
- payoffs;
- losses;
- timing;
- cost of obtaining information.
Information content and decision value are related but distinct.
Entropy and Coding
Entropy has a fundamental connection to data compression.
More probable symbols can be represented using shorter codewords, while rare symbols generally require longer codewords.
Entropy gives a lower-bound benchmark for average code length under idealized lossless coding assumptions.
Expected Code Length
If symbol \(i\) has probability \(p_i\) and codeword length \(\ell_i\), the expected code length is
\[ \boxed{ E[L]=\sum_i p_i\ell_i }. \]Efficient codes assign shorter codewords to more probable symbols.
Binary Questions and Information
Bits can be interpreted through yes-or-no questions.
If there are eight equally likely possibilities,
\[ H=\log_2 8=3. \]In an ideal balanced search, three binary answers are enough to identify one of eight possibilities.
Entropy and Decision Trees
Decision trees in machine learning often choose splits that reduce uncertainty about a target variable.
A split can be evaluated by comparing entropy before and after the split.
Larger entropy reduction means the split creates more information about the target.
Weighted Entropy after a Split
Suppose a dataset is divided into groups \(G_1,\ldots,G_k\).
The post-split entropy is often computed as
\[ \boxed{ \sum_{j=1}^{k} P(G_j)H(Y\mid G_j) }. \]Information gain is the original entropy minus this weighted remainder.
Example: Complete Separation
Suppose a binary target initially has entropy \(1\) bit.
A split produces two groups, each containing only one class.
Each group's entropy is
\[ 0. \]Therefore post-split entropy is \(0\), and information gain is
\[ \boxed{1\text{ bit}}. \]Example: No Separation
Suppose each child group has exactly the same class proportions as the original dataset.
Then the weighted post-split entropy equals the original entropy.
Information gain is
\[ \boxed{0}. \]Cross-Entropy
Cross-entropy measures how well one probability distribution \(q\) represents outcomes generated according to another distribution \(p\).
\[ \boxed{ H(p,q) = -\sum_x p(x)\log q(x) }. \]It appears frequently in statistics, coding, and machine learning.
Cross-Entropy Penalizes Confident Wrong Predictions
If an event occurs and a model assigned that event very small probability, then
\[ -\log q(x) \]becomes large.
This means confident incorrect probability assignments can receive large loss.
Entropy and Log Loss
For a realized outcome \(x\), logarithmic loss is
\[ \boxed{ L(q,x)=-\log q(x) }. \]The expected log loss under the true distribution \(p\) is cross-entropy.
This connects information theory directly to loss functions.
Kullback-Leibler Divergence
The Kullback-Leibler divergence from distribution \(q\) to distribution \(p\) is
\[ \boxed{ D_{\mathrm{KL}}(p\|q) = \sum_x p(x) \log \frac{p(x)}{q(x)} }. \]It measures how much additional log-loss is incurred when \(q\) is used in place of the true distribution \(p\).
Cross-Entropy Decomposition
Cross-entropy satisfies
\[ \boxed{ H(p,q) = H(p) + D_{\mathrm{KL}}(p\|q) }. \]The cross-entropy equals unavoidable uncertainty plus the penalty for using the wrong probability model.
KL Divergence Is Nonnegative
Under standard conditions,
\[ \boxed{ D_{\mathrm{KL}}(p\|q)\ge0. } \]Equality occurs when the distributions agree on the relevant outcomes.
KL Divergence Is Not an Ordinary Distance
KL divergence is useful for comparing distributions, but it is not a metric.
In general,
\[ D_{\mathrm{KL}}(p\|q) \ne D_{\mathrm{KL}}(q\|p). \]It is directional.
Entropy in Continuous Models
Continuous random variables use a related quantity called differential entropy.
For density \(f(x)\),
\[ h(X) = -\int f(x)\log f(x)\,dx. \]Differential entropy behaves differently from discrete entropy and can even be negative, so it should not be interpreted identically.
Information and Bayesian Updating
A Bayesian update changes a prior distribution into a posterior distribution after observing evidence.
Information measures can quantify how much the evidence changes the distribution or reduces uncertainty.
This provides another bridge between Bayesian reasoning and information theory.
Entropy Is Not Disorder in Every Context
The word entropy is used in several fields.
In information theory, entropy is specifically a function of a probability distribution.
Informal phrases such as "disorder" can sometimes be suggestive, but the mathematical definition should remain primary.
Common Error: Forgetting the Negative Sign
Since probabilities lie between \(0\) and \(1\),
\[ \log p\le0. \]The negative sign makes self-information and entropy nonnegative in the ordinary discrete setting.
Common Error: Mixing Logarithm Bases
Base \(2\) produces bits.
Base \(e\) produces nats.
Different bases scale the numerical value, so a calculation should use one base consistently.
Common Error: Treating Entropy as the Number of Outcomes
Two variables can have the same number of possible outcomes and different entropy.
What matters is the probability distribution over those outcomes.
Common Error: Assuming More Outcomes Means More Entropy
More possible outcomes can increase maximum possible entropy, but actual entropy may remain low if nearly all probability is concentrated on one outcome.
Common Error: Confusing Mutual Information with Correlation
Correlation measures a particular kind of association, especially linear association for numerical variables.
Mutual information can detect more general statistical dependence.
The two quantities are related but not interchangeable.
Common Error: Equating Information Gain with Economic Value
A signal can have high statistical information content but low economic or strategic value.
Decision value depends on how the information changes actions and consequences.
A Reliable Procedure for Computing Entropy
- List all possible outcomes.
- Assign a valid probability to each outcome.
- Choose a logarithm base and use it consistently.
- Compute \(p_i\log p_i\) for each positive-probability outcome.
- Add the terms.
- Apply the negative sign.
- Interpret the result as average uncertainty before observing the outcome.
A Reliable Procedure for Mutual Information
- Compute the original entropy \(H(X)\).
- Determine the conditional distributions of \(X\) given \(Y\).
- Compute the conditional entropy \(H(X\mid Y)\).
- Subtract:
The result measures how much uncertainty about \(X\) is removed by knowing \(Y\).
Practice 1: Self-Information
Find the self-information in bits of an event with probability
\[ p=\frac{1}{4}. \]Practice 2: Certain Event
Find the self-information of an event with probability \(1\).
Practice 3: Fair Binary Entropy
A binary variable has probabilities
\[ 0.5,\qquad0.5. \]Find its entropy in bits.
Practice 4: Four Equal Outcomes
A variable has four equally likely outcomes.
Find its entropy in bits.
Practice 5: Conditional Entropy
Suppose
\[ H(X)=2 \]bits and observing \(Y\) leaves
\[ H(X\mid Y)=0.75 \]bits.
Find \(I(X;Y)\).
Practice 6: Independent Variables
If \(X\) and \(Y\) are independent, what is
\[ I(X;Y)? \]Practice 7: Perfect Information
Suppose
\[ H(X)=1.5 \]bits and \(Y\) determines \(X\) exactly.
Find \(H(X\mid Y)\) and \(I(X;Y)\).
Practice 8: Information Gain
A classification problem has entropy \(0.9\) bits before a split and weighted entropy \(0.4\) bits after the split.
Find the information gain.
Practice 9: Expected Code Length
Two symbols have probabilities \(0.75\) and \(0.25\), with codeword lengths \(1\) and \(3\).
Find the expected code length.
Practice 10: Information versus Decision Value
A signal greatly reduces uncertainty about a state, but the same action is optimal regardless of the signal.
Does the signal necessarily have high decision value?
Practice Answers
Practice 1
\[ I(p) = -\log_2\left(\frac14\right) \] \[ =\boxed{2\text{ bits}}. \]Practice 2
\[ I(1)=-\log_2(1)=\boxed{0}. \]Practice 3
\[ H = -0.5\log_2(0.5) -0.5\log_2(0.5) \] \[ =\boxed{1\text{ bit}}. \]Practice 4
\[ H=\log_2 4=\boxed{2\text{ bits}}. \]Practice 5
\[ I(X;Y) = H(X)-H(X\mid Y) \] \[ =2-0.75 \] \[ \boxed{1.25\text{ bits}}. \]Practice 6
\[ \boxed{I(X;Y)=0}. \]Practice 7
Since \(Y\) determines \(X\),
\[ H(X\mid Y)=\boxed{0}. \]Therefore,
\[ I(X;Y)=1.5-0 \] \[ \boxed{1.5\text{ bits}}. \]Practice 8
\[ 0.9-0.4 \] \[ \boxed{0.5\text{ bits}}. \]Practice 9
\[ E[L] = 0.75(1)+0.25(3) \] \[ =0.75+0.75 \] \[ \boxed{1.5\text{ bits per symbol}}. \]Practice 10
No. The signal can have high information content but low or zero decision value if it does not change the optimal action.
What to Remember
Entropy and information provide a mathematical language for uncertainty and uncertainty reduction.
- Self-information measures the surprise of one outcome.
- Rare events carry more self-information than common events.
- Entropy is expected self-information.
- Uniform distributions maximize entropy among fixed finite outcome sets.
- Conditional entropy measures uncertainty remaining after an observation.
- Mutual information measures how much one variable tells us about another.
- Independent variables have zero mutual information.
- Information gain is a reduction in entropy.
- Cross-entropy connects probability forecasts to logarithmic loss.
- Information content and decision value are related but not identical.
The most important conceptual distinction is: entropy measures uncertainty, while information measures how much of that uncertainty is removed.
Where We Go Next
Entropy quantifies uncertainty and information content. These ideas become operational when information must be represented and transmitted efficiently.
The next lesson, Coding and Compression, develops the mathematical relationship between symbol probabilities, codeword lengths, redundancy, and efficient representation.