Entropy and Mutual Information

Entropy

$$H(X) = -\sum_x p(x) \log p(x) = E_p\left[\log \frac{1}{p(X)}\right]$$ $$H(X, Y) = -\sum_x \sum_y p(x,y) \log p(x,y), \qquad H(Y | X) = \sum_x p(x) H(Y | X = x) = -\sum_x \sum_y p(x,y) \log p(y | x)$$ $$H(X, Y) = H(X) + H(Y | X) = H(Y) + H(X | Y)$$

• $H(X) \ge 0$, 0 on the corners, $\log|\mathcal{X}|$ for the uniform.
• $H(X) \le \log |\mathcal{X}|$.
• Concave with respect to $p$.
• $H(X | Y) \le H(X)$.
• Chain rule, $H(X_1, \ldots, X_n) = \sum_{i=1}^{n} H(X_i | X_{i-1}, \ldots, X_1) \le \sum_{i=1}^{n} H(X_i)$, with equality iff the $X_i$ are independent.

Relative Entropy and Mutual Information

$$D(p \,\|\, q) = \sum_x p(x) \log \frac{p(x)}{q(x)}$$ $$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X,Y) = D\big(p(x,y) \,\|\, p(x)p(y)\big)$$ $$I(X;Y|Z) = H(X|Z) - H(X|Y,Z), \qquad I(X_1, \ldots, X_n; Y) = \sum_{i=1}^{n} I(X_i; Y | X_{i-1}, \ldots, X_1)$$

Asymptotic Equipartition Property

$\frac{1}{n}\sum x_i \to E[X]$, and for an observed iid sequence $X_1, \ldots, X_n$,

$$\frac{1}{n} \log \frac{1}{p(X_1, \ldots, X_n)} \to H(X) \quad \text{in probability}$$

so $p(X_1, \ldots, X_n) \approx 2^{-nH(X)}$.

Source Coding

For a uniquely decodable $D$-ary code with lengths $l_i$, the expected length satisfies

$$L \ge H_D(X) = \frac{H(X)}{\log D}$$

with equality only if $p_i = D^{-l_i}$.