1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I only know the answer for the first one. If you see the proof of data processing inequality in Cover page 34, it is easy to find out data processing inequality turns out to be equality only when the "double Markovity" is satisfies.

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)

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$ $\endgroup$
    – vsoftco
    Jul 29, 2014 at 0:48
  • $\begingroup$ PS: I edited the question to make it more clear. $\endgroup$
    – vsoftco
    Jul 29, 2014 at 0:49
  • $\begingroup$ 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, $\endgroup$
    – math-Student
    Jul 29, 2014 at 3:19
  • $\begingroup$ 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. $\endgroup$
    – vsoftco
    Jul 29, 2014 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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