# Convexity of mutual information $I(X;Y)$ in conditional $p(y \mid x)$

I'm trying to understand the proof that $I(X;Y)$ is convex in conditional distribution $p(y \mid x)$ - from Elements of Information Theory by Cover & Thomas, theorem 2.7.4.

In the proof we fix $p(x)$ and consider two conditionals $p_1 (y \mid x)$ and $p_2 (y \mid x)$. Corresponding joints are $p_1(x, y) = p(x) \, p_1 (y \mid x)$ and $p_2(x, y) = p(x) \, (y \mid x)$ and marginals are $p_1(y)$ and $p_2(y)$.

Then we consider conditional $p^*(y \mid x) = \lambda \, p_1 (y \mid x) + (1 - \lambda) \, p_2 (y \mid x)$, joint $p^*(x, y) = \lambda \, p_1 (x, y) + (1 - \lambda) \, p_2 (x, y) = \lambda \, p(x) \, p_1 (y \mid x) + (1 - \lambda) \, p(x) \, p_2 (y \mid x)$ and marginal $p^*(y) = \lambda \, p_1 (y) + (1 - \lambda) \, p_2 (y)$.

If we let $q^*(x, y) = p(x) \, p^*(y) = \lambda \, p(x) \, p_1 (y) + (1 - \lambda) \, p(x) \, p_2 (y)$, then the KL divergence between $p^*(x, y)$ and $q^*(x, y)$ is $D \big( p^*(x, y) \ || \ q^*(x, y) \big) = D \big( p^*(x, y) \ || \ p(x) \, p^*(y) \big) = I(X; Y)$ - for $X \sim p(x)$ and $Y \sim p^*(y)$

Next in the book they conclude the proof by saying that since $D( p \ || \ q)$ is convex in $(p, q)$, so is $I(X;Y)$. What I don't understand is why it means that $I(X; Y)$ is convex in $p(y \mid x)$?

That $D(u||v)$ is convex in the pair $(u,v)$ means that

$$D(u_{\lambda}||v_{\lambda}) \le \lambda D(u_{1}||v_{1}) +(1-\lambda)D(u_{2}||v_{2})$$

(here $u$ and $v$ and some probability functions, with $u= \lambda u_1 +(1-\lambda) u_2$, etc)

Then $$I(X_{\lambda};Y_{\lambda}) = D(p_{\lambda}(X,Y)||p_{\lambda}(X)p_\lambda(Y))$$ where (as shown in the text)

$p_{\lambda}(X,Y) = p(X) p_\lambda(Y|X)=\lambda p_1(x,y)+(1-\lambda)p_2(x,y)= p(x) (\lambda p_1(y|x)+(1-\lambda)p_2(y|x))$

I.e.: the "mixture" can be written in terms of the variable $p(y|x)$ as well as in terms of the joint $p(x,y)$ - and the same happens for the marginal $p(y)$. Then we can also write

$p_{\lambda}(X)p_\lambda(Y) = \lambda p(x)p_1(y)+(1-\lambda)p(x)p_2(y)$

Then, pluggin this into the second equation, and using the first inequation:

$$I(X_{\lambda};Y_{\lambda}) \le \lambda I(X_1;Y_1) + (1-\lambda) I(X_2;Y_2)$$

which means that $I(X;Y)$ is convex with respect to the mixed variable (in this case, $p(y|x)$)

• I'm not sure I understand what follows the "thus" in your comment. Don't fall in the trap of mapping (in my first inequation) $u \to p(x)$ and $v \to p(y)$. Actually the correspondence is $u \to p(x,y)$ and $v \to p(x)p(y)$ – leonbloy Jan 17 '15 at 22:24
• But I'm still confused, and my confusion comes from the last step. Here we have $I(X_{\lambda};Y_{\lambda}) = D(p_\lambda(x, y) \ || \ p_\lambda(x) \, p_\lambda(y) ) \le$ $\lambda D(p_1(x, y) \ || \ p_1(x) \, p_1(y) )$ $+ (1-\lambda) D(p_2(x, y) \ || \ p_2(x) \, p_2(y) )$, but I don't see why from here it follows that it's convex in $p(y \mid x)$, even if try to put there $p_1(x, y) = p_1(x) \, p_1(y \mid x)$ and $p_1(y) = \sum_x p_1(x) \, p_1(y \mid x)$ – Alexey Grigorev Jan 18 '15 at 7:57

First lets state the claim.

Claim: $I(X;Y)=D(p(x,y)||p(x)p(y))$ is concave in $p(x)$ for fixed $p(y|x)$ and convex in $p(y|x)$ for fixed $p(x)$.

One can write the following:

$I(X;Y)=H(Y)-H(Y|X)$ where $H$ is the entropy function. The entropy functions can further be written as

$$H(Y)=-\sum_y p(y)\log(p(y)) \ \text{ and } \ H(Y|X)=-\sum_x p(x)\sum_y p(y|x)\log (p(y|x))$$

What we know is that $H(Y)$ is a concave function of $p(y)$, because $x\log x$ is a convex function of $x$. We can write $p(y)=\sum_x p(y|x)p(x)$. Hence, whenever $p(y|x)$ is fixed, meaning that it is constant for all $p(y|x)$, $p(y)$ is a linear function of $p(x)$. Therefore $H(Y)$ is also concave in $p(x)$. For fixed $p(y|x)$, $H(Y|X)$ is also linear in $p(x)$. Now consider a function which is a sum of a linear and a concave function $f(x)=c(x)+l(x)$. Since $f^{''}(x)=c^{''}(x)$, where $(\cdot)^{''}$ is the second derivative, $f$ is also concave. Therefore, $I(X;Y)$ is a concave function of $p(x)$.

Now lets come to the second part. When $p(x)$ is constant, this time $p(y)=\sum_x p(y|x)p(x)$ is a linear function of $p(y|x)$. Hence, $H(Y)$ is a concave function of $p(y|x)$. Due to same reason $H(Y|X)$ is also a concave function. Difference of two concave functions can either be concave or convex or both. Going back to the definition $I(X;Y)=D(p(x,y)||p(x)p(y))$, we also know that $D(\cdot||p(x)p(y))$ is convex in $p(x)p(y)$, since KL divergence is convex in both terms. Now, $p(x)$ was constant and $p(y)$ was linear in $p(y|x)$. Therefore, the right choice was that $I$ is convex in $p(y|x)$, else $D$ cannot be convex in $p(x)p(y)$.

Another idea would be to show that $I(X;Y)$ accepts no maximum over $p(y|x)$, except for the boundaries. I dont know however how this can be shown. What I know is that $I(X;Y)$ is always upperbunded by $\min[ H(X),H(Y)]$, simply from the symmetry of $I(X;Y)=H(Y)-H(Y|X)=H(X)-H(X|Y)$.