The Data Processing Inequality

From Microlab Classes
Revision as of 11:20, 23 October 2020 by Louis Alarcon (talk | contribs)
Jump to navigation Jump to search

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)

The Data Processing Inequality

Sufficient Statistics

Fano's Inequality