GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
183 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$
asked in Probability by Veteran (32.8k points)  
edited by | 183 views

1 Answer

+6 votes
Best answer

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 by


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users