Английская Википедия:Data processing inequality

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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'.

Statement

Let three random variables form the Markov chain <math>X \rightarrow Y \rightarrow Z</math>, implying that the conditional distribution of <math>Z</math> depends only on <math>Y</math> and is conditionally independent of <math>X</math>. Specifically, we have such a Markov chain if the joint probability mass function can be written as

<math>p(x,y,z) = p(x)p(y|x)p(z|y)=p(y)p(x|y)p(z|y)</math>

In this setting, no processing of <math>Y</math>, deterministic or random, can increase the information that <math>Y</math> contains about <math>X</math>. Using the mutual information, this can be written as :

<math> I(X;Y) \geqslant I(X;Z),</math>

with the equality <math>I(X;Y) = I(X;Z) </math> if and only if <math> I(X;Y\mid Z)=0 </math>. That is, <math>Z</math> and <math>Y</math> contain the same information about <math>X</math>, and <math>X \rightarrow Z \rightarrow Y</math> also forms a Markov chain.

Proof

One can apply the chain rule for mutual information to obtain two different decompositions of <math>I(X;Y,Z)</math>:

<math>

I(X;Z) + I(X;Y\mid Z) = I(X;Y,Z) = I(X;Y) + I(X;Z\mid Y) </math>

By the relationship <math>X \rightarrow Y \rightarrow Z</math>, we know that <math>X</math> and <math>Z</math> are conditionally independent, given <math>Y</math>, which means the conditional mutual information, <math>I(X;Z\mid Y)=0</math>. The data processing inequality then follows from the non-negativity of <math>I(X;Y\mid Z)\ge0</math>.

See also

• Garbage in, garbage out

External links

• http://www.scholarpedia.org/article/Mutual_information

Шаблон:Comp-sci-stub