An urn contains r red, w white, and b black balls. Which has higher entropy, drawing k ~2 balls from the urn with replacement or without replacement? Set it up and show why. (There is both a hard way and a relatively simple way to do this.)

The case with replacement has higher entropy

Explanation:

The complete question is given:

'Drawing with and without replacement. An urn contains r red,  w white  and b black balls. Which has higher entropy, drawing k ≥ 2 balls from the urn with  replacement or without replacement?'

Solution:

- n drawing is the same irrespective of whether there is replacement or not.

-  X to denotes drawing from an urn with r red balls,  w white balls and b black balls. So, n = b + r +  w.

We have:

                                      p_X(cr) = r / n

                                      p_X(cw) = w / n

                                      p_X(cb) = b / n

- Now, if  Xi is the ith drawing with replacement then Xi are independent and p_Xi (x) = pX(x) for x e ( cr , cb , cw ).

- Now, let  Yi be the ith drawing with replacement where Yi are not independent p_Yi (x) = pX(x) for x ∈ X.

- To see this, note  Y1 =  X and assume it is true for  Yi and consider  Yi+1:

    p_Y(i+1) (cr) = p(Y(i+1),Yi).(cr, cr) + p(Y(i+1),Yi).(cr, cw) + p(Y(i+1),Yi).(cr, cb)

= pY(i+1)|Yi  (cr|cr)*pYi  (cr) +pY(i+1)|Yi  (cr|cw)*pYi (cw) + pY(i+1)|Yi  (cr|cb)*pYi (cb)

= r*( r - 1 )/n*(n-1) + w*r/n*(n-1) + b*r/n*(n-1) = r / n =  p_X(cr)

- This means, using the chain rule and the conditioning theore m:

H(Y1, Y2, . . . , Yn) =  H(Y1) +  H(Y2|Y1) +  H(Y3|Y2, Y1) + ... H(Yn|Yn−1, . . . , Y1)

=< SUM H(Yi) = n*H(X) =  H(X1, X2, . . . , Xn)

- with equality if and only if the  Yi were independent:

                          H(Y1, Y2, . . . , Yn) < H(X1, X2, . . . , Xn)

The case with replacement has higher entropy

answer:

just reverse the digits.

: )