Jensen’s Inequality

Sources:

1. Elements of Information Theory
2. EE 376A: Information Theory - Stanford University

Convexity

Convexity underlies many of the basic properties of information-theoretic quantities such as entropy and mutual information.

Definition: A function $f(x)$ is said to be convex(凸函数) over an interval $(a,b)$ if for every $x_1,x_2\in (a,b)$ and $0\le \lambda \le 1$, $$\begin{array}{}\text{(1)}& f(\lambda x_1+(1-\lambda )x_2)\le \lambda f\left(x_1\right)+(1-\lambda )f\left(x_2\right).\end{array}$$ A function $f$ is said to be strictly convex if equality holds only if $\lambda =0$ or $\lambda =1$.

Note: A function $f$ is concave(凹函数) if $-f$ is convex.

A function is convex if it always lies below any chord. A function is concave if it always lies above any chord.

Examples

Examples of convex and concave functions

• Examples of convex functions: $x^2,|x|,e^x,x\log x$ (for $x\ge$ 0 ), and so on.
• Examples of concave functions: $\log x$ and $\sqrt{x}$ for $x\ge 0$.
• Note: linear functions $ax+b$ are both convex and concave.

Theorem 1

If the function f has a second derivative that is non- negative (positive) over an interval, the function is convex (strictly convex) over that interval.

Proof: We use the Taylor series expansion(泰勒展开) of the function around $x_0$ : $$f(x)=f\left(x_0\right)+f^{\prime }\left(x_0\right)(x-x_0)+\frac{f^{\prime \prime }\left(x^{\ast }\right)}{2}{(x-x_0)}^2,$$ where $x^{\ast }$ lies between $x_0$ and $x$.

By hypothesis, $f^{\prime \prime }\left(x^{\ast }\right)\ge 0$, and thus the last term is nonnegative for all $x$. So $$f(x)\ge f(x)-\frac{f^{\prime \prime }\left(x^{\ast }\right)}{2}{(x-x_0)}^2=f\left(x_0\right)+f^{\prime }\left(x_0\right)(x-x_0)).$$

We let $x_0=\lambda x_1+(1-\lambda )x_2$ and take $x=x_1$, to obtain $$\begin{array}{}\text{(2)}& f\left(x_1\right)\ge f\left(x_0\right)+f^{\prime }\left(x_0\right)((1-\lambda )(x_1-x_2)).\end{array}$$

Similarly, taking $x=x_2$, we obtain $$\begin{array}{}\text{(3)}& f\left(x_2\right)\ge f\left(x_0\right)+f^{\prime }\left(x_0\right)\left(\lambda (x_2-x_1)\right).\end{array}$$ Multiplying $\text{(2)}$ by $\lambda$ and $\text{(3)}$ by $1-\lambda$ and adding, we obtain $\text{(1)}$. The proof for strict convexity proceeds along the same lines.

Theorem 1 allows us immediately to verify the strict convexity of $x^2,e^x$, and $x\log x$ for $x\ge 0$, and the strict concavity of $\log x$ and $\sqrt{x}$ for $x\ge 0$.

Let $E$ denote expectation. Thus, $EX=\sum _{x\in \mathcal{X}}p(x)x$ in the discrete case and $EX=\int xf(x)dx$ in the continuous case.

Jensen’s Inequality

Definition: If $f$ is a convex function and $X$ is a random variable, the Jensen’s inequality is defined as $$\begin{array}{}\text{(4)}& Ef(X)\ge f(EX).\end{array}$$ Moreover, if $f$ is strictly convex, the equality in $\text{(4)}$ implies that $X=EX$ with probability 1 (i.e., $X$ is a constant).

Proof

We prove this for discrete distributions by induction on the number of mass points. The proof of conditions for equality when $f$ is strictly convex is left to the reader. For a two-mass-point distribution, the inequality becomes $$p_{1}f\left(x_1\right)+p_{2}f\left(x_2\right)\ge f(p_1{x}_1+p_2{x}_2),$$ which follows directly from the definition of convex functions. Suppose that the theorem is true for distributions with $k-1$ mass points. Then writing $p_i^{\prime }=p_i/(1-p_k)$ for $i=1,2,\dots ,k-1$, we have

