GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
159 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 (29k points)  
retagged by | 159 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 Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users