Minimum expected length of a message

Question

A bag contains 16 balls of 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?
(a)3/2 (b)log 5 (c)15/8 (d)31/16 (e)2

According to me, since the ball is taken out with replacement. At any time, there are 16 balls of 5 different colors in the bag. To encode 5 colors, ceiling of log5 (base 2) i.e. 3 bits should be needed but the answer given is (15/8). Can someone point out my mistake and provide some hint for the correct solution?

Answer 1

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 bits on average

Answer 2

Your answer is right as the maximum value needed for encoding. But consider the following coding scheme 1 - red (1/2 prob), 01 - blue (1/4 prob), 00 - green (1/8 prob), 001 - black (1/16 prob), 000 - white (1/16 prob) multiply message length by probability and you should have 1 + 5/8 ( not 15/8 ... though)