Information Theory 定理总结及推导

Chapter 1 Information Theory for Discrete Variables

(1) Message Sets

What is a message? Shannon suggested that a message has to do with choice and sets. In his words: The significant aspect is that the actual message is one selected from a set of possible messages.

(2) Measuring Choice

Shannon was interested in defining a quantity that will measure, in some sense, how much information is “produced” by choosing messages. He suggested that the logarithm of the number of elements in the message set can be regarded as a measure of the information produced when one message is chosen from the set, all choices being equally likely.

For example, consider a fair coin that takes on values in $\{Heads,Tails\}$$\{Heads, Tails\}$ and suppose we flip the coin $n$$n$ times. The string of coin flips takes on one of $2^n$$2^n$ values, all equally likely, and the information produced is ${\log }_2{2}^n=nbits.$$\log_2{2^n}=n \ bits.$

For non-equally likely choices, Shannon developed a measure that has the same form as the entropy in statistical mechanics. For example, consider a biased coin that takes on the value Heads with probability $p$$p$ and Tails with probability $1-p$$1-p$. The string of coin flips takes on $(\genfrac{}{}{0ex}{}{n}{np})$$n\choose np$ values (since the expected number of Heads is $np$$np$). Shannon proposed that the information produced when flipping the coin $n$$n$ times is

(3) Entropy

Let $supp(f)$$supp(f)$ be the support set of the function $f$$f$, i.e., the set of $a$$a$ such that $f(a)>0$$f(a) > 0$. We define the entropy or uncertainty of the discrete random variable $X$$X$ as

$$\begin{array}{}& H(X)=\sum _{a\in supp(P_X)}-P_X(a){\log }_2{P}_X(a)=E[-{\log }_2{P}_X(X)]\end{array}$$

Example 1.1

The entropy $H(X)$$H(X)$ depends only on the probability distribution $P_X(\cdot )$$P_X(\cdot)$， and not on the letters $a$$a$ in alphabet of $X$$X$. We thus have

for any invertible or bijective function $g(\cdot )$$g(\cdot)$, since $g(\cdot )$$g(\cdot)$ simply relabels the letters in the alphabet. Examples include $Y=2^X$$Y=2^X$.

Example 1.2

Consider the Bernoulli distribution that has an alphabet $\{0,1\}$$\{0,1\}$ and $P_X(1)=p$$P_X(1)=p$. The entropy of $X$$X$ is

and $H_2()$$H_2()$ is called the binary entropy function.

Theorem 1.1

$$\begin{array}{}& 0\le H(X)\le {\log }_2|X|\end{array}$$

with equality on the left iff. there is one letter $a$$a$ in $X$$X$ with $P_X(a)=1$$P_X(a)=1$, and with equality on the right iff. $P_X(a)=\frac{1}{|X|}$$P_X(a)=\frac{1}{|X|}$ for any $a\in X$$a\in X$, i.e., $X$$X$ in uniformly distributed.

Proof. of right equality

(4) Example Distributions

(5) Conditional Entropy

Consider the joint distribution $P_{XY}()$$P_{XY}()$ where $X$$X$ and $Y$$Y$ are discrete random variables.

Focusing on one line of the table of joint distribution, we get the conditional entropy of $X$$X$ given the event $Y=b$$Y=b$ with $Pr[Y=b]>0$$Pr[Y=b]>0$ is

Similarly,

with equality on the left iff. $P_{X|Y}(a|b)=1$$P_{X|Y}(a|b)=1$ for some $a$$a$, and with equality on the right iff. $P_{X|Y}(a|b)=\frac{1}{|X|}$$P_{X|Y}(a|b)=\frac{1}{|X|}$ for any $a\in X$$a\in X$.

We average the conditional entropy on all $b\in Y$$b\in Y$ and get the conditional entropy of $X$$X$ given $Y$$Y$

Also,

with equality on the left iff. there is one $a$$a$ such that $P_{X|Y}(a|b)=1$$P_{X|Y}(a|b)=1$ for every $b$$b$. And with equality on the right iff. $P_{X|Y}(a|b)=\frac{1}{|X|}$$P_{X|Y}(a|b)=\frac{1}{|X|}$ for any $a\in X$$a\in X$ and for every $b$$b$.

Example 1.3

We say that $Y$$Y$ essentially determines $X$$X$ if $H(X|Y)=0$$H(X|Y)=0$).

Recall Example 1.1, $g(X)$$g(X)$ is invertible, $H(X)=H(g(X))$$H(X)= H(g(X))$. $X$$X$ determines $g(X)$$g(X)$ and $g(X)$$g(X)$ determines $X$$X$

