TIFR CSE 2012 | Part B | Question: 7

Question

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?

• A. $\dfrac{3}{2}\\$
• B. ${\log 5}\\$
• C. $\dfrac{15}{8}\\$
• D. $\dfrac{31}{16}\\$
• E. $2$

Answer 1

Answer is (C)

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:

$\begin{array}{llll}  \text{red} & 1 \\ \text{blue} & 01 \\ \text{green} & 001 \\ \text{white} & 0001  \\ \text{black} & 0000 \\ \end{array}$

On average from $16$ draws there will be

$\begin{array}{llll}  \text{8 reds} & =  \ \text{8 bits} \\  \text{4 blues} & = \ \text{8 bits} \\ \text{2 greens} & =\; \text{6 bits} \\  \text{1 white} & =  \ \text{4 bits}  \\ \text{1 black} & = \ \text{4 bits} \\ \end{array}$

for a total of $\dfrac{30}{16} =\dfrac{15}{8}$ bits on average.

Comments

@Rishabh Gupta 2 

if so , 

then we can use 0,1,10,01,11 => 1.25 (optimal) but least option is 1.5 itself so may be Huffman encoding is expected by examinar . Please verify

---

"on average from 16 draws there will be" . why 16 draws ?   And how is this average decieded ? The solution seems made up just to get to the answer

---

For just 1 draw also the answer is same @paraskk

.5+.5+3/8+4/16+4/16 = 15/8 bits on avg