ESE 523: Exam 1EDITEDProfessor Joseph A. O’SullivanOctober 26, 2005This is a closed book closed notes exam. It is scheduled to last for 1.5 hours. All students must do theirown work and are bound by the SEAS honor code. If you do not undertand a question, clearly state theassumptions used in trying to find a solution.NAME:Problem Score1.2.3.4.5.6.Total11(15points)Let (X1,X2,...,Xn) be arbitrary discrete random variables with known joint probability distribution p(x1,x2,...,xn).In this question, you will explore the information value of additional measurements.a. Future measurements. Let h1|k= H(X1|X2,X3,...,Xk), that is the entropy of X1given measurementsup to time k. Show that h1|k≥ h1|k+1. Denote the gain in information from the next measurement by i1|k+1,that is, i1|k+1= h1|k− h1|k+1.b. Past measurements. Let hn|n−k= H(Xn|Xn−1,Xn−2,...,Xn−k), that is the entropy of Xngivenmeasurements in the past to time n − k. Show that hn|n−k≥ hn|n−k−1. Denote the gain in information fromthe next measurement by in|n−k−1,thatis,in|n−k−1= hn|n−k− hn|n−k−1.c. Show that i1|n= in|1. That is, the information about the past equals the information about thefuture.22(20points)A code designer claims to have designed a binary code for an alphabet of size fourteen with codelengths {2,3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6}.a. Can these codeword lengths correspond to a prefix code? Justify your answer.b. Can these codeword lengths be the result of a Huffman encoding scheme? Justify your answer.c. Suppose that a source has fourteen symbols that are equally likely. What are the optimal binarycodelengths?d. For the source with equally likely symbols, what is the cost (in average number of bits per symbol) ofusing the code provided by the designer relative to the optimal code?33(15points)Suppose that there are eight horses in a set of i.i.d. horse races. The odds oi,i=1, 2,...,8are{4, 8, 8, 8,16, 16, 16, 16}, respectively. Suppose that all horses are equally likely to win.a. Assuming that all money must be bet every iteration, what is the optimum doubling rate?b. Suppose that you do not know that the true distribution is uniform. Suppose that you bet a Dutchbook. That is, you bet bi=1oion each horse and retain fraction 1 −8i=1bias cash. What is the doublingrate? What is the loss in doubling rate relative to the optimal strategy?44(20points)Consider a channel whose input and output alphabets have cardinality four. The transition probabilitiesQ(yj|xi)=Qij(with i indexing rows and j indexing columns) areQ =⎡⎢⎢⎣0.75 0.25 0 000.75 0.25 0000.75 0.250.25 0 0 0.75⎤⎥⎥⎦(1)a. What is the capacity of this channel? What distribution achieves the maximum?b. Suppose that only the first and the third inputs are used. What is the probability of error? What isthe capacity of this system?55(15points)Consider a stationary Markov chain with four states. The transition probabilities do not depend on timeand are given by the matrix P (Xk= ξj|Xk−1= ξi)=Qij(with i indexing rows and j indexing columns)whereQ =⎡⎢⎢⎣0.75 0.25 0 000.75 0.25 0000.75 0.250.25 0 0 0.75⎤⎥⎥⎦(2)Find the entropy rate of this Markov chain.66(15points)Let A, B, X, and Y be arbitrary discrete-valued random variables. Prove thatI(A; B) ≤ I(X; A)+I(Y ; B) − I(X, Y ; A, B). (3)For extra credit, interpret the condition for equality in terms of independence of random