Name: Student Number: EE 4TM4 (DIGITAL COMMUNICATIONS II): MID-TERM EXAMINATION Instructor: Dr. Jun Chen Duration of Examination: 50 Minutes Recall that T (n) (X) = { xn : ∣∣∣∣ 1nN(x|xn)− pX(x) ∣∣∣∣ ≤ pX(x) for all x ∈ X} , T (n) (Y ) = { yn : ∣∣∣∣ 1nN(y|yn)− pY (y) ∣∣∣∣ ≤ pY (y) for all y ∈ Y} , T (n) (X,Y ) = { (xn, yn) : ∣∣∣∣ 1nN(x, y|xn, yn)− pX,Y (x, y) ∣∣∣∣ ≤ pX,Y (x, y) for all (x, y) ∈ X × Y} , T (n) (Y |xn) = { yn : (xn, yn) ∈ T (n) (X,Y ) } . Prove the following results. 1) Let (xn, yn) ∈ T (n) (X,Y ) and p(xn, yn) = ∏n i=1 pX,Y (xi, yi). a) xn ∈ T (n) (X) and yn ∈ T (n) (Y ). 5% b) 2−n(1+)H(X) ≤ p(xn) ≤ 2−n(1−)H(X) and 2−n(1+)H(Y ) ≤ p(yn) ≤ 2−n(1−)H(Y ). 5% c) 2−n(1+)H(X|Y ) ≤ p(xn|yn) ≤ 2−n(1−)H(X|Y ) and 2−n(1+)H(Y |X) ≤ p(yn|xn) ≤ 2−n(1−)H(Y |X). 5% d) 2−n(1+)H(X,Y ) ≤ p(xn, yn) ≤ 2−n(1−)H(X,Y ). 5% 2) |T (n) (X,Y )| ≤ 2n(1+)H(X,Y ). 10% 3) If p(xn, yn) = ∏n i=1 pX,Y (xi, yi), then limn→∞ P{(Xn, Y n) ∈ T (n) (X,Y )} = 1. 10% 4) |T (n) (X,Y )| ≥ (1− )2n(1−)H(X,Y ) for n sufficiently large. 10% 5) For every xn ∈ X n, we have |T (n) (Y |xn)| ≤ 2n(1+)H(Y |X). 10% 6) Let X ∼ pX(x) and Y = g(X). Let xn ∈ T (n) (X). Then yn ∈ T (n) (Y |xn) if and only if yi = g(xi) for i ∈ [1 : n]. 10% 7) Let (X,Y ) ∼ pX,Y (x, y). Suppose that xn ∈ T (n)′ (X) and Y n ∼ p(yn|xn) = ∏n i=1 pY |X(yi|xi). Then, for every > ′, we have limn→∞ P{(xn, Y n) ∈ T (n) (X,Y )} = 1. 20% 8) If xn ∈ T (n)′ (X) and ′ < , then |T (n) (Y |xn)| ≥ (1− )2n(1−)H(Y |X) for n sufficiently large. 10% THE END.