$$\begin{array}{rl}\sum _{i=1}^k{p}_{i}f\left(x_i\right)& =p_{k}f\left(x_k\right)+(1-p_k)\sum _{i=1}^{k-1}{p}_i^{\prime }f\left(x_i\right)\\ & \ge p_{k}f\left(x_k\right)+(1-p_k)f\left(\sum _{i=1}^{k-1}{p}_i^{\prime }{x}_i\right)\\ & \ge f(p_k{x}_k+(1-p_k)\sum _{i=1}^{k-1}{p}_i^{\prime }{x}_i)\\ & =f\left(\sum _{i=1}^k{p}_i{x}_i\right)\end{array}$$ where the first inequality follows from the induction hypothesis and the second follows from the definition of convexity.

The proof can be extended to continuous distributions by continuity arguments.

We now use these results to prove some of the properties of entropy and relative entropy. The following theorem is of fundamental importance.

Example

Consider a uniform random variable $X$ defined on set $\{a,b\}$ and a convex function $f$ as shown in Figure 3.

By Jensen’s inequality, $0.5f(a)+f(b)\ge f0.5(a+b)$ , which can also be inferred from Figure 3.

Figure 3: Illustration of Jensen’s inequality

Theorem: Information Inequality

Let $p(x),q(x),x\in \mathcal{X}$, be two probability mass functions. Then $$D(p\Vert q)\ge 0$$ with equality if and only if $p(x)=q(x)$ for all $x$. Proof: Let $A=\{x|p(x)>0\}$ be the support set¹ of $p(x)$. Then $$\begin{array}{rl}-D(p\Vert q)& =-\sum _{x\in A}p(x)\log \frac{p(x)}{q(x)}\\ & =\sum _{x\in A}p(x)\log \frac{q(x)}{p(x)}\\ & ={\mathbb{E}}_{x\in A}(\log \frac{q(x)}{p(x)})\\ \text{(5)}& & \le \log {\mathbb{E}}_{x\in A}(\frac{q(x)}{p(x)})& =\log \sum _{x\in A}p(x)\frac{q(x)}{p(x)}\\ & =\log \sum _{x\in A}q(x)\\ \text{(6)}& & \le \log \sum _{x\in \mathcal{X}}q(x)& =\log 1\\ & =0\end{array}$$ where $\text{(5)}$ follows from Jensen's inequality, because $\log t$ is a strictly concave function of $t$.

Also, since $\log t$ is a strictly concave function of $t$, we have equality in $\text{(5)}$ if and only if $\frac{q(x)}{p(x)}$ is constant everywhere [i.e., $q(x)=cp(x)$ for all $x$ ]. Thus, $\sum _{x\in A}q(x)=$ $c\sum _{x\in A}p(x)=c$.

We have equality in $\text{(6)}$ only if $\sum _{x\in A}q(x)=\sum _{x\in \mathcal{X}}$ $q(x)=1$, which implies that $c=1$. Hence, we have $D(p\Vert q)=0$ if and only if $p(x)=q(x)$ for all $x$.

Note: 证明中必须要用到support set $A=\{x|p(x)>0\}$, 这是因为证明时出现了$\frac{q(x)}{p(x)}$, 我们必须满足$p(x)>0$.

Theorem: $H(X)\le \log |\mathcal{X}|$

We now show that the uniform distribution over the range $\mathcal{X}$ is the maximum entropy distribution over this range. It follows that any random variable with this range has an entropy no greater than $\log |\mathcal{X}|$.

Theorem: $$H(X)\le \log |\mathcal{X}|$$ where $|\mathcal{X}|$ denotes the number of elements in the range of $X$, with equality if and only $X$ has a uniform distribution over $\mathcal{X}$.

