Basic Entropy Inequalities

Let $X$ and $Y$ be two discrete random variables.

Relative Entropy

Given a distribution $p$, if we encode it with a distribution $q$ (with the same support), the expected coding length is roughly

The cost over the optimal coding is given by

By definition, we know that this gap is always non-negative. We can prove it rigorously algebraically. We show two different approaches here.

1. By that $f(x) = x \log x$ is convex for $x \ge 0$, we have$$\begin{aligned} \mathbf{D}(p || q) &= \sum_i p_i \log \frac{p_i}{q_i} \\ &= \sum_i q_i \cdot \frac{p_i}{q_i} \log \frac{p_i}{q_i} \\ &\ge \left( \sum_i q_i \cdot \frac{p_i}{q_i} \right) \log \left( \sum_i q_i \cdot \frac{p_i}{q_i} \right) \\ &= 0 \end{aligned}$$
2. By that $f(x) = -\log x$ is convex (for $x \ge 0$ ), we have$$\begin{aligned} \mathbf{D}(p || q) &= \sum_i - p_i \log \frac{q_i}{p_i} \\ &\ge -\log \left( \sum_i p_i \cdot \frac{q_i}{p_i} \right) \\ &= 0 \end{aligned}$$

Theorem (Maximum Value). Let $X$ be a random variable taking values in an alphabet $\Omega$. Then

$$\mathbf{H}(X) \le \log | \Omega |$$

The inequality is saturated if and only if $X$ is a uniform random variable on $\Omega$.

Proof. Let $U$ be a uniform random variable on $\Omega$. Then

$\square$

Joint Entropy

Definition. The joint entropy of $X$ and $Y$ is

$$\mathbf{H}(X, Y) = \sum_{x, y} p(x, y) \log \frac{1}{ p(x, y) }$$

If $X$ and $Y$ are independent, then

Conditional Entropy

Definition. The conditional entropy of $X$ given $Y = y$ is the entropy of the probability distribution $p(X \mid Y = y)$

$$\mathbf{H}(X \mid Y = y) = \sum_x p(x \mid y) \log \frac{1}{ p(x \mid y) }$$

Definition. The conditional entropy of $X$ given $Y$, is the average, over $y$, the conditional entropy of $X$ given $y$

$$\mathbf{H}(X \mid Y) = \sum_y p(y) \mathbf{H}(X \mid Y = y) = \sum_{x, y} p(x , y) \log \frac{1}{ p(x \mid y) }.$$

Theorem (Zero Conditional Entropy). Suppose that $X$ and $Y$ have the same support. $\mathbf{H}(X \mid Y) = 0$ if and only if $X$ is a function of $Y$.

Proof. If

Then either $p(y) = 0$ or $\mathbf{H}(X \mid Y = y) = 0$ for all $y$. On the other hand, for each $y$, if $p(y) > 0$, then

Then either $p(x \mid y) = 0$ or $\log \frac{1}{ p(x \mid y) } = 0$. It follows that there is a unique $x$, for which $p(x \mid y) = 1$.

Conversely, if $X$ is a function of $Y$, for each $y$ such that $p(y) > 0$, there is a unique $x$ such that $p(x \mid y) = 1$. Hence, $\mathbf{H}(X \mid Y = y) = 0$ and $H(X \mid Y) = 0$.

$\square$

Mutual Information

Definition. The mutual information between $X$ and $Y$ is

$$I(X; Y) = \mathbb{E}_{p(x, y) } \left[ \log \frac{ p(x, y)}{p(x) p(y) } \right] = \mathbf{D}( p(x, y) \Vert p(x) p(y) ).$$

The definition is symmetric and it holds that $I(X; Y) = I(Y; X)$. If we know $p(x,y)$, we use in expectation $\mathbb{E}_{p(x, y) } \left[ \log \frac{1} { p(x, y)} \right]$ bits to describe them. If we know only $p(x)$ and $p(y)$, the mutual information measures the bits we waste.

Further, mutual information measures the average reduction of randomness of $X$ that results from learning the value of $Y$.

In this sense, the mutual information quantifies the dependence between $X$ and $Y$. It measures how much knowing one random variable reduces the uncertainty about the other random variable.

Similarly, we can prove that

$\mathbf{I}(X; Y) \ge 0$.

Proof.

Or

$\square$

Corollary. $\mathbf{H} ( Y ) - \mathbf{H} ( X \mid Y) = \mathbf{H} ( X ) - \mathbf{H} ( X \mid Y) \ge 0$.

