Scribd Logo
Upload

Welcome to Scribd!

  • 49 views

    (Some) Solutions For HW Set # 2

    Uploaded by

    Lokesh Singh
    This document contains solutions to problems from homework set 2 on statistics. 1. It provides two methods for showing that the entropy of a sum of random variables X and Y is equal to the conditional entropy of Y given X. 2. It derives two inequalities relating conditional entropies using the chain rule for conditional entropy and the fact that conditioning reduces entropy. 3. It derives an approximation bound for the total variation distance between the distribution of a sum of Bernoulli random variables and a compound Poisson distribution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    (Some) Solutions For HW Set # 2

    Uploaded by

    Lokesh Singh
    49 views3 pages
    This document contains solutions to problems from homework set 2 on statistics. 1. It provides two methods for showing that the entropy of a sum of random variables X and Y is equal to the conditional entropy of Y given X. 2. It derives two inequalities relating conditional entropies using the chain rule for conditional entropy and the fact that conditioning reduces entropy. 3. It derives an approximation bound for the total variation distance between the distribution of a sum of Bernoulli random variables and a compound Poisson distribution.

    Original Description:

    cv

    Original Title

    sol2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains solutions to problems from homework set 2 on statistics. 1. It provides two methods for showing that the entropy of a sum of random variables X and Y is equal to the conditional entropy of Y given X. 2. It derives two inequalities relating conditional entropies using the chain rule for conditional entropy and the fact that conditioning reduces entropy. 3. It derives an approximation bound for the total variation distance between the distribution of a sum of Bernoulli random variables and a compound Poisson distribution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    49 views3 pages

    (Some) Solutions For HW Set # 2

    Uploaded by

    Lokesh Singh
    This document contains solutions to problems from homework set 2 on statistics. 1. It provides two methods for showing that the entropy of a sum of random variables X and Y is equal to the conditional entropy of Y given X. 2. It derives two inequalities relating conditional entropies using the chain rule for conditional entropy and the fact that conditioning reduces entropy. 3. It derives an approximation bound for the total variation distance between the distribution of a sum of Bernoulli random variables and a compound Poisson distribution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Statistics G8243

    Thursday, February 26, 2009


    Handout #8

    (Some) Solutions for HW Set # 2


    1. Entropy of a sum.

    (a) Here’s the way most of you did the problem: Since Z = X + Y , P (Z = z|X = x) =
    P (Y = z − x|X = x).
    X
    H(Z|X) = P (x)H(Z|X = x)
    X X
    = − P (x) P (Z = z|X = x) log P (Z = z|X = x)
    x z
    X X
    = P (x) P (Y = z − x|X = x) log P (Y = z − x|X = x)
    x y
    X
    = P (x)H(Y |X = x)
    = H(Y |X).

    Here’s another way, which is more cute. Note that (X, Y ) and (X + Y, X − Y ) are
    of course in a 1-1 relationship. Then,

    H(X) + H(Y |X) = H(X, Y )


    = H(X + Y, X − Y )
    = H(X, X + Y, X − Y )
    = H(X) + H(X + Y |X) + H(X − Y |X + Y, X)
    = H(X) + H(X + Y |X),

    and the result follows.


    (b) If X and Y are independent, then H(Y |X) = H(Y ). Since conditioning reduces
    entropy, H(Z) ≥ H(Z|X) = H(Y |X) = H(Y ) . Similarly we can show that H(Z) ≥
    H(X).
    (c) Consider the following joint distribution for X and Y . Let
    
    1 with probability 1/2
    X = −Y =
    0 with probability 1/2

    Then H(X) = H(Y ) = 1, but Z = 0 with prob. 1 and hence H(Z) = 0.


    (d) We have
    H(Z) ≤ H(X, Y ) ≤ H(X) + H(Y )
    because Z is a function of (X, Y ) and H(X, Y ) = H(X) + H(Y |X) ≤ H(X) + H(Y ).
    We have equality iff (X, Y ) is a function of Z and H(Y ) = H(Y |X), i.e., X and Y
    are independent.
    2. Inequalities.
    (a) Using the chain rule for conditional entropy,

    H(X, Y |Z) = H(X|Z) + H(Y |X, Z) ≥ H(X|Z),

    with equality iff H(Y |X, Z) = 0, that is, when Y is a function of X and Z.
    (b) Using the chain rule for entropy and the fact that conditioning reduces entropy,

    H(X, Y, Z) − H(X, Y ) = H(Z|X, Y )


    ≤ H(Z|X)
    = H(X, Z) − H(X) ,

    with equality iff Y and Z are conditionally independent given X.


    3. A compound Poisson approximation bound. Let X1 , X2 , . . . , Xn be IID Bern(λ/n) ran-
    dom variables, let Y1 , Y2 , ..., Yn be an independent sequence of IID random variables with
    distribution Q = (1/2, 1/2) on the set {1, 2}, let Z1 , Z2 , . . . , Zn are IID CPo(λ/n, Q), If
    we write Tn for the sum of the Zi , then PTn is the CPo(λ, Q) distribution. Following the
    same steps as those used for Poisson

    D(PSn kCPo(λ, Q)) = D(PSn kPTn )


    ≤ D(PX1 Y1 ,...,Xn Yn kPZ1 ,...,Zn )
    = nD(PX1 Y1 kPZ1 ).

    Now if X ∼ Bern(p), Y ∼ Q and Z ∼ CPo(p, Q) are independent, then it is easy to


    calculate that,
    p
    D(PXY kPZ ) ≤ p2 + (1 − p)[p + log(1 − p)] − log(1 + p/4) ≤ p2 ,
    2
    and combining the last two bounds, taking p = λ/n yields the result.
    4. Monotonicity. Note that we can write,
    1 X
    P̂n+1 (x) = I{X =x}
    n + 1 1≤i≤n+1 i
    1 X 1X
    = I{Xi =x}
    n + 1 1≤j≤n+1 n i6=j
    1 X
    = P̂ (j) ,
    n + 1 1≤j≤n+1 n

    (j)
    where P̂n is the empirical distribution induced by X1 , . . . , Xj−1 , Xj+1 , . . . , Xn . Then, by
    the convexity of the relative entropy,
     1 X  1 X
    (j)
    D(P̂n+1 kQ) = D P̂n Q ≤ D(P̂n(j) kQ),
    n + 1 1≤j≤n+1 n + 1 1≤j≤n+1
    (j)
    and since the P̂n all have the same distribution, taking expectations yields,
       
    E D(P̂n+1 kQ) ≤ E D(P̂n kQ) ,

    as claimed.

    5. Estimating the entropy. The fact that E[H(P̂n )] ≤ H(P ) follows from the concavity of
    the entropy (using Jensen’s inequality), upon noting that E(P̂n ) = P .

    6. Size of type-class. This is mostly straightforward computations.

    7. Hypothesis testing. Stein Lemma says we should use the decision region,

    P1n (xn1 )
    Bn∗ = Bn∗ () = {xn1 ∈ An : 2D(P1 kP2 )− ≤ ≤ 2D(P1 kP2 )+ }.
    P2n (xn1 )

    Under Q, the likelihood ratio of interest has,

    1 P n (X n ) X P1 (x)
    log 1n 1n → R := Q(x) log = D(QkP2 ) − D(QkP1 ),
    n P2 (X1 ) x
    P 2 (x)

    in probability, as n → ∞.
    Now consider three cases: R < D(P1 kP2 ) − , D(P1 kP2 ) −  < R < D(P1 kP2 ) + , and
    R > D(P1 kP2 ) + .

    You might also like