Навчання / Бібліотека / Ймовірність

Заощаджені біти в журналі

ЙмовірністьСереднє

Журнал зберігає стан спреду, який має $6$ значень з імовірностями $\frac{1}{2}$ , $\frac{1}{8}$ , $\frac{1}{8}$ , $\frac{1}{8}$ , $\frac{1}{16}$ і $\frac{1}{16}$ . Двійковий код фіксованої довжини використовує найменше цілих бітів, за яких кожне значення має своє слово. Скільки бітів загалом оптимальний префіксний код заощаджує порівняно з цим кодом на $8000$ станах у середньому? Дайте ціле число.

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Знайдіть ентропію, адже код досягає її, коли ймовірності це степені $\frac{1}{2}$ .

Розв’язок

Усі ймовірності є степенями $\frac{1}{2}$ , тож оптимальний префіксний код має довжини слів $1$ , $3$ , $3$ , $3$ , $4$ , $4$ , а його середня довжина дорівнює ентропії: $\frac{1}{2} \times 1 + \frac{3}{8} \times 3 + \frac{1}{8} \times 4 = \frac{17}{8}$ біта.
Щоб розрізнити $6$ значень, потрібно $3$ біти, бо $2^{2} = 4$ замало, а $2^{3} = 8$ досить.
Економія на стан дорівнює $3 - \frac{17}{8} = \frac{7}{8}$ , тож загалом $8000 \times \frac{7}{8} = 7000$ .

Відповідь: $7000$

Наступна задача Назад до бібліотеки