168 views

A bag contains $16$ balls of the following colors: 8 red, 4 blue, 2 green, 1 black, and 1 white. Anisha picks a ball randomly from the bag, and messages Babu its color using a string of zeros and ones. She replaces the ball in the bag, and repeats this experiment, many times. What is the minimum expected length of the message she has to convey to Babu per experiment?

1. $3/2$
2. $\log 5$
3. $15/8$
4. $31/16$
5. $2$
retagged | 168 views

using static huffman compression you can encode the more common colours in fewer bits than the rare colours, that being the case on can expect that common colours will usually be chosen.

eg:

red    1
blue   01
green  001
white  0001
black  0000


on average from 16 draws there will be

8 reds   = 8 bits
4 blues  = 8 bits
2 greens = 6 bits
1 white  = 4 bits
1 black  = 4 bits


for a total of 30/16 = 15/8 bits on average

answered by (379 points)
selected