Information theory

Definition. The entropy of a random variable X with a probability mass function $p(x)$ is defined by

$$H(x) = -\sum_{x} p(x) \log_2 p(x)$$

Definition. Let $X$ be a discrete r.v. with pmf $P_X(x), x \in \mathcal{X}$. For the event $X=x$, the self-information is

$$I(x) = -\log P_X(x)$$

The entropy is the average of the self-information

$$H(x) = -\sum_{x \in \mathcal{X}} P_X(x) \cdot \log_2 P_X(x) = E\left[\log_2 \frac{1}{P_X(x)}\right]$$

Remark. $1^\circ$ $I(x) \ge 0$, since $0 \le P_X(x) \le 1$

$2^\circ$ $H(X) \le \log \vert{}\mathcal{X}\vert{}$

Proof.

$\log$ is concave function and $H(x) = E\left[\log_2 \frac{1}{P_X(x)}\right]$

By Jensen inequality

$$E\left[\log_2 \frac{1}{P_X(x)}\right] \le \log_2 \left( E\left[\frac{1}{P_X(x)}\right] \right) = \log_2 \left( \sum_{x \in \mathcal{X}} P_X(x) \cdot \frac{1}{P_X(x)} \right) = \log_2 \vert{}\mathcal{X}\vert{}$$

$3^\circ$ let $X = \begin{pmatrix} 1 & 0 \\ p & 1-p \end{pmatrix}$, $H(x) = -p \log_2 p - (1-p) \log_2 (1-p)$

$4^\circ$ $H(X)$ depends on the pmf of X

$5^\circ$ $H(X)$ is a concave function of $P_X$, proof need conditional entropy

Definition. joint entropy $H(X, Y)$ of a pair of discrete r.v. $X, Y$ with joint distribution $p(x, y)$ is defined as

$$H(X, Y) = -\sum_{x}\sum_{y} p(x, y) \log p(x, y) = E\left[\log \frac{1}{p(X,Y)}\right]$$

Definition. the conditional entropy $H(Y\vert{}X)$ is defined as

$$H(Y\vert{}X) = \sum_{x} p(x) \cdot H(Y\vert{}X=x) = -\sum_{x} p(x) \cdot \sum_{y} p(y\vert{}x) \log p(y\vert{}x) = -\sum_{x}\sum_{y} p(x, y) \log p(y\vert{}x) = E\left[\log \frac{1}{p(Y\vert{}X)}\right]$$

Theorem 1. $H(X,Y) = H(X) + H(Y\vert{}X)$

Proof.

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

$$= -\sum_{x}\sum_{y} p(x,y) \log p(x) - \sum_{x}\sum_{y} p(x,y) \log p(y\vert{}x)$$

$$= H(X) + H(Y\vert{}X)$$

So $H(X_1 \dots X_n) = \sum_{i=1}^n H(X_i \vert{} X_1 \dots X_{i-1})$

Theorem 2. $H(X\vert{}Y) \le H(X)$

Proof.

$$H(X\vert{}Y) - H(X) = -\sum_{x}\sum_{y} p(x,y) \log p(x\vert{}y) + \sum_{x} p(x) \log p(x)$$

$$= \sum_{x}\sum_{y} p(x,y) \log p(x) - \sum_{x}\sum_{y} p(x,y) \log p(x\vert{}y)$$

$$= \sum_{x}\sum_{y} p(x,y) \log \frac{p(x)}{p(x\vert{}y)} = \sum_{x}\sum_{y} p(x,y) \log \frac{p(x)p(y)}{p(x,y)}$$

since $\log z \le z - 1$

$$\le \sum_{x}\sum_{y} p(x,y) \left( \frac{p(x)p(y)}{p(x,y)} - 1 \right) = \sum_{x}\sum_{y} p(x)p(y) - \sum_{x}\sum_{y} p(x,y) = 1 - 1 = 0$$

So $H(X\vert{}Y) \le H(X)$

Theorem 3. $H(X)$ is concave of the probability

Proof.

Let $X_1 \sim P_1, X_2 \sim P_2$. $\theta \in \{1, 2\}$ s.t. $P(\theta=1) = \lambda$, $P(\theta=2) = 1-\lambda$

define $Z = X_\theta$ by theorem 2

$$H(Z) \ge H(Z\vert{}\theta)$$

$Z = \lambda X_1 + (1-\lambda) X_2$ so the probability of Z is $\lambda P_1 + (1-\lambda) P_2$

