Ентропія Шеннона

Ідея: Біти на повідомлення

Стрічка надсилає оновлення, угоди, скасування й зупинки з імовірностями $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$.

• Сталий код потребує $2$ біти на кожне
• Кодові слова $0$, $10$, $110$, $111$: короткі для частих
• Жодне слово не починає інше, тож роздільники не потрібні

Приклад: Середня довжина коду

Для кодових слів $0$, $10$, $110$, $111$ з імовірностями $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$ яка середня довжина в бітах?

1. Довжини $1$, $2$, $3$, $3$
2. $\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{3}{8}=\frac{7}{4}$ біта

Формула: Ентропія

$H(X)=-\sum p(x){\log }_{2}p(x)$

Середня несподіванка −log₂ p у бітах: нижня межа для будь-якого коду без втрат.

Ідея: Несподіванка

Кожна довжина коду вище дорівнює $-{\log }_{2}p$: імовірність $\frac{1}{8}$ забрала $3$ біти.

• Рідкісні наслідки дивують більше
• Певний наслідок не несе несподіванки
• $H$ рахує в середньому добрі запитання «так чи ні»

Формула: Незалежні джерела додаються

$H(X,Y)=H(X)+H(Y)\text{for}\text{independent}X,Y$

Імовірності незалежних подій перемножуються, а логарифм перетворює добутки на суми.

Ідея: Обидва кінці шкали

На $n$ значеннях $0\le H\le {\log }_{2}n$ для будь-якого розподілу.

• $H=0$, коли одне значення певне
• $H={\log }_{2}n$, коли всі рівноймовірні
• $8$ рівних секторів: ${\log }_{2}8=3$ біти

Швидка перевірка: Тип і майданчик

Кожне повідомлення ще й надходить з майданчика A, B або C з імовірностями $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$, незалежно від типу. Яка ентропія пари?

Типова помилка: Ентропія не дисперсія

Виплати $1$, $2$, $3$ і $1$, $100$, $10000$ з однаковими ймовірностями мають однакову ентропію.

Натомість $H$ питає, який наслідок настане; дисперсія питає, наскільки наслідки віддалені.

Ідея: Як сказати це на співбесіді

Ентропія це середня кількість бітів оптимального коду: невизначеність наслідку.

• Покажіть на ймовірностях, що є степенями $\frac{1}{2}$
• Тоді кожен логарифм цілий