Information Theory - Chapter 2 Property of Entropy

In this chapter, we will further discover the properties of Entropy.

Theorem(Jensen’s inequality): If function $f$ is convex and $X$ is a discrete random variable. It takes values on $\mathcal{X}(x_1, x_2, \cdots, x_n), P_X=(p_1, \cdots, p_n)$. Then

This could also be written as

If $f$ is strictly convex, and if equality holds, then $X=\mathbb{E}[X]$.

Theorem: $P(x), Q(x)$ are distribution on $\mathcal{X}$, for $x\in \mathcal{X}$. So $D(P\Vert Q)\ge 0$ with equality iff $P(x)=Q(x), \forall x\in \mathcal{X}.$

Proof: Let

we may assume $Q(x)>0, x\in A$. (else if $Q(x)=0$ for some $x\in A$ then $D=\infty$)

Then,

Since $f(x)=\log(x)$ is concave $\Rightarrow$equality holds iff $\frac{Q(x)}{P(x)}=C, \forall x\in \mathcal{X}$. As

Corollary: $I(X;Y\ge 0)$ with equality iff $X$ and $Y$ are independent.

Proof:

Corollary: $D(P_{Y\vert X}\Vert Q_{Y\vert X})\ge 0$ with equality iff $P_{Y\vert X}(y\vert x)=Q_{Y\vert X}(y\vert x)$ for all $(y, x)\in Y\times X$ s.t. $P_X(x)>0$.

Corollary: $I(X, Y\vert Z)\ge 0$ with equality iff $P_{XY\vert Z}(xy\vert z)=P_{X\vert Z}(x\vert z)P_{Y\vert Z}(y\vert z).$

Theorem: $H(X)\le \log \vert X\vert $ with equality iff $X$ is uniformly distribution over $X$.

Proof: Let $U(x)=\frac{1}{\vert X\vert }$ for $x\in X$.

Theorem: $H(X\vert Y)\le H(X)$.

Proof: $H(X)-H(X\vert Y)=I(X;Y)\ge 0.∎$

However, note that condition on an specific event may/maynot decrease entropy:

Theorem(Independent bound): $H(X_1, \cdots, X_n)\le \sum_{i=1}^nH(X_i)$ with equality iff $X_1, \cdots, X_n$ are independent.

Han’s inequality:

So

We could demonstrate the Han’s inequality by another method.

Definition(Submodular functions): Let

The function $f$ is called submodular if

This definition is equivalant to: if $\forall T_1\subset T_2\subset S, b\in S-T_2$,

which means adding elements brings dimishing marginal return.

Theorem: Let discreterandom variable

Let

then the function $T\rightarrow H(X_T)$ is submodular.

So with this theorem, we could demonstrate Han’s inequality more conveniently.

Denote

Using equivalent definition,

Summing over $i=1, 2, \cdots, n$, we obtain Han’s inequality.

Theorem(Log-sum inequality): Let $a_i\ge 0, b_i\ge 0, i=1, 2, \cdots, n.$ Let $a=\sum_{i=1}^n a_i, b=\sum_{i=1}^n b_i$,

Proof:

Theorem(Convexity of $D$): Let $P(X), Q(X)$ be PMFs, then $D(P\Vert Q)$ is convex in $(P, Q)$, i.e., $D(\lambda P_1+(1-\lambda)P_2\Vert \lambda Q_1+(1-\lambda)Q_2)\le \lambda D(P_1\Vert Q_1) + (1-\lambda) D(P_2\Vert Q_2)$.

Proof: Apply log-sum inequality termwise. Fix $x\in X$,

Summing over the $x\in X$, we will obtain the desired results. ∎

Theorem(Convexity of $H$):$H(P)$ is a concave function of $P$.

Proof:

Note that $D(P\Vert U)=\sum_{x\in X}P(x)\log\frac{P(x)}{\vert X\vert }.$ ∎

Theorem: Given RVs $X, Y$ with joint PMF $P_{XY}$,

(1). $I(X; Y)$ is concave in $P_X$ for a fixed $P_{Y\vert X}$.

(2). $I(X;Y)$ is convex in $P_{Y\vert X}$ for a fixed $P_X$.

Proof:

(1). Note that

As

which means $P_Y$ is linear in $P_X$.

Accordingly, $H(Y)$ is concave in $P_X$, so is $I(X;Y)$ when $P_{Y_X}$ is fixed.

(2). Fix $P_X$.

Let $P_1(y\vert x), P_2(y\vert x)$ be two possibility for $P_{Y\vert X}$.

Denote $P_i(x, y)=P_X(x)P_i(y\vert x), P_i(y)=\sum_{x\in X}P_i(x, y)$.

Choose $\lambda\in [0,1)$ and consider the mixtures:

So

Let $Q_\lambda(x, y)=P_X(x)P_\lambda(y)=\lambda P_1(y)P_X(x)+(1-\lambda)P_2(y)P_X(x)=\lambda Q_1(x,y)+(1-\lambda)Q_2(x, y)$.

So, with convexity of $D$,