Словник / Ентропія
Обидві монети можуть упасти будь-яким боком, і кожне підкидання відповідає на те саме питання: герб чи решка. Здається, що й інформації вони дають порівну. Але з кривою монетою ви заздалегідь ставите на герб і майже ніколи не помиляєтеся, тож підкидання розповідає вам дуже мало. Ентропія міряє саме це: скільки ви не знали до відповіді. А біт — її одиниця: одна відповідь «так» чи «ні», коли обидві однаково ймовірні.
Шар «На пальцях» приховано на всіх задачах.
Монета А чесна: герб і решка по 50%. Монета Б погнута і падає гербом у 99 випадках зі 100. Друг підкидає монету в іншій кімнаті й кричить вам результат.
Скільки підкидань монети Б дадуть вам стільки ж інформації, скільки одне підкидання монети А?
Близько 12: одне підкидання монети Б несе лише 0,08 біта.
Інформація — це не кількість можливих відповідей, а те, наскільки відповідь вас здивувала. Чесна монета щоразу ставить вас перед повною невідомістю: вгадати неможливо, і кожен результат — справжня новина. З монетою Б ви кажете «герб» ще до підкидання й маєте рацію в 99 разах зі 100. Рідкісна решка — велика новина, але вона трапляється раз на сотню підкидань, тож у середньому монета Б майже нічого не повідомляє.
Комп'ютер загадав ціле число від 1 до 100. Ставте питання двох видів: «воно більше за X?» або «це X?». Повзунок або клік по клітинці обирає X. Перш ніж питати, подивіться, скільки біта це питання дасть у середньому: що ближче «так» і «ні» до порівну, то більше. Спробуйте спершу питати навмання, а потім ділити навпіл.
Питання, на яке «так» і «ні» однаково ймовірні, відкидає рівно половину варіантів. Це і є 1 біт. Два таких питання лишають чверть, три — восьму частину. Тому 20 вдалих питань вибирають один варіант із 220 = 1 048 576, тобто з мільйона. Звідси сила гри «20 питань»: загадати можна майже будь-що.
Питання «це 37?» теж має дві відповіді, але майже завжди чуєте «ні», і це «ні» відкидає лише одне число зі ста. Воно дає ті самі 0,08 біта, що й монета Б. Ентропія — це скільки біт у середньому несе відповідь, або, що те саме, скільки чесних питань «так чи ні» в середньому треба, щоб її дізнатися. Для 100 рівноймовірних чисел це 6,64 біта, тож ділення навпіл ніколи не потребує більше 7 питань.
Шар «Строго» приховано на всіх задачах.
Рухайте повзунок: це ймовірність герба. Крива показує, скільки біта несе одне підкидання. Вона найвища посередині, на чесній монеті, і падає до нуля з обох боків: монета, що завжди падає гербом, не каже нічого. Потім підкиньте монету 100 000 разів і порівняйте середнє здивування з формулою.
Подія з імовірністю p, коли стається, приносить −log2 p біта. Що рідша подія, то більше здивування: результат із шансом 1/2 дає 1 біт, із шансом 1/8 — 3 біти. Ентропія — це здивування, усереднене за всіма результатами з їхніми ймовірностями:
H = −Σ pi · log2 pi
Для монети Б: 0,99 · 0,0145 + 0,01 · 6,64 ≈ 0,08 біта. Решка дивує на 6,64 біта, рівно як угадане з першої спроби число від 1 до 100, але трапляється так рідко, що майже не важить у середньому. Якщо ж n варіантів однаково ймовірні, формула дає просто H = log2 n, і це найбільша можлива ентропія для n варіантів.
| Що дізнаємося | Варіантів | Ентропія, біт |
|---|---|---|
| Чесна монета | 2 | 1 |
| Кубик | 6 | 2,58 |
| Карта з колоди | 52 | 5,70 |
| Число від 1 до 100 | 100 | 6,64 |
| Людина серед 8 млрд | 8 млрд | 32,9 |
Останній рядок означає: будь-яку людину на Землі можна знайти за 33 вдалих питання «так чи ні».
Шанс угадати всі 6 чисел у лотереї «6 з 49» — 1 з 13 983 816. Повідомлення «ви виграли» несе 23,7 біта, стільки ж, скільки 24 чесних підкидання монети. «Ви програли» — близько 0,0000001 біта: ви це й так знали. Саме тому новина — це те, чого не чекали. Прогноз «завтра в Сахарі сухо» майже нічого не повідомляє, хоч і завжди правдивий.
Шар «Глибше» приховано на всіх задачах.
Погода буває чотирьох видів, тож здається, що треба 2 питання: log2 4 = 2. Але якщо сонце буває в половині днів, хмари в чверті, дощ і сніг по 1/8, вигідніше питати по черзі: «сонце?», потім «хмарно?», потім «дощ?». Сонячний день упізнаємо за одне питання, хмарний за два, решту за три. У середньому виходить 1,75 питання, і це рівно ентропія такої погоди.
| Погода | Ймовірність | Питань | Здивування, біт |
|---|---|---|---|
| Сонце | 1/2 | 1 | 1 |
| Хмарно | 1/4 | 2 | 2 |
| Дощ | 1/8 | 3 | 3 |
| Сніг | 1/8 | 3 | 3 |
Шеннон довів, що в середньому менше за ентропію питань не буває, а наблизитися до неї можна завжди. Код Морзе діє за тим самим принципом: найчастішій англійській літері E дістався найкоротший знак, одна крапка. Девід Гаффмен у 1952 році показав, як будувати найкоротший такий код для будь-яких частот, і його метод досі працює всередині ZIP, JPEG і MP3.
Клод Шеннон з Bell Labs опублікував «Математичну теорію зв'язку» у 1948 році. Там уперше біт став одиницею інформації, а саме слово, скорочення від binary digit, Шеннон приписав колезі Джону Тьюкі. Назву «ентропія» він узяв із фізики, бо формула збігається з ентропією Больцмана і Гіббса. За переказом Майрона Трайбуса (Scientific American, 1971), назву підказав Джон фон Нейман: мовляв, ніхто насправді не знає, що таке ентропія, тож у суперечці ви завжди матимете перевагу. Чи було саме так, достеменно невідомо, але історія прижилася.
Наука про те, скількома способами можна впорядкувати або вибрати речі: перестановки n!, сполучення C(n, k).
Добре перетасована колода майже напевно лежить у порядку, якого ще не бачив ніхто й ніколи.
Шанс події за умови, що вже відомо щось інше.
Майже всі баскетболісти НБА високі, але майже всі високі люди не баскетболісти.
Події незалежні, якщо знання про одну не змінює шансів іншої.
Після п'яти орлів поспіль решка не стає ймовірнішою: монета нічого не пам'ятає.
Правило, як змінювати впевненість, коли з'являються нові докази: апріорні шанси × сила доказу.
Два слабкі докази разом бувають сильними, а один яскравий нічого не важить, якщо твердження було малоймовірним.
Скільки успіхів буде в n незалежних спробах, якщо в кожній шанс той самий p.
Підкиньте монетку 100 разів: рівно 50 орлів — найімовірніший результат, але випадає він лише в 8 випадках зі 100.