For Q2, what are the assumptions of X^n nd Y^n? Are they generated from the same iid source?

And for Q3(a), what is the role of \epsilon? By "able to decode correctly", do you mean that ALL Y^n must be decoded correctly, or do you mean we allow some error in terms of \epsilon?

In Q2, what does "always" mean? Is it 100%, or allow some errors?

Mak: Q2: Your answer should hold for ARBITRARY X^n, Y^n (regardless of how they're generated).
Q3(a), the role of espilon is to be an arbitrarily small positive constant. by decoding correctly, we mean that an arbitrarily large fraction of Y^n, as some function of \epsilon.

Yuchen: Q2: always = 100% = no errors.

Thanks for the answers.

So for Q3(a), by "needs to transmit at least n(H(Y|X) − \epsilon) bits to Bob", do you mean that there must exist SOME Y^n that requires us to send at least n(H(Y|X) − \epsilon) bits? Or the EXPECTED number of bits to be transmitted is at least n(H(Y|X) − \epsilon)?

(Tong walks into my office to ask some questions)

Tong: asks about Q2: What does the probability of error mean?

Sid: As I'd said in my previous comment, your scheme should work for any X^n, Y^n. There is no randomness in X^n, Y^n -- the only randomness is from whatever scheme you may choose to use.

More precisely, X^n, Y^n are chosen somehow. Then, independently, you choose a scheme, possibly with some random variable R. For each X^n, Y^n, the probability of error over R should be at most the quantity given in the question.


Tong: Q4: Do the elements of Z come from only X or Y, or possibly from some other set too?

The random variable Z is the same as the random variable with probability p, and the same as the random variable Y with probability 1-p. There are no other possibilities for Z since p + 1-p = 1.

Tong: Followup question -- but what if X and Y intersect? The question does not cover this case.

Sid: Well, with probability p, Z equals X, i.e., it equals some value in the domain of X. With probability 1-p it equals Y, i.e, equals some value in the domain of Y. It is quite possible that there are some common values in the domains (the question indeed says this explicitly in the hint), but Z is still well-defined.

No reply for my latest question? = =

hi, do we have to prove the things we have already proved in class? like the probability of an element is from the strongly typical set?

and is the polynomial time complexity a rigid requirement for question 4(b)? do we have to prove it?

can i submit the paper directly to you, Michael ?

Liu Ke: You can put it inside the course assignment box on 8/F, SHB. Of course, I recommend you to scan and email the answers to both Prof. Jaggi and me.

i put it in the assignment box since i could not find the scanner