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.)

'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)

= 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)

Answer: The case with replacement has higher entropy