Information Theory Inequalities

Jensen’s inequality

Motivation: Whenever we have a random variable $X$, we often need to look at a function of that variable, $f(X)$. If the function is perfectly linear (like $f(x) = 2x$), the average of the function’s outputs exactly equals the function evaluated at the average input: $\mathbb{E}[f(X)] = f(\mathbb{E}[X])$. However, in nearly all branches of engineering and mathematics, systems are non-linear. In information theory, our entire framework is built on the highly non-linear logarithm function ($f(x) = \log x$). Because a curve bends, the “average of the curve at points” is not equal to the “curve of the average of those points.” We need a law that tells us exactly how a function’s geometric curvature biases its expected value. This is Jensen’s Inequality. By bounding how expected values behave inside non-linear functions, Jensen’s Inequality allows us to prove some limits of our communication systems.

Convex and concave functions

To be able to reason about functions on random variables in non-linear systems, we need to define the curvature of the functions more rigorously so we can analyze it.

ProofUsing Taylor series

Expand $f(x)$ around a point $x_0$:

$$f(x) = f(x_0) + f'(x_0)(x - x_0) + \frac{f''(x^*)}{2}(x - x_0)^2$$

Since $f''(x^*) \ge 0$, the last term is always non-negative. Therefore, the curve always sits above its tangent line: $f(x) \ge f(x_0) + f'(x_0)(x - x_0)$. If we let $x_0 = \lambda x_1 + (1-\lambda)x_2$ and plug in $x = x_1$ and $x = x_2$ respectively, multiplying the resulting inequalities by $\lambda$ and $(1-\lambda)$ and adding them together algebraically yields the exact definition of convexity.

∎

Applications to information theory: $f(x) = x^2, e^x$, and $x \log x$ (for $x \ge 0$) have positive second derivatives, making them strictly convex. $f(x) = \log x$ has a second derivative of $-1/x^2$. Since probability $x > 0$, this is strictly negative. Therefore, $\log x$ is strictly concave and $-\log x$ is strictly convex. The use case is usually to move both the summation and the probability inside the log in all the information theoretic terms.

We know a chord between two points on a convex curve sits above the curve. Jensen’s Inequality generalizes this algebraic definition from two points to an entire random variable.

ProofBy induction on discrete distributions

Base case (2 mass points): Let $X$ take values $x_1, x_2$ with probabilities $p_1, p_2$. By the literal definition of convexity (replacing $\lambda$ with $p_1$):

$$p_1 f(x_1) + p_2 f(x_2) \ge f(p_1 x_1 + p_2 x_2)$$

This is exactly $\mathbb{E}[f(X)] \ge f(\mathbb{E}[X])$.

Inductive step: Assume the theorem holds for $k-1$ mass points. We prove it for $k$ points. Isolate the $k$-th term, and re-weight the remaining $k-1$ probabilities by defining $p_i' = p_i / (1 - p_k)$:

$$\sum_{i=1}^k p_i f(x_i) = p_k f(x_k) + (1 - p_k) \sum_{i=1}^{k-1} p_i' f(x_i)$$

Apply the inductive hypothesis to the inner summation (since it has $k-1$ terms), pulling $f$ outside:

