Information Theory Inequalities

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.

∎

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])$

∎

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

∎

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

∎

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

∎

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

∎

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

∎

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}$

∎

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)$

∎

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)$

∎

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)$

∎

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 remaining symbols in the alphabet. The absolute maximum uncertainty of any variable is the log of its total possible outcomes. We can 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 that $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 inequality onto the end of our proof to finish it: $H(P_e) + P_e \log |\mathcal{X}| \ge H(X|\hat{X}) \ge H(X|Y)$

∎

We want to bound $\sum p^2(x)$. Let’s rewrite this cleverly to look like an Expected Value. The expected value of the probability itself is: $\mathbb{E}[p(X)] = \sum p(x) p(x) = \sum p^2(x)$. Now, notice that $p(x)$ can be rewritten using logs as $2^{\log p(x)}$. Therefore, our collision probability is $\mathbb{E}[2^{\log p(X)}]$.

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

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

Look at the exponent on the right side: $\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)}$

∎