Минимальная ожидаемая длина сообщения

Question

Сумка содержит 16 шаров следующих цветов: 8 красных, 4 синих, 2 зеленых, 1 черный и 1 белый. Аниша случайно выбирает шар из сумки и сообщает Бабу свой цвет, используя цепочку нулей и единиц. Она заменяет мяч в сумке и многократно повторяет этот эксперимент. Какова минимальная ожидаемая длина сообщения, которое она должна передать Бабу за эксперимент?
(а) 3/2 (б) войти 5 (с) 15/8 (г) 31/16 (е) 2

По мне, так как мяч вынимают с заменой. В любое время в сумке есть 16 шариков из 5 разных цветов. Чтобы закодировать 5 цветов, необходим потолок log5 (базовый 2), т. Е. Требуется 3 бита, но ответ будет равен (15/8). Может кто-то указать на мою ошибку и дать некоторый намек на правильное решение?

Answer 1

Используя статическое сжатие huffman, вы можете кодировать более распространенные цвета в меньшем количестве бит, чем в редких цветах, поскольку в этом случае можно ожидать, что обычно будут выбраны обычные цвета.

например:

red 1 
blue 01 
green 001 
white 0001 
black 0000 

в среднем от 16 ничьи будет

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

в общей сложности 30/16 бита в среднем

Answer 2

Вашего ответа прямо как максимальное значение необходимых для кодирования. Но рассмотрим следующую схему кодирования: 1 - красный (1/2 prob), 01 - синий (1/4 prob), 00 - зеленый (1/8 проба), 001 - черный (1/16 prob), 000 - белый (1/16 prob) умножить длину сообщения по вероятности, и вы должны иметь 1 + 5/8 (не 15/8 ... хотя)