So $H(\lambda P_1 + (1-\lambda) P_2) \ge \lambda H(P_1) + (1-\lambda) H(P_2)$

Definition (KL distance). KL distance between two pmf $p(x), q(x)$ is defined as

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

$$D(p\vert{}\vert{}q) = -\sum_{x} p(x) \ln \frac{q(x)}{p(x)} \ge -\sum_{x} p(x) \left( \frac{q(x)}{p(x)} - 1 \right) = -\sum_{x} (q(x) - p(x)) = 0$$

Definition. $D(p(x,y) \vert{}\vert{} p(x)p(y)) = \sum_{x}\sum_{y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}$

By the proof of theorem 2

$$I(X; Y) = D(p(x,y) \vert{}\vert{} p(x)p(y)) \ge 0$$

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

if X, Y independent $I(X; Y) = 0$

Theorem 2. Chain rule for information

$$I(X_1, X_2 \dots X_n; Y) = \sum_{i=1}^n I(X_i; Y \vert{} X_1 \dots X_{i-1})$$

Proof.

$$I(X_1, X_2 \dots X_n; Y) = H(X_1, X_2 \dots X_n) - H(X_1, X_2 \dots X_n \vert{} Y)$$

$$= \sum_{i=1}^n H(X_i \vert{} X_1 \dots X_{i-1}) - \sum_{i=1}^n H(X_i \vert{} X_1 \dots X_{i-1}, Y)$$

$$= \sum_{i=1}^n I(X_i; Y \vert{} X_1 \dots X_{i-1})$$

Theorem 3. (Jensen’s inequality)

If f is a convex function and X is r.v.

$$E(f(X)) \ge f(E(X))$$

and if f is strictly convex then equality holds means $X = E(X) \Rightarrow X$ is constant

Proof.

The case $n = 2$ is the convexity of $f$: for $P_1, P_2 \ge 0$ with $P_1 + P_2 = 1$ $$P_1 f(x_1) + P_2 f(x_2) \ge f(P_1 x_1 + P_2 x_2)$$

Assume the inequality holds for $n = k-1$. Set $p_i' = \frac{p_i}{1-p_k}$, then $p_1' + \dots + p_{k-1}' = 1$, so the $k-1$ version of the inequality to be proved is $$\sum_{i=1}^{k-1} p_i' f(x_i) \ge f\left( \sum_{i=1}^{k-1} p_i' x_i \right)$$

For $n = 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)$$

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

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

Theorem 4.

Let p, q be two pmf, then $D(p\vert{}\vert{}q) \ge 0$ with an equality if $p(x) = q(x) \quad \forall x \in \mathcal{X}$

Proof.

$$D(p\vert{}\vert{}q) = \sum_{x} p(x) \log \frac{p(x)}{q(x)} = -\sum_{x} p(x) \log \frac{q(x)}{p(x)} \ge -\log \left( \sum_{x} q(x) \right) = 0$$

by Jensen inequality

So $I(X; Y) = D(p(x,y) \vert{}\vert{} p(x)p(y)) \ge 0$

Theorem 5.

$$H(X) \le \log \vert{}\mathcal{X}\vert{}$$

Proof.

set $u(x) = \frac{1}{\vert{}\mathcal{X}\vert{}}$

$$D(p\vert{}\vert{}u) = \sum_{x} p(x) \log \frac{p(x)}{u(x)} = \sum_{x} p(x) \log p(x) + \sum_{x} p(x) \log \vert{}\mathcal{X}\vert{}$$

$$= \log \vert{}\mathcal{X}\vert{} - H(X) \ge 0$$

So $H(X) \le \log \vert{}\mathcal{X}\vert{}$

Theorem 6. Log Sum Inequality

$$\sum_{i=1}^n a_i \log \frac{a_i}{b_i} \ge \left( \sum_{i=1}^n a_i \right) \log \frac{\sum_{i=1}^n a_i}{\sum_{i=1}^n b_i}$$

Proof.

$t \log t$ is convex function, let $\alpha_i = \frac{b_i}{\sum b_i}$ then by Jensen Inequality

$$f\left(\sum_{i=1}^n \alpha_i t_i\right) \le \sum_{i=1}^n \alpha_i f(t_i)$$

let $t_i = \frac{a_i}{b_i}$

