Concept in information processing
The data processing inequality is an information theoretic concept that states that the information content of a signal cannot be increased via a local physical operation. This can be expressed concisely as 'post-processing cannot increase information'.[1]
Statement
Let three random variables form the Markov chain
, implying that the conditional distribution of
depends only on
and is conditionally independent of
. Specifically, we have such a Markov chain if the joint probability mass function can be written as
![{\displaystyle p(x,y,z)=p(x)p(y|x)p(z|y)=p(y)p(x|y)p(z|y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/846e8183a77e402b50a636a0417246d7ade4ac84)
In this setting, no processing of
, deterministic or random, can increase the information that
contains about
. Using the mutual information, this can be written as :
![{\displaystyle I(X;Y)\geqslant I(X;Z),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95d0c723a108da69b518ae5d8da25322b277d7f4)
with the equality
if and only if
. That is,
and
contain the same information about
, and
also forms a Markov chain.[2]
Proof
One can apply the chain rule for mutual information to obtain two different decompositions of
:
![{\displaystyle I(X;Z)+I(X;Y\mid Z)=I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3248e09b75afa0dd7605b41d8d028a6fd82776b0)
By the relationship
, we know that
and
are conditionally independent, given
, which means the conditional mutual information,
. The data processing inequality then follows from the non-negativity of
.
See also
References
- ^ Beaudry, Normand (2012), "An intuitive proof of the data processing inequality", Quantum Information & Computation, 12 (5–6): 432–441, arXiv:1107.0740, Bibcode:2011arXiv1107.0740B, doi:10.26421/QIC12.5-6-4, S2CID 9531510
- ^ Cover; Thomas (2012). Elements of information theory. John Wiley & Sons.
External links
- http://www.scholarpedia.org/article/Mutual_information