HW4 (due October 4, 2013)
For Norman students, please submit your homework to your TA, Balakrishnan Viswanathan (balakrish AT ou DOT edu).

1. AEP and mutual Information. Let (Xi,Yi) be i.i.d. ~ p(x,y). We form the log likelihood ratio of the hypothesis that X and Y are independent v.s. the hypothesis that X and Y are dependent. What is the limit of

1/n log (p(Xn) p(Yn) / p(Xn,Yn)) ? (Cover and Thomas 3.2)

2. Piece of cake. A cake is sliced roughly in half, the largest piece being chosen each time, the other pieces discarded. We will assume that a random cut creates pieces of proportions
P = ( 2/3 , 1/3 ) with probability 3/4
and
P = ( 2/5 , 3/5 ) with probability 1/4
Thus, for example, the first cut (and choice of largest piece) may result in a piece of size 3/5. Cutting and choosing from this piece might reduce it to size (3/5)(2/3) at time 2, and so on. How large, to first order in the exponent, is the piece of cake after n cuts? (Cover and Thomas 3.3)

3. Scores. Let say the average score of a class is 60 out of 100. What can you say about the top 1/3 and bottom 1/3 of the students?