Difference between revisions of "The Data Processing Inequality"

From Microlab Classes
Jump to navigation Jump to search
Line 118: Line 118:
  
 
== The Data Processing Inequality ==
 
== The Data Processing Inequality ==
 +
Consider a Markov chain, <math>X \rightarrow Y \rightarrow Z</math>.
  
 
== Sufficient Statistics ==
 
== Sufficient Statistics ==
  
 
== Fano's Inequality ==
 
== Fano's Inequality ==

Revision as of 09:08, 28 October 2020

Markovity

A Markov Chain is a random process that describes a sequence of possible events where the probability of each event depends only on the outcome of the previous event. Thus, we say that is a Markov chain in this order, denoted as:

 

 

 

 

(1)

If we can write:

 

 

 

 

(2)

Or in a more compact form:

 

 

 

 

(3)

We can use Markov chains to model how a signal is corrupted when passed through noisy channels. For example, if is a binary signal, it can change with a certain probability, , to , and it can again be corrupted to produce .

Consider the joint probability . We can express this as:

 

 

 

 

(4)

And if , we get:

 

 

 

 

(5)

Since , we can write:

 

 

 

 

(6)

Thus, we can say that and are conditionally independent given . If we think of as some past event, and as some future event, then the past and future events are independent if we know the present event . Note that this property is good definition of, as well as a useful tool for checking Markovity.

We can rewrite the joint probability as:

 

 

 

 

(7)

Therefore, if , then it follows that .

Entropy Chain Rules

Figure 1: Entropy visualization for two random variables using Venn diagrams.

As we increase the number of random variables we are dealing with, it is important to understand how this increase affects entropy. We have previously shown that for two random variables and :

 

 

 

 

(8)

We can use Venn diagrams to visualize these relationships, as seen in Fig. 1. For three random variables , , and :

 

 

 

 

(9)

In general:

 

 

 

 

(10)

Conditional Mutual Information

Conditional mutual information is defined as the expected value of the mutual information of two random variables given the value of a third random variable, and for three random variables , , and , it is defined as:

 

 

 

 

(11)

We can rewrite the definition of conditional mutual information as:

 

 

 

 

(12)

Figure 2: Entropy visualization for three random variables using Venn diagrams.

We can visualize this relationship using the Venn diagrams in Fig. 2. Compare this to our expression for the mutual information of two random variables and :

 

 

 

 

(13)

Chain Rule for Mutual Information

For random variables and :

 

 

 

 

(14)

And for random variables , and :

 

 

 

 

(15)

We can then express the conditional mutual information as:

 

 

 

 

(16)

Rearranging, we then obtain the chain rule for mutual information:

 

 

 

 

(17)

Thus, we can extend this for additional random variables:

 

 

 

 

(18)

In general:

 

 

 

 

(19)

The Data Processing Inequality

Consider a Markov chain, .

Sufficient Statistics

Fano's Inequality