Information Theory and Entropy

⚡ Key Takeaways

Information theory quantifies information, uncertainty, and the limits of communication. Its central quantity, Shannon entropy $H(X) = -\sum p_i \log p_i$ , measures the average uncertainty (in bits) of a random variable. It governs data compression (source coding) and reliable transmission (channel coding). Founded by Claude Shannon in his 1948 paper A Mathematical Theory of Communication.

💡 The Core Insight

Information is the resolution of uncertainty. The amount of information in an event is inversely related to its probability: rare events are surprising and informative; certain events tell us nothing. Entropy is the expected surprise. Once you measure uncertainty in bits, the entire theory of compression and communication follows as a matter of counting.

DefinitionSelf-Information (Surprisal)

The self-information of an event $x$ with probability $p(x)$ is

1

\quad I(x) = \log_b \frac{1}{p(x)} = -\log_b p(x)

Derivation hint: Demand that information be (i) decreasing in probability, (ii) additive for independent events $I(x,y)=I(x)+I(y)$ , and (iii) continuous. Cauchy's functional equation forces a logarithm. The base $b$ fixes the unit: $b=2$ gives bits, $b=e$ gives nats, $b=10$ gives dits/hartleys. Symbol $p(x)$ is the probability mass of outcome $x$ .

DefinitionShannon Entropy

For a discrete random variable $X$ with alphabet $\mathcal{X}$ and pmf $p(x)$ , the entropy is the expected self-information:

2

\quad H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_2 p(x) = \mathbb{E}\!\left[\log_2 \tfrac{1}{p(X)}\right]

Derivation hint: Take the expectation $\mathbb{E}[I(X)]$ of equation [1] under $p$ . The convention $0\log 0 = 0$ is used, justified by $\lim_{p\to 0^+} p\log p = 0$ . Here $H(X)$ is measured in bits, $\mathcal{X}$ is the (finite or countable) set of outcomes, and the sum runs over all $x$ with $p(x)>0$ .

DefinitionJoint, Conditional Entropy, and Mutual Information

For two random variables $X, Y$ :

3

\quad H(X,Y) = -\sum_{x,y} p(x,y)\log_2 p(x,y)

Derivation hint: Apply equation [2] to the joint pmf $p(x,y)$ over the product alphabet $\mathcal{X}\times\mathcal{Y}$ .

4

\quad H(Y\mid X) = -\sum_{x,y} p(x,y)\log_2 p(y\mid x) = H(X,Y) - H(X)

Derivation hint: Average the entropy of $Y$ given $X=x$ over $x$ : $H(Y|X)=\sum_x p(x)H(Y|X=x)$ . The chain-rule form follows from $p(x,y)=p(x)p(y|x)$ and splitting the log.

5

\quad I(X;Y) = \sum_{x,y} p(x,y)\log_2 \frac{p(x,y)}{p(x)p(y)} = H(X) - H(X\mid Y)

Derivation hint: Mutual information is the KL divergence between the joint and the product of marginals; expand the log of the ratio and regroup using [2] and [4].

DefinitionKullback–Leibler Divergence

The relative entropy between distributions $p$ and $q$ on the same alphabet is

6

\quad D(p\,\|\,q) = \sum_{x} p(x)\log_2 \frac{p(x)}{q(x)}

Derivation hint: Measure the expected number of extra bits paid for coding samples from $p$ using a code optimal for $q$ ; this is $\mathbb{E}_p[\log\frac{1}{q}] - \mathbb{E}_p[\log\frac{1}{p}]$ . $D$ is not symmetric and is not a metric, but $D(p\|q)\ge 0$ with equality iff $p=q$ .

TheoremShannon's Source Coding Theorem

Let $X_1, X_2, \dots$ be i.i.d. samples from $X$ . For any $\varepsilon>0$ , there exists a lossless code with expected length per symbol $L$ satisfying $H(X) \le L < H(X)+\varepsilon$ for $n$ large enough, and no lossless code can achieve $L < H(X)$ . Entropy is the fundamental limit of lossless compression.

TheoremNoisy-Channel Coding Theorem

For a discrete memoryless channel with transition law $p(y|x)$ , define capacity

7

\quad C = \max_{p(x)} I(X;Y)

Derivation hint: Capacity is the largest mutual information achievable by optimizing the input distribution; the max exists because $I$ is continuous and concave in $p(x)$ over a compact simplex. For any rate $R < C$ , there exist codes of block length $n$ with error probability $\to 0$ as $n\to\infty$ . For $R > C$ , error probability is bounded away from zero.

