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 (X_{i},Y_{i}) 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(X^{n}) p(Y^{n}) / p(X^{n},Y^{n})) ? (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?