# Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution.

The mutual information between the input and the output of $C_1$ must be greater or equal than the mutual information between the input and the output of the composed channel $C_1\circ C_2$ (i.e. act with $C_1$ first then feed the output to $C_2$). This follows from the data processing inequality.

My questions are:

1. Given $p(x)$, what are the channels $C_2$ for which equality holds (i.e. mutual information is non-decreasing). I know from of proof of data processing inequality that is true if and only if one has a Markov chain, but what can we say about the conditional transition matrices, i.e. relations between $p(x)$, $C_1$ and $C_2$? Or, in other words, what is the functional form of $C_2$ as a function of $C_1$ and $p(x)$?

2. And the reverse: given $C_2$, what are the input distributions $p(x)$ for which the mutual information is non-decreasing?

I wasn't able to find an elegant solution to this problem, I have only some partial solutions. For example, if $C_2$ is a permutation channel, then mutual information stays the same no matter what $p(x)$ is. Thanks!

PS: I hope it is clear what I mean by mutual information between the input and output of a channel, it is the mutual information of the joint probability distribution obtained by multiplying the elements of the transition matrix with the corresponding component of the input, $p(x,y)=p(y|x)p_{0}(x)$.

Let $X, Y$ and $Z$ are three random variables representing the input, output of the first channel and output of the second, respectively. Hence, we have the Markov chain $X\to Y\to Z$ and due to data processing inequality we have $I(X;Y)\geq I(X;Z)$. The equality occurs if and only if $I(X;Y|Z)=0$ which implies the Markov chain $X\to Z\to Y$. In this case $I(X;Y)=I(X;Z)$. This is why $Z$ is called sufficient statistics of $Y$ with respect to $X$. (see this post1)
• Thanks @SAmath, was aware that this is the case, from the famous book. I was actually a bit unclear in my question. I would like to be able to say something about the transition matrices $C_1$ and $C_2$, i.e. given an input $p(x)$ and a channel $C_1$ (basically a transition matrix $p(y|x)$), what channels $C_2$ make give equality in the data processing. Intuitively, $C_2$ has to be somehow "correctable", that is, all information about the input should be present at the output of $C_2$. I find hard to formalize this and come up with an explicit form of $C_2$ as a function of $p(x)$ and $C_1$ – vsoftco Jul 29 '14 at 0:48
• Suppose $p(x)$ and $p(y|x)$ are given. Then your problem is to characterize the sufficient statistics of $Y$ with respect to $X$. Lets call this $T(Y)$. Then $C_2$ is simply equal to $p(T(y)|y)=I_{\{(T(y)=y\}}$. It can be shown that $T(y)$ can be characterized as the following: $T:\mathcal{Y}\to \mathcal{P}(\mathcal{X})$ defined by $y\to p(x|y)$ where $\mathcal{P}(\mathcal{X})$ is the simplex of probability measures over alphabet $\mathcal{X}$. If this is not clear (which I think it is) please let me know, – math-Student Jul 29 '14 at 3:19
• thanks. I am slightly unfamiliar with the notation, but my understanding is that basically $C_2$ has to behave like the identity on the support of $p(x) C_1$? Sorry for the long strings of comments. – vsoftco Jul 29 '14 at 13:54