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)$)

  • $\begingroup$ 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)$ $\endgroup$ – leonbloy Jan 17 '15 at 22:24
  • $\begingroup$ 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)$ $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.