Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Let $p_0(x)$ be some arbitrary but fixed 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_2\circ C_1$ (i.e. act with $C_1$ first then feed the output to $C_2$). This follows from the data processing inequality. What are the necessary and conditions on $C_2$ so that one has equality? That is, the mutual information is not decreasing but stays the same under the composition? Of course if $C_2$ is identity, or a permutation channel, then it is true.

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

  • $\begingroup$ Why isn't $C_1\circ C_2$ Markov? If $z=C_2(y)$, does $p(z|y,x)$ depend on $x$ in your example? $\endgroup$ – Kirill Jul 25 '14 at 2:24
  • $\begingroup$ @Kirill Take the channel from $X$ to $Y$ to be a bit flip channel with error $\eps$, and the one from $Y$ to $Z$ an identity channel. Then $p(z|y,x)$ depends just on $X$. Is my reasoning somehow wrong? $\endgroup$ – vsoftco Jul 25 '14 at 2:27
  • $\begingroup$ Yes, I think so: $p(z|y,x)=[z=y]$ is independent of $x$, so $Z\perp X\mid Y$. $\endgroup$ – Kirill Jul 25 '14 at 2:28
  • $\begingroup$ @Kirill, damn, I was computing the marginal actually, without conditioning. Yes, it is indeed Markovian and then the claim follows from data processing. Thanks. Stupid mistake... However the real question is what is the condition for the equality in terms of the transition matrix $C_2$? I will edit the question and ask this one. $\endgroup$ – vsoftco Jul 25 '14 at 2:32
  • $\begingroup$ @Kirill, I know that equality is achieved when $X->Z->Y$ is also a Markov chain, but didn't find a compact way of representing this as a necessary and sufficient condition for the channel $C_2$ itself. $\endgroup$ – vsoftco Jul 25 '14 at 2:37

Your Answer

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

Browse other questions tagged or ask your own question.