ProofEntropy Bounds and Non-negativity of KL

We establish $0 \le H(X) \le \log_2 |\mathcal{X}|$ and $D(p\|q)\ge 0$ . 1. Non-negativity of $H$ . Each term $-p(x)\log_2 p(x)\ge 0$ since $0\le p(x)\le 1$ makes $\log_2 p(x)\le 0$ . Hence $H(X)\ge 0$ , with equality iff some $p(x)=1$ (a deterministic variable). 2. Gibbs' inequality (KL $\ge 0$ ). Use $\ln t \le t-1$ for $t>0$ . Then

8

\quad -D(p\|q)\ln 2 = \sum_x p(x)\ln\frac{q(x)}{p(x)} \le \sum_x p(x)\Big(\frac{q(x)}{p(x)}-1\Big) = \sum_x q(x) - \sum_x p(x) = 0

Derivation hint: Apply $\ln t \le t-1$ with $t = q(x)/p(x)$ , multiply by $p(x)\ge 0$ , and sum; both distributions normalize to 1. 3. Therefore $D(p\|q)\ge 0$ , with equality iff $q(x)/p(x)=1$ everywhere, i.e. $p=q$ . 4. Maximum entropy. Set $q$ to the uniform distribution $u(x)=1/|\mathcal{X}|$ . Then

9

\quad D(p\|u) = \sum_x p(x)\log_2\frac{p(x)}{1/|\mathcal{X}|} = \log_2|\mathcal{X}| - H(X) \ge 0

Derivation hint: Substitute $q=u$ into [6], split the logarithm, and recognize $-\sum p\log p = H(X)$ . Non-negativity from step 2 gives the bound. 5. Hence $H(X)\le \log_2|\mathcal{X}|$ , with equality iff $X$ is uniform. Uncertainty is maximized when all outcomes are equally likely. $\blacksquare$

∎

CS

Claude Shannon

1916–2001

An American mathematician and electrical engineer at Bell Labs, Shannon single-handedly founded information theory with his 1948 monograph. His earlier 1937 master's thesis showed that Boolean algebra could describe switching circuits—arguably the most influential master's thesis ever, birthing digital logic design. Shannon was famously playful: he built juggling machines, a mechanical mouse that solved mazes ("Theseus"), and rode a unicycle through Bell Labs corridors. He chose the word "entropy" on the advice of John von Neumann, who reportedly told him no one understands entropy, so he'd always win an argument.

🧠 Intuition

Think of entropy as the average number of yes/no questions needed to pin down an outcome using an optimal questioning strategy. If a horse race has 8 equally likely horses, you need 3 questions ("Is it in the top half?" etc.)—and $H = \log_2 8 = 3$ bits. If one horse is a near-certain favorite, you often guess right with one question, so the average drops below 3. The biased coin is the cleanest mental model. A fair coin gives 1 bit. A coin that lands heads 90% of the time is mostly predictable: most flips tell you little, so its entropy is only about 0.47 bits. A two-headed coin gives 0 bits—you learn nothing. Mutual information $I(X;Y)$ is the overlap of uncertainties: how much knowing $Y$ shaves off your uncertainty about $X$ . It is symmetric—learning about smoke tells you exactly as much about fire as vice versa.

Figure

Binary entropy function

H(p) = -p\log_2 p - (1-p)\log_2(1-p)

, peaking at

p=0.5

ExampleEntropy of a Biased Coin

Given: A coin lands heads with probability $p = 0.25$ , tails with $0.75$ .

Steps: 1. Apply equation [2]: $H = -p\log_2 p - (1-p)\log_2(1-p)$ . 2. $-0.25\log_2 0.25 = -0.25 \times (-2) = 0.5$ bits. 3. $-0.75\log_2 0.75 = -0.75 \times (-0.415) = 0.311$ bits. 4. Sum: $0.5 + 0.311 = 0.811$ bits.

\boxed{H(X) \approx 0.811 \text{ bits per flip}}

Interpretation: a long sequence of $n$ such flips can be compressed to roughly $0.811\,n$ bits, versus $n$ bits for naive storage—an 19% saving.

ExampleCapacity of a Binary Symmetric Channel

Given: A binary symmetric channel (BSC) flips each transmitted bit independently with probability $f = 0.1$ .

