EEET 5105 Information Theory and Coding Assignment 2 Due date: 5/9/2016. Please submit the hardcopy in class. Remember to put your student ID and name. Problems: 1. Markov Chain. Let A – B – U – W – X – Y – Z form a Markov chain. (a) Draw the information diagram. (b) Rewrite I(X; Y) – I(A; Z) as a summation of nonnegative quantities (entropy or mutual information) in order to prove that I(A; Z) ≤ I(X; Y). (c) Let A be uniformly distributed in an alphabet with size equal to M and let ϵ = Pr[A ≠ Z]. What is the lower bound on I(X;Y) in terms of M and ϵ? 2. Stationary processes. Let . . . , X−1, X0, X1, . . . be a stationary (not necessarily Markov) stochastic process. Which of the following statements are true? If it is true, prove it; otherwise, provide a counterexample. (Hints: rewrite the quantities in terms their definitions and use P. 3 in Chapter 3. The fact that condition does not increase entropy may be useful too.) (a) H(Xn|X0) = H(X−n|X0) . (b) H(Xn|X0) ≥ H(Xn−1|X0) . (c) H(Xn|X1, X2, . . . , Xn−1, Xn+1) is non-increasing in n. (d) H(Xn|X1, . . . , Xn−1, Xn+1, . . . , X2n) is non-increasing in n. 3. Typicality. Let PX(1) = 0.5, PX(2) = 0.3 and PX(3) = 0.2. If X1, X2, …, X10 are independent and identically distributed according to PX. Suppose ϵ = 0.01 and δ = 0.2. The empirical distribution of a sequence x is denoted as QX. a) If x = (x1, x2, x3, …, x10) ∈ Wn[X]ϵ , what is the range of p(x1, x2, x3, …, x10)? b) What is the range of |Wn[X]ϵ|? [Suppose n is sufficiently large in this case.] c) Give an example that x ∈ Wn[X]ϵ and verify your example. d) Give an example that x ∉ Wn[X]ϵ and verify your example. e) Show that the definition of weakly typical set can be rewritten as |D(QX|| PX) + H(QX) – H(PX)| ≤ ϵ f) Which of the following are strongly typical sequences? [1111122233], [1111222334], [1112223333], [1111222233]