Data processing inequality: Difference between revisions

Revision as of 20:12, 10 February 2023

Latest revision as of 16:21, 22 August 2024

(4 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Concept in information processing}}

The '''data processing inequality''' is an [[information theory|information theoretic]] concept whichthat 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'.<ref name= BeaudryArxiv>{{citation |journal=Quantum Information & Computation |volume=12 |issue=5–6 |pages=432–441 |last1=Beaudry |first1=Normand |title=An intuitive proof of the data processing inequality |date=2012 |doi=10.26421/QIC12.5-6-4 |arxiv=1107.0740|bibcode=2011arXiv1107.0740B |s2cid=9531510 }}</ref>

==DefinitionStatement==

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 [[Conditional independence|conditionally independent]] of <math>X</math>. Specifically, we have such a Markov chain if the joint probability mass function can be written as

Line 7 ⟶ 8:

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>

Withwith the equality <math>I(X;Y) = I(X;Z) </math> if and only if <math> I(X;Y\mid Z)=0 </math>, i.e. 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.<ref>{{cite book| title=Elements of information theory | last1=Cover | last2=Thomas | date=2012 | publisher=John Wiley & Sons}}</ref>

==Proof==