Nonnegativity of Information Measures

Information Divergence is Nonnegative

Let $p,q$ be two different probability distributions over a discrete alphabet ${\mathcal {X}}$. The relative entropy or Kullback-Leibler divergence between $p$ and $q$ is defined as

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

We will prove the following properties of the KL divergence:

• KL divergence is always nonnegative.
• KL divergence is zero if and only if $p(x)=q(x)$ for all $x$.

Proof

Without loss of generality, assume that the base of the logarithm is $e$. This assumption will allow us to use the property that $\ln t\geq 1-1/t$ for all $t>0$. To keep the proof a bit simpler, we further assume that $p(x)$ and $q(x)$ are strictly positive. Rest assured that the result still holds either distribution is zero for some values of $x$.

$D(p\vert \vert q)=\sum _{x}p(x)\ln {\frac {p(x)}{q(x)}}\geq \sum _{x}p(x)\left(1-{\frac {q(x)}{p(x)}}\right)=\sum _{x}p(x)-\sum _{x}q(x)=1-1=0,$

where we used the fact that discrete probability distributions add up to 1.

Whenever we encounter mathematical results expressed as an inequality, it always make sense to ask if the lower/upper bound is tight. By that, we mean to ask: when does equality hold? In the proof, we only produce an inequality by using $\ln t\geq 1-1/t$. Hence, if we know the value of $t$ for which equality holds, we will understand better the tightness of our KL divergence bound. Indeed, our logarithmic inequality will become an equation if and only if $t=1$. In the context of our proof, equality will hold if the expression $p(x)/q(x)$ equals 1, which is just another way of saying that $p(x)=q(x)$.

Remarks

We have just shown that KL divergence is a nonnegative number obtained from comparing two discrete distributions over the same alphabet, and that it will be exactly zero precisely when the two distributions are identical. At this point, it might be tempting to assume that KL divergence is a "distance" between discrete distribution. A careful look at the expression, however, should reveal that relative entropy is not symmetric with respect to $p$ and $q$, i.e., $D(p\vert \vert q)\neq D(q\vert \vert p)$ in general.

Checkpoint: Let $p,q$ be distributions over an alphabet of size 5 such that $p(X)=[1/5,1/5,1/5,1/5,1/5]$ and $q(X)=[1/3,1/3,1/15,1/15,1/15]$. Calculate $D(p\vert \vert q)$ and $D(q\vert \vert p)$.

Conditional Mutual Information is Nonnegative

In this section, we show that for any three random variables $X,Y,Z$, the conditional mutual information $I(X;Y|Z)$ is nonnegative. The important consequences of this statement are the following:

• Entropy is nonnegative.
• Mutual information is nonnegative.
• Conditional entropy is nonnegative.

These consequences are immediate by considering special cases for $I(X;Y|Z)$. The entropy of $X$ can be obtained as follows: $H(X)=I(X;X|Z)$, where $X\perp Z$. The conditional entropy of $X$ given $Z$ is similarly obtained by removing the independence restriction: $H(X|Z)=I(X;X|Z)$. Lastly, (unconditional) mutual information can be obtained by requiring that $X,Y\perp Z$.

Proof

The proof is outlined as follows:

• We express the mutual information between $X$ and $Y$ as the KL-divergence between two distributions over the joint alphabet ${\mathcal {X}}\times {\mathcal {Y}}$.
• We use the nonnegativity of relative entropy to argue that $I(X;Y)\geq 0$.
• We show that conditioning will preserve nonnegativity, i.e., $I(X;Y)\geq 0\Rightarrow I(X;Y|Z)\geq 0$.

The first part of the proof becomes apparent after writing down the definition of mutual information:

$I(X;Y)=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)p(y)}}$

The two distributions over ${\mathcal {X}}\times {\mathcal {Y}}$ that we need to set up KL divergence are as follows: (1) the joint distribution $p(x,y)$, and (2) the distribution obtained by simply multiplying the marginal probabilities $p(x)$ and $p(y)$. Observe that the latter distribution corresponds to the joint distribution if $X$ and $Y$ were independent. With a slight abuse of notation, we now write

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

where we have used the nonnegativity of relative entropy. This small result is quite satisfying on its own because it reinforces this notion that mutual information is related to the degree of non-independence between $X$ and $Y$. Indeed, equality will hold if and only if $p(x,y)=p(x)p(y)$ for all $x,y$, which is equivalent to $X$ and $Y$ being independent.

Arguing for the nonnegativity of $I(X;Y|Z)$ follows from the following expression: $I(X;Y|Z)=\sum _{z}p(z)I(X;Y|Z=z)$. Observe the similarity between this equation and conditional entropy. Since $p(z)$ are nonnegative values, then the linear combination must also be nonnegative and the conclusion follows.

Connection to Markov Chains

Conditional mutual information is closely connected with the conditional independence property in Markov chains. In particular, observe that conditioning any information measure can never increase it: $I(X;Y|Z)\leq I(X;Y)$ for any random variables $X$, $Y$, $Z$.

Checkpoint: Starting with $I(X;Y|Z)=\sum _{z}p(z)I(X;Y|Z=z)$, argue that $I(X;Y|Z)\leq I(X;Y)$.

The conditions under which equality holds, i.e. $I(X;Y|Z)=0$, can be seen by setting

$\sum _{z}p(z)I(X;Y|Z=z)=0$.

Since $p(z)\geq 0$ for all $z$, the summation will vanish if and only if each term $I(X;Y|Z=z)$ is forced to be equal to zero, which means that if we know the value taken by $Z$, then $X$ and $Y$ are conditionally independent, or $X\perp Y|Z$. This is equivalent to saying that $X\rightarrow Z\rightarrow Y$ forms a Markov chain, wherein knowing $Z$ "breaks" the dependence between $X$ and $Y$.