$$\left( \sum \frac{a_i}{\sum b_i} \right) \log \left( \frac{\sum a_i}{\sum b_i} \right) \le \sum_{i=1}^n \frac{b_i}{\sum b_i} \frac{a_i}{b_i} \log \frac{a_i}{b_i}$$

$$\Rightarrow \left( \sum a_i \right) \log \left( \frac{\sum a_i}{\sum b_i} \right) \le \sum_{i=1}^n a_i \log \frac{a_i}{b_i}$$

Theorem 7.

Convexity of Relative Entropy

$(p_1, q_1) \quad (p_2, q_2) \quad 0 \le \lambda \le 1$

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

Proof.

$$\sum_{x} [\lambda p_1(x) + (1-\lambda) p_2(x)] \log \frac{\lambda p_1(x) + (1-\lambda) p_2(x)}{\lambda q_1(x) + (1-\lambda) q_2(x)}$$

$$\le \sum_{x} \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)}$$

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

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

Theorem 8. Convexity of Mutual Information

(1) Concave of $p(x)$ for fixed $p(y\vert{}x)$ (2) Convex of $p(y\vert{}x)$ for fixed $p(x)$

Proof.

(1)

$$I(X; Y) = H(Y) - H(Y\vert{}X)$$

$$H(Y\vert{}X) = \sum_{x} p(x) \cdot H(Y\vert{}X=x) \text{, since } p(y\vert{}x) \text{ is fix so } H(Y\vert{}X=x) \text{ is fix}$$

So $H(Y\vert{}X)$ is the linear combination of $p(x)$

$$H(Y) = \sum_{y} p(y) \log \frac{1}{p(y)} \text{, } p(y) = \sum_{x} p(x) p(y\vert{}x) \text{ so } p(y) \text{ is linear combination of } p(x)$$

$H(Y)$ is concave for $p(y)$ so is concave for $p(x)$

So $I(X; Y)$ is concave for $p(x)$

(2) $I(X; Y) = D(p(x,y) \vert{}\vert{} p(x)p(y))$

$\forall p_0(y\vert{}x), p_1(y\vert{}x) \quad p_\lambda(y\vert{}x) = \lambda p_0(y\vert{}x) + (1-\lambda) p_1(y\vert{}x) \quad \lambda \in (0,1)$

$$p_\lambda(x,y) = p(x) \cdot p_\lambda(y\vert{}x) = p(x) \cdot (\lambda p_0(y\vert{}x) + (1-\lambda) p_1(y\vert{}x)) = \lambda p_0(x,y) + (1-\lambda) p_1(x,y)$$

$$p_\lambda(x) p_\lambda(y) = p(x) \cdot \sum_{x} p_\lambda(x,y) = p(x) \cdot \sum_{x} p(x) \cdot p_\lambda(y\vert{}x) = p(x) \cdot (\lambda p_0(y) + (1-\lambda) p_1(y))$$

$$I_\lambda(X; Y) = D(\lambda p_0(x,y) + (1-\lambda) p_1(x,y) \vert{}\vert{} \lambda p(x)p_0(y) + (1-\lambda) p(x)p_1(y)) \le \lambda I_0 + (1-\lambda) I_1$$

Definition. Markov Chain

r.v. X Y Z s.t. $p(x,y,z) = p(x) p(y\vert{}x) p(z\vert{}y)$

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

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

Theorem 9. (Data Processing Inequality)

$X \rightarrow Y \rightarrow Z$ is a Markov Chain. Then $I(X; Y) \ge I(X; Z)$

Proof.

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

Since $p(x,z\vert{}y) = p(x\vert{}y) \cdot p(z\vert{}y)$ so $I(X; Z\vert{}Y) = 0$

and $I(X; Y\vert{}Z) \ge 0$ so

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

Corollary 1. if $Z = g(Y)$ then $X \rightarrow Y \rightarrow g(Y)$

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

Corollary 2. if $X \rightarrow Y \rightarrow Z$ then

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

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

and $I(X; Z) \ge 0$ so $I(X; Y\vert{}Z) \le I(X; Y)$

Definition. sufficient statistic

For Markov Chain $\theta \rightarrow X \rightarrow T(X)$ if

$I(\theta; T(X)) = I(\theta; X)$ then T is sufficient statistic

which $I(\theta; X \vert{} T(X)) = 0 \Rightarrow \theta \rightarrow T(X) \rightarrow X$ is Markov Chain