$$\ge p_k f(x_k) + (1 - p_k) f \left( \sum_{i=1}^{k-1} p_i' x_i \right)$$

We now have exactly two weighted terms: $p_k$ and $(1-p_k)$. Apply the base-case convexity definition one final time to pull $f$ outside everything:

$$\ge f \left( p_k x_k + (1 - p_k) \sum_{i=1}^{k-1} p_i' x_i \right) = f \left( \sum_{i=1}^k p_i x_i \right) = f(\mathbb{E}[X])$$

∎

Consequences of Jensen’s inequality

By passing our information measures through Jensen’s Inequality, we establish the fundamental physical bounds of communication theory.

ProofLet $A$ be the support set where $p(x) > 0$

$$-D(p\vert{}\vert{}q) = - \sum_{x \in A} p(x) \log \frac{p(x)}{q(x)} = \sum_{x \in A} p(x) \log \frac{q(x)}{p(x)}$$

Because $\log(t)$ is strictly concave, $\mathbb{E}[\log(X)] \le \log(\mathbb{E}[X])$. We apply this by bringing the logarithm outside the summation:

$$\le \log \left( \sum_{x \in A} p(x) \frac{q(x)}{p(x)} \right) = \log \left( \sum_{x \in A} q(x) \right)$$

Because probabilities must sum to 1 (or less, if $A$ is a subset), $\sum_{x \in A} q(x) \le 1$.

$$\le \log(1) = 0$$

Therefore, $-D(p\vert{}\vert{}q) \le 0$, meaning $D(p\vert{}\vert{}q) \ge 0$.

∎

Proof

Since $I(X;Y) = D(p(x,y) \vert{}\vert{} p(x)p(y))$, and all relative entropies are $\ge 0$, mutual information is $\ge 0$. (Equality holds iff $X$ and $Y$ are independent).

∎

Proof

Let $u(x) = 1/\vert{}\mathcal{X}\vert{}$ be the uniform distribution Calculate $D(p\vert{}\vert{}u) = \sum p(x) \log \frac{p(x)}{1/\vert{}\mathcal{X}\vert{}} = \sum p(x) \log p(x) + \sum p(x) \log \vert{}\mathcal{X}\vert{} = -H(X) + \log \vert{}\mathcal{X}\vert{}$.

Since $D(p\vert{}\vert{}u) \ge 0$, we have $\log \vert{}\mathcal{X}\vert{} - H(X) \ge 0$.

∎

Proof

We know $I(X;Y) = H(X) - H(X\vert{}Y)$. We also know $I(X;Y) \ge 0$. Therefore, $H(X) - H(X\vert{}Y) \ge 0$.

∎

ProofApply the Chain Rule for Entropy

$H(X_1, \ldots, X_n) = \sum_{i=1}^n H(X_i \vert{} X_{i-1}, \ldots, X_1)$. By theorem above, conditioning reduces entropy, so $H(X_i \vert{} X_{i-1}, \ldots, X_1) \le H(X_i)$ for every term. Substituting this bound into the summation proves the theorem.

∎

[!APPLICATION] Bounding the Entropy of Unseen Tails via Jensen’s Inequality A common challenge in data systems, from high-speed network telemetry to Natural Language Processing (NLP), is that distributions have massive or infinite supports, but hardware and memory constraints prevent tracking every rare tail event.

Jensen’s inequality gives a guaranteed ceiling on the uncertainty hiding inside an unprofiled tail without needing to store or identify the rare items.

---

The Setup: Heavy Hitters and the Tail

Suppose a system samples from a discrete distribution. We can afford fast memory to track exact counts for the top $k$ dominant outcomes (“heavy hitters”), leaving an unprofiled tail:

• Tracked mass: $P_{\text{top}} = \sum_{i=1}^k p_i$
• Tail mass: $P_{\text{tail}} = 1 - P_{\text{top}}$
• Tail cardinality: At most $M$ distinct possible items in the tail.

Total entropy splits into the tracked portion and the unobserved tail: $$H(X) = H_{\text{top}} + H_{\text{tail}} = \sum_{i=1}^k -p_i \log_2 p_i + \sum_{x \in \text{tail}} -p(x) \log_2 p(x)$$

---

The Derivation via Jensen’s Inequality

Define the normalized conditional probability distribution over the $M$ tail items as $w_i = \frac{p_i}{P_{\text{tail}}}$, such that $\sum_{i=1}^M w_i = 1$. The tail’s entropy is:

$$H_{\text{tail}} = \sum_{i=1}^M -p_i \log_2 p_i = P_{\text{tail}} \sum_{i=1}^M w_i \log_2 \left(\frac{1}{p_i}\right)$$

Because $f(t) = \log_2(t)$ is strictly concave, Jensen’s inequality states that $\mathbb{E}[f(T)] \le f(\mathbb{E}[T])$:

$$\sum_{i=1}^M w_i \log_2 \left(\frac{1}{p_i}\right) \le \log_2 \left( \sum_{i=1}^M w_i \frac{1}{p_i} \right)$$

Substitute $w_i = \frac{p_i}{P_{\text{tail}}}$ into the inner sum:

$$\sum_{i=1}^M w_i \frac{1}{p_i} = \sum_{i=1}^M \left(\frac{p_i}{P_{\text{tail}}}\right) \frac{1}{p_i} = \sum_{i=1}^M \frac{1}{P_{\text{tail}}} = \frac{M}{P_{\text{tail}}}$$

Multiplying through by $P_{\text{tail}}$ gives the fundamental tail bound:

$$H_{\text{tail}} \le P_{\text{tail}} \log_2 \left( \frac{M}{P_{\text{tail}}} \right)$$

(Equality holds if and only if the tail is perfectly uniform, where every tail item has probability $p_i = \frac{P_{\text{tail}}}{M}$.)

This gives an exact bounding bracket on the true source entropy:

$$H_{\text{top}} \le H(X) \le H_{\text{top}} + P_{\text{tail}} \log_2 \left( \frac{M}{P_{\text{tail}}} \right)$$

---

Where This Is Used

1. Streaming Network Telemetry (DDoS Detection):
   • The problem: High-speed routers monitor traffic entropy to detect DDoS attacks. Normal traffic is dispersed (high entropy), while flood attacks surge toward a single target (entropy drops sharply). However, on 100 Gbps fiber links, a switch cannot maintain per-flow hash tables for $2^{32}$ IPv4 addresses in fast SRAM.
   • The streaming solution: Routers deploy the Misra-Gries heavy-hitter algorithm (keeping only $k$ board slots). If an IP arrives and is on the board, its count increments; if a slot is open, it takes it; if the board is full, every count decrements by 1. For $N$ packets, mass-subtractions occur at most $\frac{N}{k+1}$ times since we effectively discard k+1 previous observations on every board miss. Any flow exceeding $\frac{1}{k+1}$ of total traffic is mathematically guaranteed to stay on the board.
   • Bounding the tail: Packets decremented or unrecorded form the tail. The switch knows the exact residual packet fraction $P_{\text{tail}}$ and upper bounds $M$ by the total number of unrecorded packets. Using Jensen’s bound $P_{\text{tail}} \log_2(M / P_{\text{tail}})$, the router establishes certified anomaly thresholds without ever allocating RAM for millions of fleeting tail connections.
2. Natural Language Processing & Language Model Vocabulary Truncation:
   • The problem: Real-world language vocabularies follow heavy-tailed Zipfian distributions. Language models and compression tools truncate vocabularies to the top $K$ frequent words (e.g., $K = 50,000$), mapping every other rare word, typo, or foreign token into a single catch-all <UNK> (unknown) token.
   • Bounding perplexity: Evaluating a model’s true cross-entropy or perplexity over an open vocabulary requires accounting for the unseen tail lumped inside <UNK>. By tracking the total empirical probability mass assigned to <UNK> ($P_{\text{tail}} = P(\text{UNK})$) and estimating the remaining vocabulary size $M$, Jensen’s inequality guarantees the maximum possible surprise hiding inside that unresolved <UNK> bucket, establishing formal bounds on out-of-vocabulary perplexity.

The log sum inequality

We have used Jensen’s Inequality to prove the limits of a static communication system (e.g., the penalty of a wrong codebook is always $\ge 0$). But real telegraph networks are dynamic.

Suppose your telegraph operator operates smoothly in the morning (with source probability $p_1$) and gets highly erratic at night due to drinking (with source probability $p_2$). If an engineer is lazy and tries to build a single “daily average” model by mathematically blending the morning and night probabilities together, do they gain or lose precision?

To prove how uncertainty and penalties behave when we mix distributions, we need a tool that handles the sum of blended ratios. This is the Log Sum Inequality. It is the formal proof that blending distinct signals always destroys information.

ProofVia Jensen’s inequality

To prove this, we first need to build a strictly convex function.

Let $f(t) = t \log t$.

First derivative: $f'(t) = \log t + 1$ (if base $e$; or $\frac{1}{\ln 2} \log_2 t + \frac{1}{\ln 2}$).

Second derivative: $f''(t) = 1/t$ (times a positive constant depending on the log base).

Since our inputs $t$ will be strictly positive, $1/t > 0$. Because the second derivative is strictly positive, the function $f(t) = t \log t$ is strictly convex.

Now, we set up Jensen’s Inequality: $\sum \lambda_i f(t_i) \ge f(\sum \lambda_i t_i)$.

To use Jensen’s, we need our weights $\lambda_i$ to act like a valid probability distribution (they must sum to 1).

Let $A = \sum a_i$ and $B = \sum b_i$.

We construct our valid probability weights using the $b$ terms: $\lambda_i = \frac{b_i}{B}$.

We will feed the function the ratio of our terms: $t_i = \frac{a_i}{b_i}$.

Evaluate the left side of Jensen’s (the expected value of the function).

$$\sum_i \lambda_i f(t_i) = \sum_i \frac{b_i}{B} \left( \frac{a_i}{b_i} \log \frac{a_i}{b_i} \right)$$

The $b_i$ in the numerator and denominator cancel out, leaving:

$$= \frac{1}{B} \sum_i a_i \log \frac{a_i}{b_i}$$

Evaluate the right side of Jensen’s (the function of the expected value). First, find the expected value inside the function:

$$\sum_i \lambda_i t_i = \sum_i \frac{b_i}{B} \frac{a_i}{b_i} = \frac{1}{B} \sum_i a_i = \frac{A}{B}$$

Now apply the function $f(t) = t \log t$ to that result:

$$f\left(\frac{A}{B}\right) = \frac{A}{B} \log \frac{A}{B}$$

Bring them together. Because $f(t)$ is convex, Left Side $\ge$ Right Side.

$$\frac{1}{B} \sum_i a_i \log \frac{a_i}{b_i} \ge \frac{A}{B} \log \frac{A}{B}$$

Multiply both sides by $B$, and you get the Log Sum Inequality:

$$\sum_{i=1}^n a_i \log \frac{a_i}{b_i} \ge A \log \frac{A}{B}$$

∎

Consequences: applying it to telecom

The Log Sum Inequality looks like a pretty random inequality, but substituting $p(x)$ and $q(x)$ for $a$ and $b$ instantly proves two physical properties of communication networks.

Convexity of relative entropy

Proof

We want to evaluate the blended Relative Entropy for a specific symbol $x$. We map our variables to the Log Sum Inequality:

Let $a_1 = \lambda p_1(x)$ and $a_2 = (1-\lambda)p_2(x)$. (These sum to the blended reality).

Let $b_1 = \lambda q_1(x)$ and $b_2 = (1-\lambda)q_2(x)$. (These sum to the blended assumption).

Applying the Log Sum Inequality to these two terms:

$$a_1 \log \frac{a_1}{b_1} + a_2 \log \frac{a_2}{b_2} \ge (a_1 + a_2) \log \frac{a_1 + a_2}{b_1 + b_2}$$

Substituting our probabilities back in:

$$\lambda p_1(x) \log \frac{\lambda p_1(x)}{\lambda q_1(x)} + (1-\lambda) p_2(x) \log \frac{(1-\lambda) p_2(x)}{(1-\lambda) q_2(x)} \ge \big( \lambda p_1(x) + (1-\lambda)p_2(x) \big) \log \frac{\lambda p_1(x) + (1-\lambda)p_2(x)}{\lambda q_1(x) + (1-\lambda)q_2(x)}$$

Notice the weights $\lambda$ and $(1-\lambda)$ cancel out inside the isolated logarithms on the left.

Summing this inequality over all symbols $x \in \mathcal{X}$ yields:

$$\lambda D(p_1\vert{}\vert{}q_1) + (1-\lambda) D(p_2\vert{}\vert{}q_2) \ge D(\lambda p_1 + (1-\lambda)p_2 \vert{}\vert{} \lambda q_1 + (1-\lambda)q_2)$$

∎

Concavity of entropy

Claim: Blending predictable systems creates an unpredictable system. “Averaging destroys certainty.”

Proof

We can prove this instantly using the convexity of Relative Entropy we just derived. Entropy is simply the maximum possible entropy ($\log \vert{}\mathcal{X}\vert{}$) minus the relative entropy distance to the uniform distribution $u(x) = 1/\vert{}\mathcal{X}\vert{}$:

$$H(p) = \log \vert{}\mathcal{X}\vert{} - D(p\vert{}\vert{}u)$$

We substitute this definition into the convexity inequality, setting both $q_1$ and $q_2$ to the uniform distribution $u$:

$$D(\lambda p_1 + (1-\lambda)p_2 \vert{}\vert{} u) \le \lambda D(p_1\vert{}\vert{}u) + (1-\lambda) D(p_2\vert{}\vert{}u)$$

Replace the $D$ terms with their entropy equivalents:

$$\log \vert{}\mathcal{X}\vert{} - H(\lambda p_1 + (1-\lambda)p_2) \le \lambda \big(\log \vert{}\mathcal{X}\vert{} - H(p_1)\big) + (1-\lambda) \big(\log \vert{}\mathcal{X}\vert{} - H(p_2)\big)$$

The $\log \vert{}\mathcal{X}\vert{}$ terms cleanly cancel out from both sides:

$$-H(\lambda p_1 + (1-\lambda)p_2) \le - \lambda H(p_1) - (1-\lambda) H(p_2)$$

Multiply by $-1$ and flip the inequality:

$$H(\lambda p_1 + (1-\lambda)p_2) \ge \lambda H(p_1) + (1-\lambda) H(p_2)$$

∎

Data processing inequality

Suppose our sender $X$ transmits a message across a noisy copper wire, and the receiver gets a corrupted signal $Y$. The receiver decides to plug their machine into a secondary computer to “clean up” the signal, running it through a complex algorithm or a statistical filter to produce a final output $Z$.

In engineering, we model multi-stage pipelines, like running raw data through a software filter, or relaying a signal from a Mars rover ($X$) to an orbiter ($Y$) to an Earth station ($Z$), using Markov chains.

Why do we need them? Without the Markov property, analyzing a set of outcomes in different parts of a multi-stage system requires using the chain rule of probability, where would have to condition every new event on the entire history of all events of the pipeline:

$$p(x, y, z) = p(x) p(y \vert{} x) p(z \vert{} x, y)$$

If this pipeline had ten steps, the final probability would be conditioned on all nine previous variables, which becomes computationally heavy.

The Markov property lets us decouple complex systems into isolated, local hops. Instead of analyzing the whole network at once, we only need to understand the transition from one node to the very next.

By modeling our system as a step-by-step Markov chain, we can answer whether downstream processing can recover the original message? Can the final filtered output $Z$ have more mutual information with the sender $X$ than the raw, corrupted signal $Y$ originally did?

To prove why processing can never increase information, we first define our sequential pipeline.

Markov chains ($X \rightarrow Y \rightarrow Z$)

Because of this conditional independence, the joint probability of the entire three-part system factors cleanly into a chain of local, step-by-step probabilities:

Because knowing $X$ provides absolutely zero new statistical information about the behavior of $Z$ once the intermediate bottleneck $Y$ is known, their conditional mutual information is zero: $I(X ; Z \vert{} Y) = 0$.

ProofThrough the chain rule for mutual information

We want to calculate the total mutual information between the original sender $X$ and the entire receiver system $(Y, Z)$. We can expand this joint mutual information $I(X; Y, Z)$ in two different directions.

Expansion 1 (start with $Y$). Using the chain rule, the information $X$ shares with the whole system is the information it shares with $Y$, plus the new information it shares with $Z$ (given that we already know $Y$):

$$I(X; Y, Z) = I(X; Y) + I(X; Z \vert{} Y)$$

Expansion 2 (start with $Z$). Alternatively, we can expand it backwards. The information $X$ shares with the whole system is the information it shares with $Z$, plus the new information it shares with $Y$ (given that we already know $Z$):

$$I(X; Y, Z) = I(X; Z) + I(X; Y \vert{} Z)$$

Equating and simplifying. Because both expansions equal the exact same total $I(X;Y,Z)$, we set them equal to each other:

$$I(X; Y) + I(X; Z \vert{} Y) = I(X; Z) + I(X; Y \vert{} Z)$$

Now, we apply our physical constraint. Because X → Y → Z is a Markov chain, we established that $I(X; Z \vert{} Y) = 0$. (Once you have the raw signal Y, the processed signal Z tells you absolutely nothing new about X). Substitute 0 into the left side of the equation:

$$I(X; Y) = I(X; Z) + I(X; Y \vert{} Z)$$

Finally, we proved via Jensen’s Inequality that all mutual information quantities are non-negative. Therefore, $I(X; Y \vert{} Z) \ge 0$. If $I(X;Y)$ is equal to $I(X;Z)$ plus some positive number, then $I(X;Y)$ must be greater than or equal to $I(X;Z)$.

$$I(X; Y) \ge I(X; Z)$$

∎

Consequences and corollaries

This proves that you cannot gain information by applying a function to your data. If you take a noisy audio file and run it through a complex equalizer function, the resulting file might sound better to a human, but mathematically, it contains less (or equal) information about the original studio recording than the raw file did.

When does equality hold?

The only way for $I(X; Y) = I(X; Z)$ to be true is if the leftover term $I(X; Y \vert{} Z)$ is exactly $0$. This means $X \rightarrow Z \rightarrow Y$ must also form a Markov chain. In engineering terms, this means the processing step $Z$ perfectly preserved every single detail of $Y$ that was relevant to $X$. (In statistics, a function that achieves this equality is called a Sufficient Statistic).

Sufficient statistics

In our communication systems, we don’t always know the exact physical reality of the wire. Often, there is a hidden parameter $\theta$ governing the system (e.g., the exact probability $\theta$ that a static burst flips a bit). We cannot observe $\theta$ directly, we can only observe a raw sequence of received data $X$.

To save bandwidth and storage, an engineer might want to compress that massive raw dataset $X$ into a small, calculated summary value, $T(X)$, such as the sample mean or the total number of errors.

Because the parameter generates the data, and the data generates the summary, this forms a strict Markov chain:

$$\theta \rightarrow X \rightarrow T(X)$$

By the Data Processing Inequality, we know that processing the raw data into a summary must destroy (or at best, preserve) information about the hidden parameter:

$$I(\theta; T(X)) \le I(\theta; X)$$

We need to know: is it mathematically possible to compress the raw data $X$ into a smaller footprint $T(X)$ such that we hit exact equality, losing absolutely zero information about the hidden parameter $\theta$?

By the equality condition of the Data Processing Inequality, for the information to remain perfectly intact, the Markov chain must be reversible. The sequence $\theta \rightarrow T(X) \rightarrow X$ must also form a valid Markov chain. This gives us the formal definition: $T(X)$ is a sufficient statistic if the raw data $X$ is conditionally independent of the parameter $\theta$, given $T(X)$.

Examples of sufficient statistics

1. The coin toss (discrete binary channel). Suppose a noisy wire flips bits with an unknown probability $\theta$. We send a sequence of $n$ zeroes, and receive a raw sequence of bits $X_1, X_2, \ldots, X_n$. Instead of storing the exact sequence of bits (e.g., 0, 1, 1, 0, 1), the engineer simply stores the total number of flipped bits: $T(X) = \sum X_i = 3$. Is $T$ a sufficient statistic? Yes. If you know exactly 3 bits flipped out of 5, every single permutation that contains three 1s (like 1,1,1,0,0 or 0,1,0,1,1) is equally likely. Knowing the actual physical parameter $\theta$ does not give you any extra predictive power to guess which specific arrangement happened. The sum $T$ captured 100% of the useful information about $\theta$.

2. The normal distribution (continuous). If $X$ is a sequence of normally distributed voltage readings with an unknown mean $\theta$ and a known variance of 1, the sample mean $\bar{X} = \frac{1}{n}\sum X_i$ is a sufficient statistic.

Once you know the sample mean, the exact scatter of the individual voltage spikes around that mean is driven entirely by the known variance (the system’s baseline noise). The specific pattern of the scatter contains absolutely zero additional mathematical evidence about the true location of $\theta$.

1. The uniform distribution (continuous). If noise is distributed uniformly between an unknown floor $\theta$ and a ceiling $\theta + 1$, the sample mean is actually not sufficient. If you only know the mean, $\theta$ could still shift up or down depending on the extreme outliers. A sufficient statistic here is the pair of the absolute highest and lowest spikes: $T(X) = (\max\{X_i\}, \min\{X_i\})$, because they rigidly lock the possible bounds of $\theta$.

Minimal sufficient statistics

While a sufficient statistic guarantees no information about $\theta$ is lost, it does not guarantee maximum compression.

For example, if we are tracking the probability of bit flips ($\theta$), storing the pair of values (sum of the first half of the sequence, sum of the second half of the sequence) is technically a sufficient statistic $U(X)$. It preserves all information about $\theta$. But it is redundant. It stores two numbers when one would do the job.

Proving Minimality

To prove a sufficient statistic is minimal, you must show that any further attempt to compress it will strictly break the equality $I(\theta; T(X)) = I(\theta; X)$.

Let’s look at why our previous examples are minimal:

1. The bit flip sum ($T(X) = \sum X_i$): We saw that $U(X) = (Sum_{first\_half}, Sum_{second\_half})$ was sufficient. We can compute our single sum $T(X)$ directly from $U(X)$ by adding the two values together. However, we cannot go backwards. Knowing $T(X) = 3$ does not let us compute $U(X)$ (was it 2+1, or 3+0?). This proves $T(X)$ is a deeper compression. Why is $T(X)$ minimal? Because if we compress it even one step further, for example, only storing whether the sum is Even or Odd, or capping the sum at a max of 10, we throw away the exact ratio of 1s to 0s, $I(\theta; T(X))$ drops, and it is no longer sufficient. Therefore, the exact integer sum is the absolute floor of compression.

2. The min/max pair for uniform noise ($T(X) = (\min, \max)$): Can we compress this pair into a single number, like the median or the difference $(\max - \min)$? If we only store the difference between the highest and lowest spikes, we know the spread of the noise, but we lose the absolute location of the floor. Without the floor, we lose our exact lock on $\theta$. Thus, storing two distinct values is mathematically the smallest possible footprint that retains 100% of the information about a uniform boundary.

Fano’s inequality: the physical limits of guessing

The problem: translating abstract noise into physical error rates. Suppose you are transmitting English letters ($|\mathcal{X}| = 26$) over a noisy telegraph wire. The sender types a letter $X$, the wire corrupts it into a smudge $Y$, and the receiving machine runs a decoding algorithm to print a final guess $\hat{X} = g(Y)$.

Because the machine calculates its guess strictly from the corrupted signal $Y$ and has no secret line to the sender, this forms a Data Processing Markov chain:

$$X \rightarrow Y \rightarrow \hat{X}$$

We know that physical noise permanently destroys information in the wire, quantified by the conditional entropy $H(X|Y)$. But engineers do not measure success in “conditional entropy”, they measure it in the physical probability of an error, $P_e = \Pr(\hat{X} \neq X)$.

Fano’s Inequality translates the abstract mathematical noise of the wire directly into a hard, statistical floor for the machine’s error rate.

The theorem

The proof

ProofVia an error indicator variable

We prove this by tracking the machine’s success using an artificial binary random variable, $E$. Let $E = 1$ if the machine failed ($\hat{X} \neq X$), and $E = 0$ if the machine succeeded ($\hat{X} = X$).

We want to calculate the joint conditional entropy $H(E, X | \hat{X})$. We expand this using the Chain Rule for Entropy in two different directions.

Expansion 1 (condition on X first). $$H(E, X | \hat{X}) = H(X | \hat{X}) + H(E | X, \hat{X})$$ If we know both the sender’s true symbol $X$ and the machine’s guess $\hat{X}$, there is absolutely zero uncertainty about whether an error occurred. Therefore, $H(E | X, \hat{X}) = 0$. $$H(E, X | \hat{X}) = H(X | \hat{X})$$

Expansion 2 (condition on E first). $$H(E, X | \hat{X}) = H(E | \hat{X}) + H(X | E, \hat{X})$$ By Theorem 2.6.5 (Conditioning Reduces Entropy), we can drop $\hat{X}$ from the first term to upper-bound it: $H(E | \hat{X}) \le H(E)$. Since $E$ is a simple binary coin flip (error or no error), its entropy is just $H(P_e)$. Now we bound the second term, $H(X | E, \hat{X})$, by averaging over the two possible states of the error indicator $E$: $$H(X | E, \hat{X}) = \Pr(E = 0)H(X | \hat{X}, E=0) + \Pr(E = 1)H(X | \hat{X}, E=1)$$

• Case E=0 (no error). If there is no error, $X$ is exactly $\hat{X}$. Since we are conditioning on $\hat{X}$, there is 0 uncertainty about $X$.
• Case E=1 (error). If an error occurred, we know $X$ must be one of the symbols in the alphabet. The absolute maximum uncertainty of any variable is the log of its total possible outcomes. We safely upper bound this by $\log |\mathcal{X}|$.

Substituting these bounds back into the expansion gives: $$H(X | E, \hat{X}) \le (1 - P_e)(0) + P_e \log |\mathcal{X}|$$ Therefore, Expansion 2 is bounded by: $$H(E, X | \hat{X}) \le H(P_e) + P_e \log |\mathcal{X}|$$

Equating and applying data processing. Equating Expansion 1 and our bound for Expansion 2, we get: $$H(P_e) + P_e \log |\mathcal{X}| \ge H(X|\hat{X})$$ Finally, because $X \rightarrow Y \rightarrow \hat{X}$ is a Markov chain, the Data Processing Inequality guarantees the guess cannot have more information than the raw signal: $I(X; \hat{X}) \le I(X; Y)$. Expanding this into entropies ($H(X) - H(X|\hat{X}) \le H(X) - H(X|Y)$) proves that $H(X|\hat{X}) \ge H(X|Y)$. We chain this onto our proof to finish it: $$H(P_e) + P_e \log |\mathcal{X}| \ge H(X|\hat{X}) \ge H(X|Y)$$

∎

---

Useful corollaries: Calculating the exact error floor

1. The absolute error floor: Because the binary entropy of the error event, $H(P_e)$, can never exceed 1 bit (maximum uncertainty), we can replace $H(P_e)$ with 1 to simplify the inequality:

$$1 + P_e \log |\mathcal{X}| \ge H(X|Y)$$

Algebraically rearranging this isolates $P_e$, giving an engineer a direct formula for the lowest possible error rate their network can ever achieve, regardless of their software:

$$P_e \ge \frac{H(X|Y) - 1}{\log |\mathcal{X}|}$$

2. A tighter bound (alphabet restriction): If your decoding software is smart enough to only guess valid letters ($\hat{X} \in \mathcal{X}$), then when it makes an error ($E=1$), we know the true symbol must be one of the other $(|\mathcal{X}| - 1)$ letters. We can shrink the penalty term:

$$H(P_e) + P_e \log(|\mathcal{X}| - 1) \ge H(X|Y)$$

---

A sidelight: Probability of Collision (The Birthday Paradox in Information Theory)

Fano’s inequality establishes the physical limits of a machine trying to calculate a match for a noisy signal. But what happens if we remove the wire entirely, and just look at two completely independent sources? What is the probability that they randomly “guess” each other, generating the exact same output at the exact same time?

This leads to a beautiful corollary about collisions, which forms the mathematical foundation for cryptography, hashing algorithms, and the Birthday Paradox.

Motivation. Suppose two independent systems (like two password generators) both output symbols using the exact same probability distribution $p(x)$. What is the probability they randomly collide ($\Pr(X = X')$)?

To understand this, look at the classic Birthday Paradox. If a system picks uniformly from 1,000 possible passwords, the chance of two systems colliding is exactly $1/1000$. (System A picks some password, and System B has a $1/1000$ chance of matching whatever A picked).

But what if the system isn’t uniform? What if it is highly biased (low entropy), meaning it heavily favors picking “password123”? The collisions will skyrocket. Information theory formalizes this intuition: the lower the entropy of a system, the more frequently its independent outputs will crash into each other.

To find the total probability of a collision, we must sum up the probability of them colliding on the first symbol, plus colliding on the second symbol, and so on: $$\Pr(X = X') = \sum_x \Pr(X = x)\Pr(X' = x) = \sum_x p^2(x)$$

ProofVia Jensen’s inequality

We want to find a lower bound for $\sum p^2(x)$. Let’s rewrite this cleverly as an Expected Value. By definition, the expected value of a function $g(x)$ is $\sum p(x)g(x)$. If we let our function simply be the probability itself, $g(x) = p(x)$, we get: $$\mathbb{E}[p(X)] = \sum p(x) p(x) = \sum p^2(x)$$

Next, notice that $p(x)$ can be rewritten algebraically using a base-2 logarithm as $2^{\log p(x)}$. Therefore, our collision probability is perfectly equivalent to $\mathbb{E}[2^{\log p(X)}]$.

The function $f(y) = 2^y$ curves upward sharply (it is strictly convex because its second derivative is positive). Therefore, by Jensen’s Inequality, the Expected Value of the function is always $\ge$ the function of the Expected Value:

$$\mathbb{E}[2^{\log p(X)}] \ge 2^{\mathbb{E}[\log p(X)]}$$

Now, look at the exponent on the right side. The expected value of $\log p(X)$ is literally the definition of negative entropy: $\mathbb{E}[\log p(X)] = \sum p(x) \log p(x) = -H(X)$. Substituting this back in proves the lemma:

$$\sum p^2(x) \ge 2^{-H(X)}$$

∎

How Information Theory drives the Cryptographic Birthday Paradox

In cryptography, hash functions produce outputs of a fixed bit length, $n$ (like a 256-bit hash). This means there are theoretically $2^n$ possible unique hashes. The famous cryptographic rule of thumb states that a hacker only needs $2^{n/2}$ random guesses to find a collision since we compare the guessed inputs hash output against all the previous hash outputs.

But this assumes the hash function is perfect. How does the math actually work if the algorithm is flawed? We can use our Information Theory lemma to prove exactly how many guesses an attack requires based on the system’s actual entropy.

1. The single-pair probability Our lemma proved that the probability of any two specific outputs randomly colliding is governed by the system’s entropy: $\Pr(X = X') \ge 2^{-H(X)}$. If a hash function is perfectly uniform, its entropy equals its bit length: $H(X) = n$. Therefore, the baseline probability of a single pair colliding is $2^{-n}$.

2. The explosive growth of pairs The Birthday Paradox occurs because a hacker making $k$ guesses doesn’t just make $k$ comparisons. They compare every new guess against every single previous guess. Generating $k$ outputs creates approximately $k^2$ unique pairs.

3. Equating pairs to the probability For a hacker to have a high probability of finding a collision, the total number of pairs they generate ($k^2$) must roughly equal the inverse of the single-pair collision probability ($2^{H(X)}$): $$k^2 \approx 2^{H(X)}$$

Take the square root of both sides to find $k$ (the number of guesses required): $$k \approx \sqrt{2^{H(X)}} = 2^{H(X) / 2}$$

Nonnegativity of entropy

Proof

On the support, $0 < p(x) \le 1$, so $-\log p(x) \ge 0$. Entropy is $H(X) = \mathbb{E}[-\log p(X)]$, an average of non-negative numbers, so it is non-negative. The average is zero only if every term is zero, i.e. $p(x) = 1$ for the single symbol in the support.

∎

Equality conditions

Mutual information identities

Proof

Start from $I(X;Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}$ and write $p(x,y) = p(x\vert{}y)p(y)$. The log becomes $\log \frac{p(x\vert{}y)}{p(x)} = -\log p(x) + \log p(x\vert{}y)$. Averaging over $p(x,y)$ gives $H(X) - H(X\vert{}Y)$. Factoring the other way, $p(x,y) = p(y\vert{}x)p(x)$, gives the second line. The third line follows by substituting the chain rule $H(X\vert{}Y) = H(X,Y) - H(Y)$ into the first. The fourth sets $Y = X$, where $H(X\vert{}X) = 0$.

∎

The second law for Markov chains

The data processing inequality looked at one pipeline $X \rightarrow Y \rightarrow Z$. Now suppose a message is relayed through a long chain of identical relay stations, $X_1 \rightarrow X_2 \rightarrow X_3 \rightarrow \cdots$, each with the same transition matrix. What happens to the signal as the number of hops grows? We need one more tool first.

Proof

Write $\frac{p(x,y)}{q(x,y)} = \frac{p(x)}{q(x)} \cdot \frac{p(y\vert{}x)}{q(y\vert{}x)}$, take the log of the product as a sum of logs, and average over $p(x,y)$.

∎

Proof

(1) Let $p$ and $q$ be the joint distributions of $(X_n, X_{n+1})$ under the two starting points. Expand the joint relative entropy with the chain rule in both directions:

$$D(p(x_n, x_{n+1})\vert{}\vert{}q(x_n, x_{n+1})) = D(p(x_n)\vert{}\vert{}q(x_n)) + D(p(x_{n+1}\vert{}x_n)\vert{}\vert{}q(x_{n+1}\vert{}x_n))$$

$$= D(p(x_{n+1})\vert{}\vert{}q(x_{n+1})) + D(p(x_n\vert{}x_{n+1})\vert{}\vert{}q(x_n\vert{}x_{n+1}))$$

Both chains use the same relay, so $p(x_{n+1}\vert{}x_n) = q(x_{n+1}\vert{}x_n)$ and the second term of the first line is $0$. The second term of the second line is a relative entropy, so it is $\ge 0$. Therefore $D(\mu_n\vert{}\vert{}\mu_n') \ge D(\mu_{n+1}\vert{}\vert{}\mu_{n+1}')$.

(2) Take $\mu_n' = \mu$ for all $n$. A stationary distribution is unchanged by the relay, so it is a valid second chain.

(3) With the uniform distribution $u$, we computed in the maximum entropy proof that $D(\mu_n\vert{}\vert{}u) = \log \vert{}\mathcal{X}\vert{} - H(X_n)$. By (2) the left side decreases, so $H(X_n)$ increases.

(4) Chain three facts:

$$H(X_n\vert{}X_1) \ge H(X_n\vert{}X_1, X_2) = H(X_n\vert{}X_2) = H(X_{n-1}\vert{}X_1)$$

Conditioning reduces entropy, then the Markov property (given $X_2$, the older $X_1$ is irrelevant), then stationarity (shift every index by one).

∎

Empirical distributions approach the truth on average

ProofVia convexity of relative entropy

For each $i$, let $\hat{p}^{(i)}$ be the empirical pmf of the $n-1$ samples that remain after deleting $X_i$. Each sample $X_j$ belongs to $n-1$ of these leave-one-out sets, each time with weight $\frac{1}{n-1}$, so averaging them gives back the full frequency table:

$$\frac{1}{n} \sum_{i=1}^n \hat{p}^{(i)} = \hat{p}_n$$

By the convexity of relative entropy (with both $q$‘s equal to $p$):

$$D(\hat{p}_n\vert{}\vert{}p) \le \frac{1}{n} \sum_{i=1}^n D(\hat{p}^{(i)}\vert{}\vert{}p)$$

Take expectations. Each $\hat{p}^{(i)}$ is the frequency table of $n-1$ i.i.d. samples, so it has the same distribution as $\hat{p}_{n-1}$, and the right side becomes $\mathbb{E}\, D(\hat{p}_{n-1}\vert{}\vert{}p)$.

∎

Differential entropy

Real wires do not carry letters, they carry voltages. To reason about continuous signals we replace sums with integrals and probability mass functions with densities $f(x)$. Most of the toolkit survives the move, but not all of it.

Proof

Same as the discrete proofs: $I(X;Y) = h(X) - h(X\vert{}Y) = D(f(x,y)\vert{}\vert{}f(x)f(y)) \ge 0$, and the independence bound follows by applying this term by term in the chain rule.

∎

Proof

$$h(X+Y) \ge h(X+Y\vert{}Y) = h(X\vert{}Y) = h(X)$$

The first step is conditioning reduces entropy. The second holds because, once $Y = y$ is known, $X + Y$ is just $X$ shifted by $y$, and shifting a density does not change its entropy. The third is independence.

∎

Differential entropies of common densities

These come up constantly as reference points. All values are in nats (use $\ln$; divide by $\ln 2$ for bits). Cover & Thomas Table 17.1 lists about twenty more (beta, chi, gamma, Weibull, Student’s $t$, and others).

Distribution	Density	$h$ (nats)
Uniform	$\frac{1}{b-a}$ on $[a, b]$	$\ln(b - a)$
Normal	$\frac{1}{\sqrt{2\pi\sigma^2}} e^{-(x-\mu)^2 / 2\sigma^2}$	$\frac{1}{2}\ln(2\pi e \sigma^2)$
Exponential	$\frac{1}{\lambda} e^{-x/\lambda}$, $x > 0$	$1 + \ln \lambda$
Laplace	$\frac{1}{2\lambda} e^{-\vert{}x - \theta\vert{}/\lambda}$	$1 + \ln(2\lambda)$
Cauchy	$\frac{\lambda}{\pi(\lambda^2 + x^2)}$	$\ln(4\pi\lambda)$
Logistic	$\frac{e^{-x}}{(1 + e^{-x})^2}$	$2$

ProofTwo of the entries

Normal: $-\ln f(X) = \frac{1}{2}\ln(2\pi\sigma^2) + \frac{(X-\mu)^2}{2\sigma^2}$. Taking expectations, $\mathbb{E}[(X-\mu)^2] = \sigma^2$, so $h = \frac{1}{2}\ln(2\pi\sigma^2) + \frac{1}{2} = \frac{1}{2}\ln(2\pi e\sigma^2)$.

Exponential: $-\ln f(X) = \ln\lambda + X/\lambda$ and $\mathbb{E}[X] = \lambda$, so $h = \ln\lambda + 1$.

∎

Notice the normal entry: the entropy of a Gaussian depends only on its variance. Inverting it gives a very useful quantity, the variance a Gaussian would need in order to be exactly as unpredictable as $X$:

The Gaussian maximizes entropy

ProofVia the information inequality

Let $\phi$ be the $\mathcal{N}(0, K)$ density and $f$ the density of $X$. Then

$$0 \le D(f\vert{}\vert{}\phi) = -h(f) - \int f \log \phi$$

The key observation: $\log \phi(x) = -\frac{1}{2} x^T K^{-1} x - \frac{1}{2}\log (2\pi)^n \vert{}K\vert{}$ is a quadratic in $x$, so its average depends only on the second moments of whatever distribution you average it against. Both $f$ and $\phi$ have covariance $K$, so $\int f \log \phi = \int \phi \log \phi = -h(\phi)$. Substituting, $0 \le -h(f) + h(\phi)$, i.e. $h(f) \le h(\phi) = \frac{1}{2}\log(2\pi e)^n \vert{}K\vert{}$. Equality iff $D(f\vert{}\vert{}\phi) = 0$, i.e. $f = \phi$.

∎

More bounds on entropy and relative entropy

One more consequence of Fano

The continuous Fano: estimation error

Fano bounds the error of a machine that guesses a letter. The continuous version bounds the error of a machine that estimates a voltage.

Proof

Without side information. The best constant guess is the mean, so $\mathbb{E}(X - \hat{X})^2 \ge \operatorname{Var}(X)$. By the maximum entropy theorem in one dimension, $h(X) \le \frac{1}{2}\ln(2\pi e \operatorname{Var}(X))$; exponentiating and rearranging gives $\operatorname{Var}(X) \ge \frac{1}{2\pi e}e^{2h(X)}$.

With side information. For each $y$, the same argument applied to the conditional distribution of $X$ given $Y = y$ gives $\mathbb{E}[(X - \hat{X}(y))^2 \mid Y = y] \ge \frac{1}{2\pi e}e^{2h(X\vert{}Y=y)}$. Average over $Y$ and use Jensen on the convex function $e^{2t}$:

$$\mathbb{E}\left[\frac{1}{2\pi e}e^{2h(X\vert{}Y=y)}\right] \ge \frac{1}{2\pi e}e^{2\,\mathbb{E}[h(X\vert{}Y=y)]} = \frac{1}{2\pi e}e^{2h(X\vert{}Y)}$$

∎

Continuity of entropy (the $L_1$ bound)

If two operators have nearly the same letter frequencies, do they have nearly the same entropy? Yes, and we can say exactly how nearly.

ProofVia the concavity of $-t \log t$

Let $f(t) = -t\log t$. It is concave (its second derivative is $-1/t$ up to a positive constant), with $f(0) = f(1) = 0$, so it is positive on $(0,1)$.

Step 1 (one symbol). Consider a chord of $f$ spanning an interval of width $\nu \le \frac{1}{2}$, from $t$ to $t + \nu$. Because $f$ is concave, its slope is steepest at the ends of $[0,1]$, so the chord changes the most when it sits at one end: $t = 0$ or $t = 1 - \nu$. Therefore

$$\vert{}f(t) - f(t + \nu)\vert{} \le \max\{f(\nu), f(1-\nu)\} = -\nu \log \nu$$

(for $\nu \le \frac{1}{2}$ the left end wins).

Step 2 (sum over symbols). Let $r(x) = \vert{}p(x) - q(x)\vert{}$ and $s = \lVert p - q \rVert_1 = \sum_x r(x)$. Each $r(x) \le s \le \frac{1}{2}$, so by the triangle inequality and Step 1,

$$\vert{}H(p) - H(q)\vert{} \le \sum_x \vert{}f(p(x)) - f(q(x))\vert{} \le \sum_x -r(x)\log r(x)$$

Step 3 (normalize). Write $r(x) = s \cdot \frac{r(x)}{s}$, where $r/s$ is a pmf:

$$\sum_x -r(x)\log r(x) = -s\log s + s\, H\!\left(\frac{r}{s}\right) \le -s\log s + s\log\vert{}\mathcal{X}\vert{}$$

using the maximum entropy bound on $H(r/s)$. This equals $-s\log\frac{s}{\vert{}\mathcal{X}\vert{}}$.

∎

Pinsker’s inequality

ProofReduce to a coin, then do calculus

Work in nats.

Binary case. For coins with heads probabilities $p$ and $q$, $\lVert\cdot\rVert_1 = 2\vert{}p - q\vert{}$, so we need $p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} \ge 2(p-q)^2$. Fix $p$ and let $g(q)$ be the left side minus the right side. Then $g(p) = 0$ and

$$g'(q) = -\frac{p}{q} + \frac{1-p}{1-q} + 4(p - q) = (q - p)\left[\frac{1}{q(1-q)} - 4\right]$$

Since $q(1-q) \le \frac{1}{4}$, the bracket is $\ge 0$. So $g' \le 0$ for $q \le p$ and $g' \ge 0$ for $q \ge p$: $g$ has its minimum at $q = p$, where it is $0$.

General case. Let $A = \{x : p_1(x) \ge p_2(x)\}$, $P_1 = p_1(A)$, $P_2 = p_2(A)$. Then $\lVert p_1 - p_2\rVert_1 = 2(P_1 - P_2)$. Apply the log sum inequality separately to the symbols in $A$ and in $A^c$:

$$D(p_1\vert{}\vert{}p_2) \ge P_1\ln\frac{P_1}{P_2} + (1 - P_1)\ln\frac{1-P_1}{1-P_2}$$

This is the binary case with $p = P_1$, $q = P_2$, so it is $\ge 2(P_1 - P_2)^2 = \frac{1}{2}\lVert p_1 - p_2 \rVert_1^2$.

∎

Local behavior: relative entropy near the truth

ProofTaylor expansion

Write $P(x) = Q(x)(1 + \delta(x))$ with $\delta$ small and $\sum_x Q(x)\delta(x) = 0$. Then

$$D(P\vert{}\vert{}Q) = \sum_x Q(x)(1+\delta)\ln(1+\delta) = \sum_x Q(x)\left(\delta + \frac{\delta^2}{2} + O(\delta^3)\right)$$

The linear term vanishes, and $\sum_x Q\delta^2 = \chi^2(P,Q)$.

∎

Inequalities for types

Suppose you record a whole shift of $n$ symbols from the operator. Instead of the exact sequence, look only at its frequency table. The method of types counts sequences by their frequency table, and it turns out that relative entropy is precisely the exponent that governs how surprising a frequency table is.

Proof

A type is determined by the count of each symbol, and each count is one of the $n + 1$ values $0, 1, \ldots, n$.

∎

Proof

Group the product by symbol. With $P = P_{x^n}$, $Q^n(x^n) = \prod_a Q(a)^{nP(a)} = 2^{n\sum_a P(a)\log Q(a)}$, and $\sum_a P(a)\log Q(a) = -H(P) - D(P\vert{}\vert{}Q)$ by the same add-and-subtract trick used in the mismatched collision corollary.

∎

Proof

Upper bound. Under $P^n$, every sequence in $T(P)$ has probability $2^{-nH(P)}$ (previous theorem with $Q = P$). The class’s total probability is at most 1, so $\vert{}T(P)\vert{}2^{-nH(P)} \le 1$.

Lower bound. First, under $P^n$ the class $T(P)$ is the most likely type class. Using $\vert{}T(P)\vert{} = n!/\prod_a (nP(a))!$, for any other type $\hat{P}$:

$$\frac{P^n(T(P))}{P^n(T(\hat{P}))} = \prod_a \frac{(n\hat{P}(a))!}{(nP(a))!}\,P(a)^{n(P(a) - \hat{P}(a))}$$

Using $\frac{m!}{k!} \ge k^{m-k}$ on each factorial ratio, this is at least $\prod_a (nP(a))^{n(\hat{P}(a) - P(a))}P(a)^{n(P(a)-\hat{P}(a))} = n^{n\sum_a(\hat{P}(a) - P(a))} = 1$. Then $1 = \sum_{\hat{P}} P^n(T(\hat{P})) \le \vert{}\mathcal{P}_n\vert{}\, P^n(T(P)) \le (n+1)^{\vert{}\mathcal{X}\vert{}}\vert{}T(P)\vert{}2^{-nH(P)}$.

∎

Proof

$Q^n(T(P)) = \vert{}T(P)\vert{}\cdot 2^{-n(H(P) + D(P\vert{}\vert{}Q))}$. Plug in the two bounds on $\vert{}T(P)\vert{}$.

∎

Combinatorial bounds on entropy

A binary type class is just a binomial coefficient: the number of length-$n$ bit strings with exactly $k = np$ ones is $\binom{n}{np}$. The type bounds above say $\binom{n}{np} \approx 2^{nH(p)}$ up to a polynomial factor. Stirling’s formula pins the factor down to about $\sqrt{n}$.

ProofVia a strong form of Stirling

Use $\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \le n! \le \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n)}$.

Upper bound. Use the upper Stirling bound for $n!$ and the lower one for $(np)!$ and $(nq)!$. The $(\cdot/e)$ powers collapse to $p^{-np}q^{-nq} = 2^{nH(p)}$, leaving

$$\binom{n}{np} \le \frac{e^{1/(12n)}}{\sqrt{2\pi npq}}2^{nH(p)} < \frac{1}{\sqrt{\pi npq}}2^{nH(p)}$$

since $e^{1/(12n)} \le e^{1/12} \approx 1.087 < \sqrt{2}$.

Lower bound. Swap roles: lower Stirling for $n!$, upper for $(np)!$ and $(nq)!$:

$$\binom{n}{np} \ge \frac{1}{\sqrt{2\pi npq}}2^{nH(p)}e^{-\frac{1}{12np} - \frac{1}{12nq}}$$

If $np \ge 1$ and $nq \ge 3$, the exponential is at least $e^{-1/12 - 1/36} = e^{-1/9} \approx 0.8948 > \frac{\sqrt{\pi}}{2} \approx 0.8862$, and $\frac{1}{\sqrt{2\pi npq}}\cdot\frac{\sqrt{\pi}}{2} = \frac{1}{\sqrt{8npq}}$. (The case $np \ge 3$, $nq \le 2$ follows by swapping $p$ and $q$.) The only leftover cases are checked by hand: $\binom{2}{1} = 2 \ge 2$, $\binom{3}{1} = 3 \ge 2.92$, $\binom{4}{2} = 6 \ge 5.66$.

∎

Entropy rates of subsets (Han’s inequality)

The independence bound says the whole is at most the sum of its parts: $h(X_1, \ldots, X_n) \le \sum_i h(X_i)$. Han’s inequality refines this into a whole ladder: the per-symbol entropy of a randomly chosen group of $k$ variables shrinks steadily as the group gets bigger. (Everything below works equally for discrete entropy $H$; we write $h$ to match the text.)

Proof

The last rung, $h_n^{(n)} \le h_{n-1}^{(n)}$. Let $X_{-i}$ denote all variables except $X_i$. For each $i$, peel off $X_i$ last and then drop conditioning:

$$h(X_1, \ldots, X_n) = h(X_{-i}) + h(X_i\vert{}X_{-i}) \le h(X_{-i}) + h(X_i\vert{}X_1, \ldots, X_{i-1})$$

Add these $n$ inequalities. The last terms sum, by the chain rule, to $h(X_1, \ldots, X_n)$:

$$n\,h(X_1, \ldots, X_n) \le \sum_{i=1}^n h(X_{-i}) + h(X_1, \ldots, X_n)$$

Rearranging, $\frac{1}{n}h(X_1, \ldots, X_n) \le \frac{1}{n}\sum_{i=1}^n\frac{h(X_{-i})}{n-1}$, which is $h_n^{(n)} \le h_{n-1}^{(n)}$.

Every other rung. Apply the last-rung result to each $k$-element subset (treating it as a collection of $k$ variables), which gives $h_k^{(k)} \le h_{k-1}^{(k)}$ for that subset. Averaging over all $k$-subsets chosen uniformly preserves the inequality, and the averages are exactly $h_k^{(n)}$ and $h_{k-1}^{(n)}$.

∎

Proof

Take the last-rung inequality from Han’s proof, multiply by $r$, and exponentiate. The exponent on the right is an average, and $e^t$ is convex, so by Jensen (the arithmetic–geometric mean inequality):

$$e^{\frac{r}{n}h(X_1,\ldots,X_n)} \le e^{\frac{1}{n}\sum_i \frac{r\,h(X_{-i})}{n-1}} \le \frac{1}{n}\sum_{i=1}^n e^{\frac{r\,h(X_{-i})}{n-1}}$$

This is $t_n^{(n)} \le t_{n-1}^{(n)}$. Average over subsets exactly as before.

∎

Proof

Last rung. Start from the independence bound $h(X_1, \ldots, X_n) \le \sum_i h(X_i)$ and subtract both sides from $n\,h(X_1, \ldots, X_n)$:

$$(n-1)\,h(X_1, \ldots, X_n) \ge \sum_{i=1}^n \big(h(X_1, \ldots, X_n) - h(X_i)\big) = \sum_{i=1}^n h(X_{-i}\vert{}X_i)$$

Divide by $n(n-1)$: $\frac{1}{n}h(X_1, \ldots, X_n) \ge \frac{1}{n}\sum_i\frac{h(X_{-i}\vert{}X_i)}{n-1}$, which is $g_n^{(n)} \ge g_{n-1}^{(n)}$. Then average over subsets as before.

∎

Proof

$I(X(S); X(S^c)) = h(X(S)) - h(X(S)\vert{}X(S^c))$, so $f_k^{(n)} = h_k^{(n)} - g_k^{(n)}$: a decreasing sequence minus an increasing one.

∎

Entropy and Fisher information

Differential entropy measures how hard a signal is to describe. Fisher information measures how precisely a hidden parameter can be estimated from it. The two turn out to be connected by an exact calculus identity, and that identity powers one of the deepest results in the subject: the entropy power inequality.

For a Gaussian, $f'/f = -(x - \mu)/\sigma^2$, so $J = 1/\sigma^2$: a narrow bell is easy to locate, a wide one is hard.

ProofVia Cauchy–Schwarz on the score

Let $V = \frac{\partial}{\partial\theta}\ln f(X;\theta)$ (the score). Its mean is $\int \frac{\partial f}{\partial\theta}dx = \frac{\partial}{\partial\theta}\int f\,dx = 0$, so $\operatorname{Var}(V) = J(\theta)$. Unbiasedness says $\int T(x)f(x;\theta)dx = \theta$; differentiating in $\theta$ gives $\mathbb{E}[TV] = 1$, and since $\mathbb{E}[V] = 0$ this is $\operatorname{Cov}(T, V) = 1$. By Cauchy–Schwarz, $1 = \operatorname{Cov}(T,V)^2 \le \operatorname{Var}(T)\operatorname{Var}(V)$.

∎

ProofVia the heat equation

Let $Y_t = X + \sqrt{t}Z$ with density $g_t(y)$, the convolution of $f$ with a Gaussian of variance $t$. Differentiating the Gaussian kernel directly shows that $g_t$ solves the heat equation:

$$\frac{\partial g_t}{\partial t} = \frac{1}{2}\frac{\partial^2 g_t}{\partial y^2}$$

Differentiate $h(Y_t) = -\int g_t\ln g_t\,dy$:

$$\frac{\partial}{\partial t}h(Y_t) = -\int\frac{\partial g_t}{\partial t}dy - \int\frac{\partial g_t}{\partial t}\ln g_t\,dy$$

The first term is $-\frac{\partial}{\partial t}\int g_t = 0$. Substitute the heat equation into the second and integrate by parts:

$$-\frac{1}{2}\int\frac{\partial^2 g_t}{\partial y^2}\ln g_t\,dy = -\frac{1}{2}\left[\frac{\partial g_t}{\partial y}\ln g_t\right]_{-\infty}^{\infty} + \frac{1}{2}\int\frac{1}{g_t}\left(\frac{\partial g_t}{\partial y}\right)^2dy$$

The last integral is $\frac{1}{2}J(Y_t)$. The boundary term vanishes: write it as $\frac{\partial_y g_t}{\sqrt{g_t}}\cdot\sqrt{g_t}\ln g_t$; the first factor is square-integrable (its square integrates to the Fisher information) and the second goes to $0$ in the tails because $u\ln u \rightarrow 0$ as $u \rightarrow 0$. (Swapping derivatives and integrals needs a dominated-convergence argument; see Barron.)

∎

ProofStam’s perturbation argument (outline, $n = 1$)

Add independent Gaussian noise of growing variance to both signals: $X_t = X + \sqrt{f(t)}Z_1$ and $Y_t = Y + \sqrt{g(t)}Z_2$, and define

$$s(t) = \frac{2^{2h(X_t)} + 2^{2h(Y_t)}}{2^{2h(X_t + Y_t)}}$$

The EPI is the statement $s(0) \le 1$. As $t \rightarrow \infty$ (with $f, g \rightarrow \infty$) everything becomes Gaussian and $s(\infty) = 1$. With a clever choice of $f$ and $g$, de Bruijn’s identity turns $s'(t)$ into an expression in Fisher informations, and the Fisher information inequality

$$\frac{1}{J(X + Y)} \ge \frac{1}{J(X)} + \frac{1}{J(Y)}$$

shows $s'(t) \ge 0$. So $s$ climbs to $1$, and therefore started at most $1$. The vector case follows by induction (Stam, Blachman).

∎

Since a Gaussian with entropy $h$ has $2^{2h} = 2\pi e\sigma^2$, the EPI can be read as a statement comparing every pair of signals to a Gaussian pair:

Entropy power and the Brunn–Minkowski inequality

The EPI has a geometric twin. Replace “entropy power” with “volume” and “sum of random variables” with “sum of sets”.

Both are endpoints of a single family, indexed by a generalization of entropy.

ProofSketch

Note the density of $X + Y$ is the convolution $f * g$. Take the logarithm of Young’s inequality, rewrite each norm as a Rényi entropy power, and set $\lambda = r'/p'$ (so $1 - \lambda = r'/q'$). Collecting the $C$ constants produces the binary entropy terms. The final algebraic simplification is omitted in the text as well.

∎

Inequalities for determinants

Here is a trick that turns information theory into a matrix-inequality factory. If $X \sim \mathcal{N}(0, K)$ in $\mathbb{R}^n$, then $h(X) = \frac{1}{2}\log(2\pi e)^n\vert{}K\vert{}$. The determinant is a volume, and Gaussian entropy is the log of that volume. So every entropy inequality applied to Gaussians becomes a determinant inequality for free. Throughout, $K$ is a symmetric positive (semi)definite $n \times n$ matrix and $K(i_1, \ldots, i_k)$ is the principal submatrix on those rows and columns.

ProofVia a random switch

Let $X_1 \sim \mathcal{N}(0, K_1)$, $X_2 \sim \mathcal{N}(0, K_2)$, and an independent switch $\theta$ with $\Pr(\theta = 1) = \lambda$, $\Pr(\theta = 2) = 1 - \lambda$. Let $Z = X_\theta$. Then $Z$ has covariance $\lambda K_1 + (1-\lambda)K_2$ but is not Gaussian. Using the maximum entropy theorem, then conditioning reduces entropy:

$$\frac{1}{2}\log(2\pi e)^n\vert{}\lambda K_1 + (1-\lambda)K_2\vert{} \ge h(Z) \ge h(Z\vert{}\theta) = \frac{\lambda}{2}\log(2\pi e)^n\vert{}K_1\vert{} + \frac{1-\lambda}{2}\log(2\pi e)^n\vert{}K_2\vert{}$$

∎

Proof

Let $X \sim \mathcal{N}(0, K)$. The independence bound gives

$$\frac{1}{2}\log(2\pi e)^n\vert{}K\vert{} = h(X_1, \ldots, X_n) \le \sum_{i=1}^n h(X_i) = \sum_{i=1}^n\frac{1}{2}\log 2\pi e K_{ii}$$

with equality iff the $X_i$ are independent, i.e. $K_{ij} = 0$ for $i \ne j$.

∎

Proof

Let $X \sim \mathcal{N}(0, K)$. Since $h(X(S)) = \frac{1}{2}\log(2\pi e)^k\vert{}K(S)\vert{}$ and $k\binom{n}{k} = n\binom{n-1}{k-1}$,

$$h_k^{(n)} = \frac{1}{2}\log 2\pi e + \frac{1}{2n\binom{n-1}{k-1}}\log P_k$$

Han’s inequality says this decreases in $k$, which is the claim.

∎

Proof

Take the exponentiated Han inequality with $r = 2$ (in nats): $e^{2h(X(S))/k} = 2\pi e\,\vert{}K(S)\vert{}^{1/k}$, so $t_k^{(n)} = 2\pi e\,S_k^{(n)}$.

∎

Proof

For Gaussians, $h(X(S)\vert{}X(S^c)) = \frac{1}{2}\log(2\pi e)^k\frac{\vert{}K\vert{}}{\vert{}K(S^c)\vert{}}$ (with $\vert{}K(\emptyset)\vert{} = 1$). Plug this into the conditional Han inequality ($g_k^{(n)}$ increasing).

∎

Proof

Let $(X_1, \ldots, X_n) \sim \mathcal{N}(0, K_n)$. Then

$$h(X_k\vert{}X_{k-1}, \ldots, X_1) = h(X^k) - h(X^{k-1}) = \frac{1}{2}\log 2\pi e\frac{\vert{}K_k\vert{}}{\vert{}K_{k-1}\vert{}}$$

This conditional entropy is decreasing in $k$:

$$h(X_k\vert{}X_{k-1}, \ldots, X_1) = h(X_{k+1}\vert{}X_k, \ldots, X_2) \ge h(X_{k+1}\vert{}X_k, \ldots, X_1)$$

(Toeplitz means the process is stationary, so shifting indices changes nothing; then conditioning reduces entropy.) A decreasing sequence has decreasing running averages, and the running average is $\frac{1}{k}h(X_1, \ldots, X_k) = \frac{1}{2}\log 2\pi e\,\vert{}K_k\vert{}^{1/k}$, which gives the chain. Finally, a convergent sequence and its running averages (Cesàro means) have the same limit, which gives the last line.

∎

Proof

Let $X_1 \sim \mathcal{N}(0, K_1)$ and $X_2 \sim \mathcal{N}(0, K_2)$ be independent, so $X_1 + X_2 \sim \mathcal{N}(0, K_1 + K_2)$. Apply the EPI:

$$(2\pi e)\vert{}K_1 + K_2\vert{}^{1/n} = 2^{\frac{2}{n}h(X_1 + X_2)} \ge 2^{\frac{2}{n}h(X_1)} + 2^{\frac{2}{n}h(X_2)} = (2\pi e)\left(\vert{}K_1\vert{}^{1/n} + \vert{}K_2\vert{}^{1/n}\right)$$

(Here $h$ is in bits, so $2^{2h/n} = (2\pi e)\vert{}K\vert{}^{1/n}$.)

∎

Inequalities for ratios of determinants

Proof

Given the past, $X_n$ is Gaussian with a mean that is linear in the past and a variance $\sigma_n^2$ that does not depend on the past values. So

$$\frac{1}{2}\log 2\pi e\sigma_n^2 = h(X_n\vert{}X_1, \ldots, X_{n-1}) = h(X_1, \ldots, X_n) - h(X_1, \ldots, X_{n-1}) = \frac{1}{2}\log 2\pi e\frac{\vert{}K_n\vert{}}{\vert{}K_{n-1}\vert{}}$$

∎

Minimizing prediction error over a set of allowed covariance matrices comes up in maximum entropy spectral estimation, which makes concavity of these ratios useful.

ProofVia a random switch

Ky Fan does not apply directly, since this is a difference of two concave functions. Instead, let $X_1 \sim \mathcal{N}(0, S_n)$, $X_2 \sim \mathcal{N}(0, T_n)$, an independent switch $\theta$ with $\Pr(\theta = 1) = \lambda$, and $Z = X_\theta$, so $K_n = \lambda S_n + (1-\lambda)T_n$. Write $Z_{\text{last}}$ for the last $p$ coordinates and $Z_{\text{first}}$ for the first $n - p$. Then

$$\lambda\frac{1}{2}\log(2\pi e)^p\frac{\vert{}S_n\vert{}}{\vert{}S_{n-p}\vert{}} + (1-\lambda)\frac{1}{2}\log(2\pi e)^p\frac{\vert{}T_n\vert{}}{\vert{}T_{n-p}\vert{}} = h(Z_{\text{last}}\vert{}Z_{\text{first}}, \theta)$$

$$\le h(Z_{\text{last}}\vert{}Z_{\text{first}}) \le \frac{1}{2}\log(2\pi e)^p\frac{\vert{}K_n\vert{}}{\vert{}K_{n-p}\vert{}}$$

The equality uses $h(\text{last}\vert{}\text{first}) = h(\text{all}) - h(\text{first})$ for each Gaussian; then conditioning reduces entropy; then a conditional version of the maximum entropy theorem.

∎

ProofVia a sum of independent Gaussians

Let $X \sim \mathcal{N}(0, A_n)$ and $Y \sim \mathcal{N}(0, B_n)$ be independent and $Z = X + Y$. Then

$$\frac{1}{2}\log 2\pi e\frac{\vert{}A_n + B_n\vert{}}{\vert{}A_{n-1} + B_{n-1}\vert{}} = h(Z_n\vert{}Z_{n-1}, \ldots, Z_1)$$

$$\ge h(Z_n\vert{}Z_{n-1}, \ldots, Z_1, X_{n-1}, \ldots, X_1, Y_{n-1}, \ldots, Y_1) = h(X_n + Y_n\vert{}X^{n-1}, Y^{n-1})$$

$$= \frac{1}{2}\log 2\pi e\left(\operatorname{Var}(X_n\vert{}X^{n-1}) + \operatorname{Var}(Y_n\vert{}Y^{n-1})\right) = \frac{1}{2}\log 2\pi e\left(\frac{\vert{}A_n\vert{}}{\vert{}A_{n-1}\vert{}} + \frac{\vert{}B_n\vert{}}{\vert{}B_{n-1}\vert{}}\right)$$

Steps: the prediction-error lemma; conditioning reduces entropy; $Z$‘s past is a function of the $X$ and $Y$ pasts; given the pasts, $X_n + Y_n$ is Gaussian with the two conditional variances adding (independence); the prediction-error lemma again (conditional variances of Gaussians do not depend on the conditioning values, so no expectation is needed). Drop the logs, then set $A = \lambda S$ and $B = (1-\lambda)T$; the ratio of an $n \times n$ to an $(n-1) \times (n-1)$ determinant scales linearly, so

$$\frac{\vert{}\lambda S_n + (1-\lambda)T_n\vert{}}{\vert{}\lambda S_{n-1} + (1-\lambda)T_{n-1}\vert{}} \ge \lambda\frac{\vert{}S_n\vert{}}{\vert{}S_{n-1}\vert{}} + (1-\lambda)\frac{\vert{}T_n\vert{}}{\vert{}T_{n-1}\vert{}}$$

∎

The big picture

Chapter 17 closes with a one-line summary of every major result in the book. Most of these live in other notes; this is the map.

Problems

Proof

Let $X_1 \sim \mathcal{N}(0, K_1)$ and $X_2 \sim \mathcal{N}(0, K_2)$ be independent. By the “adding noise cannot sharpen” lemma, $h(X_1 + X_2) \ge h(X_1)$, i.e. $\frac{1}{2}\log(2\pi e)^n\vert{}K_1 + K_2\vert{} \ge \frac{1}{2}\log(2\pi e)^n\vert{}K_1\vert{}$.

∎

Proof

Let $X \sim \mathcal{N}(0, K)$ and $W = (X_{p+1}, \ldots, X_n)$. Using $h(\text{some}\vert{}W) = h(\text{some}, W) - h(W)$ for Gaussians:

$$\frac{1}{2}\log(2\pi e)^p\frac{\vert{}K\vert{}}{\vert{}K(p+1, \ldots, n)\vert{}} = h(X_1, \ldots, X_p\vert{}W) \le \sum_{i=1}^p h(X_i\vert{}W) = \sum_{i=1}^p\frac{1}{2}\log 2\pi e\frac{\vert{}K(i, p+1, \ldots, n)\vert{}}{\vert{}K(p+1, \ldots, n)\vert{}}$$

The inequality is the (conditional) independence bound. Exponentiate.

∎

ProofVia second derivatives

Let $\phi(K) = \ln\vert{}K + K_0\vert{} - \ln\vert{}K\vert{}$ and move along a symmetric direction $D$: $K + tD$. A standard identity gives $\frac{d^2}{dt^2}\ln\vert{}M + tD\vert{} = -\operatorname{tr}\big((M^{-1}D)^2\big)$ at $t = 0$. So, with $A = K^{-1}$ and $B = (K + K_0)^{-1}$,

$$\frac{d^2}{dt^2}\phi = \operatorname{tr}(ADAD) - \operatorname{tr}(BDBD)$$

Since $K \preceq K + K_0$, we have $A \succeq B \succeq 0$. Then

$$\operatorname{tr}(ADAD) - \operatorname{tr}(BDBD) = \operatorname{tr}\big((A-B)DAD\big) + \operatorname{tr}\big((A-B)DBD\big) \ge 0$$

because $A - B$, $DAD$ and $DBD$ are all positive semidefinite, and the trace of a product of two PSD matrices is non-negative. A non-negative second derivative along every line means convexity.

Information-theoretic reading: with $Z \sim \mathcal{N}(0, K_0)$ and independent noise $X \sim \mathcal{N}(0, K)$, $\frac{1}{2}\ln\frac{\vert{}K + K_0\vert{}}{\vert{}K\vert{}} = h(Z + X) - h(X) = I(Z; Z + X)$, the information a Gaussian signal gets through Gaussian noise of covariance $K$. The claim is that this is convex in the noise covariance.

∎

Proof

Since $X_1 \rightarrow X_3 \rightarrow X_4$, expanding $I(X_1; X_3, X_4)$ both ways (as in the DPI proof) gives $I(X_1; X_3) - I(X_1; X_4) = I(X_1; X_3\vert{}X_4)$. Likewise $I(X_2; X_3) - I(X_2; X_4) = I(X_2; X_3\vert{}X_4)$. So we need $I(X_1; X_3\vert{}X_4) \le I(X_2; X_3\vert{}X_4)$.

A Markov chain reversed is still Markov, and conditioned on $X_4$ the variables still form a chain $X_3 \rightarrow X_2 \rightarrow X_1$. The data processing inequality, applied conditionally on $X_4$, gives exactly that. Rearranging finishes the proof.

∎

Proof

By the data processing inequality and the chain rule,

$$I(X; Y) \ge I(X; Z, W) = I(X; Z) + I(X; W\vert{}Z)$$

And by the chain rule twice, $I(X; W\vert{}Z) = I(X, Z; W) - I(Z; W) \ge I(X; W) - I(Z; W)$. Combine the two lines.

∎