Theorem. The entropy $\mathbf{H}(X)$ is concave in the probability density $p(x)$.

Proof. Let $\lambda_1, \lambda_2 \in [0, 1]$ such that $\lambda_1 + \lambda_2 = 1$. Suppose that $Z_1, Z_2$ are random variables with density functions $p_1(z)$ and $p_2(z)$ respectively. Define the random variable

and let $X = Z_Y$.

Then

On the other hand,

We finish the proof by observing that $\mathbf{H}(X) \ge \mathbf{H}(X \mid Y)$.

$\square$

Definition. Let $X$ be a Bernoulli random variable with mean $p \in [0, 1]$. Denote $\mathbf{H}(p) = \mathbf{H}(X) = p \log \frac{1}{p} + (1 - p) \log \frac{1}{1 - p}$.
Corollary. $\mathbf{H}(p)$ is concave in $p$.

Conditional Mutual Information

Definition. The conditional mutual information between $X$ and $Y$ given $Z = z$ is the mutual information between the random variables $X$ and $Y$ in the joint ensemble $\Pr (X, Y | Z = z)$,

$$I(X ; Y \mid Z = z) = \mathbf{H}(X \mid Z = z) - \mathbf{H}(X \mid Y, Z = z)$$

Definition. The conditional mutual information between $X$ and $Y$ given $Z$ is average over $z$ of $I(X; Y \mid Z = z)$,

$$\begin{aligned} I(X; Y \mid Z) &= \mathbf{H}(X \mid Z) - \mathbf{H}(X \mid Y, Z) \\ &= \mathbf{H}(Y \mid Z) - \mathbf{H}(Y \mid X, Z) \\ &= \mathbf{H}(X \mid Z) + \mathbf{H}(Y \mid Z) - \mathbf{H}(X, Y \mid Z) \\ &= \mathbb{E}_{X, Y, Z} \log \frac{ p(X, Y \mid Z )}{ p(X \mid Z) \cdot p(Y \mid Z)}. \end{aligned}$$

Conditional Relative Entropy

Definition (Conditional Relative Entropy).

$$\begin{aligned} \mathbf{D}( p(y \mid x) || q(y \mid x) ) &\doteq \mathbb{E}_{p(x, y) } \left[ \log \frac{ p(Y \mid X) }{ q(Y \mid X) } \right]\\ &=\sum_{x} \sum_{ y } p(y \mid x) \log \frac{ p(y \mid x) }{ q(y \mid x) } \end{aligned}$$

Lemma. Relative entropy $\mathbf{D}( p || q )$ is convex in the pair $(p, q)$: if there are two distribution pairs $(p_1, q_1)$ and $(p_2, q_2)$, then for $\alpha_1, \alpha_2 \in [0, 1]$, s.t., $\alpha_1 + \alpha_2 = 1$, it holds that

$$\mathbf{D}( \alpha_1 p_1 + \alpha_2 p_2 || \alpha_1 q_1 + \alpha_2 q_2 ) \le \alpha_1 \mathbf{D}( p_1 || q_1 ) + \alpha_2 \mathbf{D}( p_2 || q_2 )$$

Proof. For any fix value $x$, let $s(x)$ be a shorthand for $\alpha_1 p_1(x) + \alpha_2 p_2(x)$. It holds that

$\square$

Chain Rules

Chain Rule for Information Content

$\log \frac{1}{ p(x, y) } = \log \frac{1}{p(x) } + \log \frac{1}{p(y | x) }$.

Chain Rule for Entropy

Let $X_1, \ldots, X_n$ be random variables whose density function is $p(x_1 \ldots, x_n)$.

$\mathbf{H}(X_1, \ldots, X_n) = \sum_{i = 1}^n \mathbf{H}(X_i \mid X_1, \ldots, X_{i - 1})$

Proof.

$\square$

Corollary. $ \mathbf{H} ( X_1, \ldots, X_n) \le \sum_{i = 1}^n \mathbf{H}(X_i). $

$\square$

Chain Rule for Mutual Information

$\mathbf{I}(Y; X_1, \ldots, X_n) = \sum_{i = 1}^n \mathbf{I}( Y; X_i \mid X_1, \ldots, X_{i - 1})$

Proof 1.

$\square$

Proof 2.

$\square$

Convexity of Relative Entropy.

$$\mathbf{D}( p(x, y) || q(x, y) ) = \mathbf{D}( p(x) || q(x) ) + \mathbf{D}( p(y \mid x) || q(y \mid x) ).$$

Proof.

$\square$