For a non-invertible function $f(X)$$f(X)$, $H(X)\ne H(f(X))$$H(X)\neq H(f(X))$ since the probability distribution of $X$$X$ and $f(X)$$f(X)$ might be different. $X$$X$ still determines $f(X)$$f(X)$ but $f(X)$$f(X)$ no longer determines $X$$X$

Examples include $Y=|X|$$Y=|X|$ and $Y=cosX$$Y=cosX$.

(6) Joint Entropy

The joint entropy of $X$$X$ and $Y$$Y$ is defined by considering the concatenation (not multiplication!) $XY$$XY$ of $X$$X$ and $Y$$Y$ as a new discrete random variable, i.e., we have

and

with equality on the left iff. $X$$X$ essentially determines $Y$$Y$, or $Y$$Y$ essentially determines $X$$X$, or both. And with equality on the right iff. $P_{XY}(a,b)=\frac{1}{|X||Y|}$$P_{XY}(a,b)=\frac{1}{|X||Y|}$ for all $(a,b)$$(a,b)$.

Example 1.4 Chain Rule for Entropy

Example 1.5

Proof.

Example 1.6

Using conclusions about conditional entropy in Example 1.3, we study the joint distribution $H(Xf(X))$$H(Xf(X))$ and $H(Xg(X))$$H(Xg(X))$.

For a invertible function $g(X)$$g(X)$,

For a non-invertible function $f(X)$$f(X)$,

(7) Information Divergence / Kullback-Leibler Distance

The informational divergence between $P_X(\cdot )$$P_X (\cdot)$ and $P_Y(\cdot )$$P_Y (\cdot)$ is defined as

$$\begin{array}{}& \begin{array}{c}D(P_X\parallel P_Y)=\sum _{a\in supp(P_X)}{P}_X(a){\log }_2\frac{P_X(a)}{P_Y(a)}\\ =E[{\log }_x\frac{P_X(X)}{P_Y(X)}]\end{array}\end{array}$$

We define $D(P_X\parallel P_Y)=\mathrm{\infty }$$D(P_X\parallel P_Y ) = \infin$ if $P_Y(a)=0$$P_Y (a) = 0$ for some $a\in supp(P_X)$$a\in supp(P_X)$.

Observe that the definition is not symmetric in $P_X$$P_X$ and $P_Y$$P_Y$ , i.e., we have $D(P_X\parallel P_Y)\ne D(P_Y\parallel P_X)$$D(P_X\parallel P_Y ) \neq D(P_Y\parallel P_X )$ in general.

To avoid the case $D(P_X\parallel P_Y)=\mathrm{\infty }$$D(P_X\parallel P_Y ) = \infin$ we introduce the notation $P_Y\gg P_X$$P_Y\gg P_X$ to mean that $P_Y(a)=0\Rightarrow P_X(a)=0$$P_Y(a)=0 \Rightarrow P_X(a)=0$ for all $a\in X$$a\in X$. In other words, $P_Y\gg P_X$$P_Y\gg P_X$ implies that $supp(P_X)\subseteq supp(P_Y)$$supp(P_X)\subseteq supp(P_Y)$, or $D(P_X\parallel P_Y)<\mathrm{\infty }$$D(P_X\parallel P_Y ) < \infin$ for finite sets.

Given a third discrete random variable $Z$$Z$, we define the conditional information divergence between $P_{X|Z}(\cdot )$$P_{X|Z}(\cdot)$ and $P_{Y|Z}(\cdot )$$P_{Y|Z}(\cdot)$ as

Theorem 1.2

$$\begin{array}{}& D(P_X\parallel P_Y)\ge 0\end{array}$$

with equality iff. $P_X(a)=P_Y(a)$$P_X (a) = P_Y (a)$ for all $a\in supp(P_X)$$a\in supp(P_X)$.

Proof.

Example 1.7

If $P_Y(\cdot )$$P_Y(\cdot)$ is uniform on X, for $a\in supp(P_X)$$a\in supp(P_X)$, $P_Y(a)=\frac{1}{|X|}$$P_Y(a)=\frac{1}{|X|}$

Example 1.8

If $P_X(\cdot )$$P_X(\cdot)$ is uniform on X, for $a\in supp(P_X)$$a\in supp(P_X)$, $P_X(a)=\frac{1}{|X|}$$P_X(a)=\frac{1}{|X|}$

Example 1.9

If $P_X(a)=1$$P_X(a)=1$ for some $a\in X$$a\in X$,

Example 1.10 Chain Rule for Information Divergence