🔬 Scientist
Pure mathematics — no exam syllabus
Information Theory — The Mathematics of Communication
Information theory answers two fundamental questions: what is information, and how much can we communicate reliably? Claude Shannon, in his 1948 paper "A Mathematical Theory of Communication," invented the entire field — defining entropy, channel capacity, and the limits of data compression and error correction. His work made the digital age possible: every time you zip a file, stream a video, or send a text, Shannon's mathematics is at work.
"Information is the resolution of uncertainty."
— Claude Shannon
Part 1
📊 Entropy — Measuring Uncertainty
The Birth of Information
Shannon's Great Question: What Is Information?
Before Shannon, nobody knew how to measure information. Shannon realized that information isn't about meaning — it's about uncertainty. A message you can predict (like "the sun will rise tomorrow") carries little information. A message that surprises you (like "it's snowing in the Sahara") carries lots. The self-information of an event with probability p is h(p) = −log₂(p) bits. A fair coin flip (p=1/2) gives 1 bit. A sure thing (p=1) gives 0 bits. The entropy H(X) of a random variable is the average self-information: H(X) = −Σ p(x) log₂ p(x). For a fair coin, H = 1 bit. For a biased coin (p=0.9), H = −0.9·log₂(0.9) − 0.1·log₂(0.1) ≈ 0.47 bits — less uncertainty, less information. Entropy is the fundamental limit on lossless compression: you cannot compress data to fewer bits than its entropy.
Information is not about meaning — it's about surprise. The more unpredictable something is, the more information it carries.
Properties of Entropy
Entropy is always non-negative, maximized by the uniform distribution, and additive for independent events. For a distribution over n outcomes with probabilities p₁, p₂, ..., pₙ: H ≤ log₂(n), with equality iff all pᵢ = 1/n. Joint entropy H(X,Y) extends the definition to pairs. Conditional entropy H(Y|X) = H(X,Y) − H(X) measures the remaining uncertainty about Y after knowing X.
A coin comes up Heads with probability p. The entropy is H = −p·log₂(p) − (1-p)·log₂(1-p).
• p = 0.5: H = 1 bit (maximum uncertainty)
• p = 0.9: H ≈ 0.47 bits
• p = 0.99: H ≈ 0.08 bits
• p = 0 or 1: H = 0 bits (no uncertainty)
This function is called the binary entropy function H₂(p). It's symmetric around p=0.5 and concave — it peaks at maximum uncertainty and drops to zero at certainty.
Part 2
🗜️ Data Compression — The Source Coding Theorem
The Ultimate Limit
Shannon's Source Coding Theorem — You Can't Beat Entropy
Shannon's source coding theorem (or noiseless coding theorem) establishes the fundamental limit of lossless data compression. For a source emitting symbols with entropy H, the average number of bits needed per symbol is at least H. Conversely, there exists a code that gets arbitrarily close to H. This means entropy is the ultimate compression ratio — no algorithm, no matter how clever, can compress data to fewer bits than its entropy without losing information. Huffman coding achieves entropy-optimal compression for known probability distributions (it assigns shorter codes to more frequent symbols). Lempel-Ziv (used in zip, gzip, PNG) achieves it for unknown distributions by building the dictionary adaptively. Every time you zip a file, you're getting closer to Shannon's limit — but you can never beat it.
Entropy is the hard limit of compression. You can't beat Shannon — but you can get arbitrarily close.
Prefix Codes and Kraft's Inequality
A prefix code (or instantaneous code) is a code where no codeword is a prefix of another. This lets you decode without lookahead. Kraft's inequality gives a necessary and sufficient condition for the existence of a prefix code with codeword lengths ℓ₁, ..., ℓₙ: Σ 2^{−ℓᵢ} ≤ 1 (for binary codes). Huffman's algorithm constructs the optimal prefix code for a given distribution — it repeatedly merges the two least probable symbols and assigns them the longest codewords. The average codeword length L satisfies H ≤ L < H + 1.
Shannon's Source Coding Theorem
The minimum possible average codeword length for lossless compression is H(X)
You can approach H arbitrarily closely by coding blocks of symbols together (the "per-symbol" entropy).
Huffman Code for a 4-Symbol Source
Symbols A, B, C, D with probabilities 0.5, 0.25, 0.125, 0.125. Huffman assigns: A=0, B=10, C=110, D=111. Average length = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 bits. Entropy H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits — optimal!
Part 3
📡 Channel Capacity and Reliable Communication
The Noisy Channel
Shannon's Second Theorem — How Much Can We Send Through a Noisy Channel?
Real communication channels are noisy — bits get flipped, signals fade, interference creeps in. The obvious solution is to add redundancy (error-correcting codes), but that reduces the effective data rate. Shannon's noisy channel coding theorem proves that for any channel with noise, there's a channel capacity C — the maximum rate at which information can be transmitted with arbitrarily low error probability. Below C, you can achieve near-perfect communication with the right code. Above C, reliable communication is impossible. The capacity of the additive white Gaussian noise channel is C = ½·log₂(1 + S/N) bits per channel use — the Shannon-Hartley theorem. This formula governs everything from WiFi to 5G to deep space communication. Modern turbo codes and LDPC codes get within a fraction of a dB of the Shannon limit.
Noise is inevitable, but Shannon tells us exactly how much we can communicate through it. The Shannon limit is the boundary between possible and impossible.
Mutual Information
The mutual information I(X; Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) measures how much knowing one variable reduces uncertainty about another. It's symmetric, non-negative, and equals 0 iff X and Y are independent. Channel capacity is defined as the maximum mutual information over all input distributions: C = max_{p(x)} I(X; Y). This is the fundamental limit — the tightest upper bound on how fast we can send data through a noisy channel.
The simplest noisy channel: input bits are flipped with probability p (crossover probability). The channel capacity is C = 1 − H₂(p) bits per channel use.
• p = 0: C = 1 bit (perfect channel — send raw bits)
• p = 0.5: C = 0 bits (channel is useless — output is independent of input)
• p = 0.1: C = 1 − (−0.1·log₂(0.1) − 0.9·log₂(0.9)) ≈ 1 − 0.47 = 0.53 bits
With a (7,4) Hamming code (which corrects 1 error per 7 bits), we can send 4 bits of information per 7 channel uses = 0.57 bits/use — below capacity at p=0.1. At p=0.01, capacity ≈ 0.92 bits/use, and the Hamming code still only gives 0.57 — we need more efficient codes like turbo or LDPC to approach the limit.
Error-Correcting Codes
Hamming codes (1950) were the first practical error-correcting codes. A (7,4) Hamming code encodes 4 data bits into 7 bits, correcting any single-bit error. Reed-Solomon codes correct burst errors and are used in CDs, QR codes, and space probes. Turbo codes (1993) and LPDC codes (rediscovered in the 1990s) approach the Shannon limit within fractions of a decibel — they're used in 4G/5G, satellite communication, and deep space networks. The search for capacity-approaching codes drove half a century of coding theory, and the field continues to evolve with polar codes (Arikan, 2009), the first provably capacity-achieving codes with low complexity.
Part 4
🌌 Beyond Shannon — Entropy in Physics, ML, and Quantum Information
Entropy Is Everywhere
From Thermodynamics to Machine Learning — The Universal Language of Uncertainty
Shannon's entropy is mathematically identical to Boltzmann's entropy in thermodynamics: S = k_B · ln(W) where W is the number of microstates. Shannon's H is just Boltzmann's S but with base-2 logs and a different constant. This is no coincidence — both measure the same thing: the number of possible states of a system, and thus our uncertainty about which one it's in. In machine learning, cross-entropy is the most common loss function for classification — it measures the difference between the predicted and actual probability distributions. KL divergence D_KL(P||Q) = Σ p(x) log(p(x)/q(x)) measures how much information is lost when using Q to approximate P. It's the foundation of variational inference, Bayesian deep learning, and generative models (VAEs use KL divergence to regularize latent spaces). In quantum information theory, the von Neumann entropy S(ρ) = −Tr(ρ log ρ) generalizes Shannon entropy to quantum states, and the Holevo bound limits how much classical information can be extracted from a quantum system.
Entropy is the bridge between physics, information, and learning — a single idea that connects the second law of thermodynamics to the training of neural networks.
KL Divergence and the Information Bottleneck
The Kullback-Leibler divergence (or relative entropy) is the foundation of information geometry. It's not a metric (it's asymmetric), but it satisfies D_KL ≥ 0 with equality iff P = Q. The information bottleneck method finds a compressed representation Z of X that preserves information about Y — it maximizes I(Z; Y) − β·I(Z; X). This has become a framework for understanding deep learning: neural networks naturally learn to compress inputs while preserving task-relevant information.
Data Processing Inequality
I(X; Y) ≥ I(X; f(Y)) for any function f
Processing can only destroy or preserve information — it can never create it. This simple inequality is the foundation of all data analysis.
Rate-Distortion Theory — Lossy Compression
Not all compression needs to be lossless. Rate-distortion theory answers: given a distortion measure (like mean squared error), what's the minimum bitrate needed to reconstruct a source within a given distortion D? The rate-distortion function R(D) characterizes this trade-off. For a Gaussian source with variance σ² and MSE distortion, R(D) = ½·log₂(σ²/D) for D ≤ σ². This is the theory behind JPEG, MP3, and video compression — you trade bits for perceptual quality, and Shannon tells you the optimal trade-off.
Two envelopes contain money, one twice as much as the other. You pick one, open it, and find $100. Should you switch?
Naive reasoning: the other envelope has $50 or $200 with equal probability, expected value = $125, so switch! But this reasoning would apply regardless of what you found, so you'd switch even before opening — a contradiction.
The resolution: you need a prior distribution over the amounts. If all amounts are equally likely, the expected value is infinite (improper prior), and the calculation breaks down. Information theory tells us that without a proper prior, you can't assign meaningful probabilities — the "equally likely" assumption smuggles in an infinite expected value.
This shows how careful we must be with probabilistic reasoning — a key lesson for both information theory and decision theory.
"The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point. Frequently the messages have meaning; that is, they refer to or are correlated according to some system with certain physical or conceptual entities. These semantic aspects of communication are irrelevant to the engineering problem."
— Claude Shannon, 1948 — the opening of the paper that created information theory
🎯 Practice — Check Your Information Theory Intuition
These puzzles build information theory intuition — no heavy math needed.