Proof: $$ Let $u(x)=\frac{1}{|\mathcal{X}|}$ be the uniform probability mass function over $\mathcal{X}$, and let $p(x)$ be the probability mass function for $X$. Then $$D(p\Vert u)=\sum p(x)\log \frac{p(x)}{u(x)}=\log |\mathcal{X}|-H(X).$$ Hence by the nonnegativity of relative entropy, $$0\le D(p\Vert u)=\log |\mathcal{X}|-H(X).$$

Theorem: Conditioning reduces entropy

Conditioning reduces entropy(Information can't hurt): $$H(X\mid Y)\le H(X)$$ with equality if and only if $X$ and $Y$ are independent.

Proof:

1. We know that $0\le I(X;Y)$².
2. Since $I(X;Y)=H(X)-H(X\mid Y)$.
3. We have $H(X\mid Y)\le H(X)$

Intuitively, the theorem says that knowing another random variable $Y$ can only reduce the uncertainty in $X$.

Note that this is true only on the average. Specifically, $H(X\mid Y=y)$ may be greater than or less than or equal to $H(X)$, but on the average $H(X\mid Y)=\sum _{y}p(y)H(X\mid Y=y)\le$ $H(X)$. For example, in a court case, specific new evidence might increase uncertainty, but on the average evidence decreases uncertainty.

For multiple condions

This theorem can be extended to multiple condions. Given random variables $X_1,X_2,\cdots ,X_n$, $$H(X_1|X_2,X_3,\cdots ,X_n)\le H(X_1|X_3,\cdots ,X_n).$$ Proof:

1. We know that $0\le I(X_1|X_3,\cdots ,X_n;X_2)$.
2. Note that the conditional entropy of $X|Y$ given observation $Z$ is $H(X|Y,Z)$. so $I(X_1|X_3,\cdots ,X_n;X_2)=H(X_1|X_3,\cdots ,X_n)-H(X_1|X_2,X_3,\cdots ,X_n)$.
3. We have $H(X_1|X_3,\cdots ,X_n)\le H(X_1|X_2,X_3,\cdots ,X_n)$.

Example

Let $(X,Y)$ have the following joint distribution:

Y\X	x=1	x=2
Y=1	0	3/4
Y=2	1/8	1/8

Then we have

• $H(X)=H(\frac{1}{8},\frac{7}{8})=0.544$ bit,
• $H(X\mid Y=1)=0$ bits,
• $H(X\mid Y=2)=1$ bit.

We calculate $H(X\mid Y)=\frac{3}{4}H(X\mid Y=1)+\frac{1}{4}$ $H(X\mid Y=2)=0.25$ bit.

Thus, the uncertainty in $X$ is:

• increased if $Y=2$ is observed
• decreased if $Y=1$ is observed

But uncertainty decreases on the average.

Theorem: Independence bound on entropy

Let $X_1,X_2,\dots ,X_n$ be drawn according to $p(x_1,x_2,\dots ,x_n)$. Then $$H(X_1,X_2,\dots ,X_n)\le \sum _{i=1}^{n}H\left(X_i\right)$$ with equality if and only if the $X_i$ are independent.

Proof:

1. By the chain rule for entropies, $$H(X_1,X_2,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)$$

2. Then by theorem of Conditioning reduces entropy, $$\mathrm{\forall }i\in 1,\cdots ,n,H(X_i\mid X_{i-1},\dots ,X_1)\le H(X_i)$$

3. Then we have $$\begin{array}{rl}H(X_1,X_2,\dots ,X_n)& =\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)\\ & \le \sum _{i=1}^{n}H\left(X_i\right)\end{array}$$ According to theorem of Conditioning reduces entropy, we have equality if and only if $X_i$ is independent of $X_{i-1},\dots ,X_1$ for all $i$ (i.e., if and only if the $X_i$ 's are independent).

   Q.E.D.

---

1. The support set of a probability distribution is the set of all possible values of the random variable for which the probability of that value is greater than zero.↩︎

2. https://lyk-love.cn/2023/10/15/Shannon-Entrophy/#properties-2↩︎