Overview

In this lecture, we are going to introduce most of the basic definitions in information theory. This includes entropy, joint entropy, conditional entropy, relative entropy, mutual information, convexity, concavity and so on. A lot of theorems in inequalities will also be introduced. This includes the Jensen’s inequality, data-processing inequality and Fano’s inequality. Importance of these inequalities will be discussed.

 

Scenario

Let  be two correlated random variables with probability distribution q(.,.) , which we called it as the true distribution.

Let a sequence of  pairs of random variables be  , where each pair of random variables is distributed independent and identically distributed (i.i.d.) and have the empirical distribution {p(x,y)}, depending on the fraction of pairs of type (x,y) that occur.

 

Strongly typical sets

Since the true distribution is provided, the events that the occurrence of some sequences are more likely than others. In other words, true distribution q and empirical distribution p are “similar”. Denote a jointly strongly typical set , where  is the “variational distance”.

Using Lemma 4 in [1], we approximate

 

In most cases, we only obtain either  or  and guess another. Suppose we know , and denote a jointly strongly typical set . Applying lemma 4 in [1] again, we obtain the following:

 

 

 

 

The size of a typical set can be interpreted as the uncertainty of a random variable. The larger is the  typical set, the less uncertainty of that random variable.

 

Weak typicality and strong typicality

 weakly typical is defined as

 

 

A sequence  is said to be  strongly-typical with respect to a distribution  on  if:

1. For all  with , we have

2. For all  with , , where  is the number of occurences of the symbol in the sequence .

Weak typicality does not imply strong typicality. By definition, strong typicality implies weak typicality with a different .

 

 

Mutual information

 

Relative information

Relative entropy, divergence or Kullback-Leibler distance between two p.m.f. is defined as

 

It is not a true distance as it is not symmetric, i.e. 

 

Equalities in information theory

We can use the Venn diagram to help us remember the inequalities. The inequalities hold even when conditioning on another random variable Z.

 

We may want to extend the Venn diagram to more than two random variables. The equalities still holds. However, the diagram can be misleading when finding out the inequalities, e.g.  can be positive or negative.

 

 

 

These equalities can be proved using the equalities for two variables found in PS2-Q2. Applying the inequalities in PS2-Q3 gives the inequalities in three variables case.

 

Jensen’s inequality

A function f(x) is said to be convex over an interval (a,b) if for every and  and .

Jensen’s inequality is to generalize this idea to more than two points. If function f(x) is convex and X is a random variable, 

 

With Jensen's inequality, we can prove that some of the properties of relative entropy.

Let , , , be two probability mass functions. Then

with equalitiy if and only if  for all .

 

Proof:

 

Let be the support set of . Then

 [Jessen's inequality)

.

 

Since

 

, with equalitiy if and only if  and  are independent.

 

Data processing inequality

Random variables X,Y,Z are said to form a Markov chain in that order (denoted by X -> Y -> Z) if the conditional distribution of Z depends only on Y and is conditionally independent of X.

If X -> Y -> Z, expressing I(X;Y;Z) in two ways:

 

 since X and Z are conditionally independent given Y.

We call  the data processing inequality and it becomes an equality when 

Any extra manipulation on the input data will not provide us extra information but some noise will often distort the signal and degrade the information.

 

Fano’s inequality

Given the three random variables which form a Markov chain.

 

We want to know 

We create a random variable E representing whether the outcome has error.

 

 

Expand  in two ways

The first way of expansion:

 

Note that E is a deterministic function of  and , hence no information. This implies

and so 

 

 

By the data-processing inequality,  and therefore, . This gives

 

The second way of expansion:

Furthermore,

As a result, we obtain the Fano's inequality

 or 

With this function, we can determine a lower bound on the error probability of any decoder.

 

Reference

[1] Siyao, “Scribe Note of Problem Set 1” [Online]. Available: http://ieg5154.pbworks.com/w/page/46027275/Scribe_Note_1_2

[2] Raymond Yeung, "Lecture Notes - Chapter 3 - The I-Measure". Available: https://course.ie.cuhk.edu.hk/~ierg5154/Ch3.pdf