Information Theory and Entropy

Information theory quantifies information, uncertainty, and the limits of communication. Its central quantity, Shannon entropy

H (X) = - \sum p_{i} lo g 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.

Information theory is the mathematical study of the storage, transmission, and quantification of information. At its heart lies entropy, a number measuring the average unpredictability of a random source: a fair coin carries 1 bit per toss, while a biased coin carries less. Entropy sets a hard floor on how much data can be compressed without loss and—via channel capacity—a hard ceiling on how fast information can flow through a noisy medium. The surprising fact is that these two seemingly different limits emerge from a single coherent framework, and that reliable communication over noise is possible at all below capacity, with error probability driven arbitrarily close to zero. This unification, achieved in one 1948 paper, underpins every modern digital technology.

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.

Formal Statement

Self-Information (Surprisal)

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

I (x) = lo g_{b} \frac{1}{p ( x )} = - lo g_{b} p (x)

⟳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$ .

Shannon Entropy

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

H (X) = - x \in X \sum p (x) lo g_{2} p (x) = E [lo g_{2} \frac{1}{p ( X )}]

⟳Take the expectation

E [I (X)]

of equation [1] under

p

. The convention

0 lo g 0 = 0

is used, justified by

lim_{p \to 0^{+}} p lo g p = 0

Here $H (X)$ is measured in bits, $X$ is the (finite or countable) set of outcomes, and the sum runs over all $x$ with $p (x) > 0$ .

Joint, Conditional Entropy, and Mutual Information

For two random variables $X, Y$ :

H (X, Y) = - x, y \sum p (x, y) lo g_{2} p (x, y)

⟳Apply equation [2] to the joint pmf

p (x, y)

over the product alphabet

X \times Y

H (Y ∣ X) = - x, y \sum p (x, y) lo g_{2} p (y ∣ x) = H (X, Y) - H (X)

⟳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.

I (X; Y) = x, y \sum p (x, y) lo g_{2} \frac{p ( x , y )}{p ( x ) p ( y )} = H (X) - H (X ∣ Y)

⟳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].

Kullback–Leibler Divergence

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

D (p ∥ q) = x \sum p (x) lo g_{2} \frac{p ( x )}{q ( x )}

⟳Measure the expected number of extra bits paid for coding samples from

p

using a code optimal for

q

; this is

E_{p} [lo g \frac{1}{q}] - E_{p} [lo g \frac{1}{p}]

D

is not symmetric and is not a metric, but

D (p ∥ q) \geq 0

with equality iff

p = q

Shannon's Source Coding Theorem

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

Noisy-Channel Coding Theorem

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

C = p (x) max I (X; Y)

⟳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.

Why It Holds / Derivation

Entropy Bounds and Non-negativity of KL

We establish $0 \leq H (X) \leq lo g_{2} ∣ X ∣$ and $D (p ∥ q) \geq 0$ .

Non-negativity of $H$ . Each term $- p (x) lo g_{2} p (x) \geq 0$ since $0 \leq p (x) \leq 1$ makes $lo g_{2} p (x) \leq 0$ . Hence $H (X) \geq 0$ , with equality iff some $p (x) = 1$ (a deterministic variable).

Gibbs' inequality (KL $\geq 0$ ). Use $ln t \leq t - 1$ for $t > 0$ . Then

- D (p ∥ q) ln 2 = x \sum p (x) ln \frac{q ( x )}{p ( x )} \leq x \sum p (x) (\frac{q ( x )}{p ( x )} - 1) = x \sum q (x) - x \sum p (x) = 0

⟳Apply

ln t \leq t - 1

with

t = q (x) / p (x)

, multiply by

p (x) \geq 0

, and sum; both distributions normalize to 1.

Therefore $D (p ∥ q) \geq 0$ , with equality iff $q (x) / p (x) = 1$ everywhere, i.e. $p = q$ .

Maximum entropy. Set $q$ to the uniform distribution $u (x) = 1/∣ X ∣$ . Then

D (p ∥ u) = x \sum p (x) lo g_{2} \frac{p ( x )}{1/∣ X ∣} = lo g_{2} ∣ X ∣ - H (X) \geq 0

⟳Substitute

q = u

into [6], split the logarithm, and recognize

- \sum p lo g p = H (X)

. Non-negativity from step 2 gives the bound.

Hence $H (X) \leq lo g_{2} ∣ X ∣$ , with equality iff $X$ is uniform. Uncertainty is maximized when all outcomes are equally likely. $■$

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.

Building 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 = lo g_{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.

Binary entropy function $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$, peaking at $p=0.5$

Worked Examples

Entropy of a Biased Coin

Given: A coin lands heads with probability

p = 0.25

, tails with

0.75

. Steps:

Apply equation [2]: $H = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ .
$- 0.25 lo g_{2} 0.25 = - 0.25 \times (- 2) = 0.5$ bits.
$- 0.75 lo g_{2} 0.75 = - 0.75 \times (- 0.415) = 0.311$ bits.
Sum: $0.5 + 0.311 = 0.811$ bits.

H (X) \approx 0.811 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.

Capacity of a Binary Symmetric Channel

Given: A binary symmetric channel (BSC) flips each transmitted bit independently with probability

f = 0.1

. Steps:

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

C \approx 0.531 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 Misconceptions

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. "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

lo g_{2} ∣ X ∣

Connections

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_{data} ∥ p_{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.

Real-World Applications

Data compression. ZIP, gzip, and PNG use entropy coders (Huffman, arithmetic coding) approaching the entropy limit; JPEG and MP3 combine this with lossy quantization guided by rate-distortion theory.
Error-correcting codes. Reed–Solomon codes on CDs/DVDs/QR codes, LDPC codes in Wi-Fi (802.11n) and 5G, and Turbo codes in deep-space probes all operate near Shannon capacity.
Cryptography. Shannon's notion of perfect secrecy (the one-time pad) and entropy as a measure of key unpredictability/randomness underpin secure key generation.
Machine learning. Cross-entropy loss trains nearly every neural network classifier; decision trees split on information gain (mutual information).
Genomics & neuroscience. Mutual information quantifies neural coding efficiency and identifies co-evolving residues or regulatory motifs in DNA sequences.
Communication systems. The Shannon–Hartley theorem $C = B lo g_{2} (1 + SNR)$ dictates modem, DSL, fiber, and cellular data-rate design.
Quantum information. Von Neumann entropy generalizes Shannon entropy to density matrices, grounding quantum computing and entanglement measures.

Historical Development

1924–1928: Harry Nyquist and Ralph Hartley at Bell Labs quantify "information" via $lo g$ 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.

Subtleties & Limits

Several deep issues remain active. Differential entropy $h (X) = - \int f (x) lo g f (x) d x$ 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.