• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

• You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View

# Scribe Note 2( 22-Jan )

last edited by 15 years, 2 months ago

1. Fano's inequality

Intuition:  If Y is a function of X, Y = g(X), then  H(Y|X) =0 . If we can only estimate X from Y with some probability of  error P(e), we can image that H(X|Y) will be small if P(e) is small ,and   H(X|Y)->0 , as P(e) -> 0.

Proof:  we model the process as a Markov Chain

X------> Y-------->

we define E as follows:

E  =  1,    if

=  0,    if

We expand  in two ways,

for the second equation,

(1)

,which means

for the first equation, since E is a function of X and , then

now,                                                          (2)

From (1),(2), we obtain

(3)

Next , we will prove

From data-processing inequality, we have

since

,we obtain

(4)

From (3),(4)

viz

2. Converse for source coding theorem.

---->,------> form a markov chain.

(i.i.d)

( H(x) = H(x|y) + I(x;y) )

(data processing inequality in the above Markov chain)

( I(x;y)<= H(y))

( H(x)<= log|X| )

(Fano's inequality)

,which means

#### Mak said

at 8:12 pm on Feb 9, 2009

Is this note finished?

It is written in Scribe Notes 2 Feb that, "Last time, we proved the converse of the source coding theorem by ingenious use of several information-theoretic inequalities." But I can't seem to find the related info here?

#### Cho Yiu Ng said

at 8:19 pm on Feb 10, 2009

As I recall, there were certain discussions about this. So, Cheng Fan, would you mind writing down what we have discussed?

#### Harry said

at 10:28 pm on Feb 14, 2009

sorry,professor in class indeed discussed something about the converse of the source coding theorem. I will update it .

#### Cho Yiu Ng said

at 8:26 pm on Feb 22, 2009

Thanks Cheng Fan! Are there any comments?

#### Cho Yiu Ng said

at 11:32 am on Feb 24, 2009

As a number of you made a mistake in the problem set 3, I ask a question here (which was raised by Yuchen in the lecture as well). Is it correct to apply Fano's Inequality in the converse of Source Coding Theorem above? Please compare it carefully with the Fano's Inequality. On the other hand, if such application is incorrect, can we change the proof a little bit so that we can apply the Fano's Inequality?

#### Silas said

at 4:39 pm on Feb 24, 2009

I recall that we can follow the steps of the proof in the Fano's inequality to obtain the last inequality. The Fano's inequality utilizes the last inequality mentioned in the scribe note.

#### Silas said

at 4:41 pm on Feb 24, 2009

I see. We can make g(X) = X and apply the Fano's inequality.

#### Cho Yiu Ng said

at 4:20 pm on Feb 25, 2009

What is g(X)?