Steps: 1. Capacity of a BSC: $C = 1 - H(f)$ bits per channel use, where $H(f)$ is the binary entropy of the flip probability. 2. Compute $H(0.1) = -0.1\log_2 0.1 - 0.9\log_2 0.9$ . 3. $-0.1\log_2 0.1 = -0.1\times(-3.322) = 0.332$ bits. 4. $-0.9\log_2 0.9 = -0.9\times(-0.152) = 0.137$ bits. 5. $H(0.1) = 0.469$ bits, so $C = 1 - 0.469 = 0.531$ .

\boxed{C \approx 0.531 \text{ bits per channel use}}

Interpretation: despite 10% noise, you can transmit reliably (with vanishing error) at up to about 0.53 information bits per physical bit sent, using a good error-correcting code.

⚠️ Common mistake

Entropy is not disorder, and high entropy is not "bad." In information theory, entropy measures uncertainty about which message will occur, not physical messiness. A maximally compressed file looks like random noise precisely because it has maximal entropy—every bit is informative.

Information is not the same as meaning. Shannon's theory is deliberately semantic-free: the string "asdfjkl" and a Shakespeare sonnet of equal length and letter statistics carry the same Shannon information. Meaning lives outside the theory.

Bits-the-unit vs. bits-the-storage. A source with entropy 0.8 bits/symbol still requires whole physical bits to store one symbol; the entropy is the amortized limit over long sequences, not a per-symbol storage size.

Counterexample

"More outcomes always means more entropy." False. Consider $X$ over 1000 outcomes where one outcome has probability $0.999$ and the remaining 999 share $0.001$ . Its entropy is about $0.011$ bits—far less than a fair coin's 1 bit over only 2 outcomes. Entropy depends on the shape of the distribution, not the alphabet size alone. Only the uniform distribution attains the maximum $\log_2|\mathcal{X}|$ .

connection

Information theory sits at a crossroads. Its entropy formula is mathematically identical (up to Boltzmann's constant) to the Statistical Mechanics entropy $S = -k_B\sum p_i\ln p_i$ , linking information to thermodynamics via Maxwell's Demon and Landauer's principle. The KL divergence is the workhorse of Bayesian Inference and underlies Maximum Likelihood Estimation, since maximizing likelihood minimizes $D(p_{\text{data}}\|p_{\text{model}})$ . Mutual information is a central objective in Machine Learning, from feature selection to the information bottleneck. The maximum-entropy principle connects to Probability Theory as a least-biased way to assign distributions under constraints, recovering the Gaussian and exponential families.

🔬 Where this appears

⏳ History

- 1924–1928: Harry Nyquist and Ralph Hartley at Bell Labs quantify "information" via

\log

of the number of possible messages, anticipating the logarithmic measure.

- 1940–1945: Shannon works on cryptography and fire-control during WWII; his classified report A Mathematical Theory of Cryptography (1945) contains early entropy ideas.

- 1948: Shannon publishes A Mathematical Theory of Communication in the Bell System Technical Journal, defining entropy, channel capacity, and the coding theorems.

- 1949: The paper is republished as a book with Warren Weaver's accessible introduction; Shannon also proves the sampling theorem's role and analyzes the one-time pad.

- 1951: Shannon estimates the entropy of printed English at roughly 1 bit per letter using human prediction experiments.

- 1951: Solomon Kullback and Richard Leibler introduce relative entropy (KL divergence).

- 1957: Edwin Jaynes formulates the maximum entropy principle, recasting statistical mechanics as inference.

- 1961: Rolf Landauer establishes that erasing one bit dissipates at least

k_B T\ln 2

of heat, physically grounding information.

- 1993–2008: Practical capacity-approaching codes arrive—Turbo codes (Berrou et al., 1993) and the rediscovery of LDPC codes (Gallager 1962; MacKay 1996)—finally realizing Shannon's 1948 promise.

open-problem

Several deep issues remain active. Differential entropy $h(X) = -\int f(x)\log f(x)\,dx$ for continuous variables can be negative and is not coordinate-invariant, requiring care; the right invariant object is relative entropy or mutual information. Finite-blocklength information theory (Polyanskiy–Poor–Verdú, 2010) sharpens Shannon's asymptotic limits for the short codes used in real low-latency systems—an ongoing refinement. The information bottleneck as a theory of deep learning generalization is debated. In the quantum realm, computing capacities of quantum channels exhibits superadditivity and remains only partially understood. Finally, algorithmic (Kolmogorov) complexity offers an alternative, individual-object notion of information that is provably uncomputable, sitting uneasily alongside Shannon's ensemble-based theory.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also