Математичні парадокси

Словник / Ентропія

Словник · ентропія і біт

Яка монета розповідає більше: чесна чи та, що майже завжди падає гербом?

Обидві монети можуть упасти будь-яким боком, і кожне підкидання відповідає на те саме питання: герб чи решка. Здається, що й інформації вони дають порівну. Але з кривою монетою ви заздалегідь ставите на герб і майже ніколи не помиляєтеся, тож підкидання розповідає вам дуже мало. Ентропія міряє саме це: скільки ви не знали до відповіді. А біт — її одиниця: одна відповідь «так» чи «ні», коли обидві однаково ймовірні.

На пальцяхкартинки, аналогії, маленькі числа

Шар «На пальцях» приховано на всіх задачах.

Дві монети

Монета А чесна: герб і решка по 50%. Монета Б погнута і падає гербом у 99 випадках зі 100. Друг підкидає монету в іншій кімнаті й кричить вам результат.

Скільки підкидань монети Б дадуть вам стільки ж інформації, скільки одне підкидання монети А?

Вгадайте число і порахуйте біти

Комп'ютер загадав ціле число від 1 до 100. Ставте питання двох видів: «воно більше за X?» або «це X?». Повзунок або клік по клітинці обирає X. Перш ніж питати, подивіться, скільки біта це питання дасть у середньому: що ближче «так» і «ні» до порівну, то більше. Спробуйте спершу питати навмання, а потім ділити навпіл.

Питань0
Біт отримано0
Чисел лишилось100

    Біт — одна чесна відповідь «так чи ні»

    Питання, на яке «так» і «ні» однаково ймовірні, відкидає рівно половину варіантів. Це і є 1 біт. Два таких питання лишають чверть, три — восьму частину. Тому 20 вдалих питань вибирають один варіант із 220 = 1 048 576, тобто з мільйона. Звідси сила гри «20 питань»: загадати можна майже будь-що.

    Питання «це 37?» теж має дві відповіді, але майже завжди чуєте «ні», і це «ні» відкидає лише одне число зі ста. Воно дає ті самі 0,08 біта, що й монета Б. Ентропія — це скільки біт у середньому несе відповідь, або, що те саме, скільки чесних питань «так чи ні» в середньому треба, щоб її дізнатися. Для 100 рівноймовірних чисел це 6,64 біта, тож ділення навпіл ніколи не потребує більше 7 питань.

    Строготаблиці, графіки, формули

    Шар «Строго» приховано на всіх задачах.

    Крива ентропії монети

    Рухайте повзунок: це ймовірність герба. Крива показує, скільки біта несе одне підкидання. Вона найвища посередині, на чесній монеті, і падає до нуля з обох боків: монета, що завжди падає гербом, не каже нічого. Потім підкиньте монету 100 000 разів і порівняйте середнє здивування з формулою.

    Біта за підкидання–
    Здивування: герб / решка–
    Підкидань на 1 біт–

    Формула: середнє здивування

    Подія з імовірністю 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 варіантів.

    Що дізнаємосяВаріантівЕнтропія, біт
    Чесна монета21
    Кубик62,58
    Карта з колоди525,70
    Число від 1 до 1001006,64
    Людина серед 8 млрд8 млрд32,9

    Останній рядок означає: будь-яку людину на Землі можна знайти за 33 вдалих питання «так чи ні».

    Рідкісне дивує сильно, але рідко

    Шанс угадати всі 6 чисел у лотереї «6 з 49» — 1 з 13 983 816. Повідомлення «ви виграли» несе 23,7 біта, стільки ж, скільки 24 чесних підкидання монети. «Ви програли» — близько 0,0000001 біта: ви це й так знали. Саме тому новина — це те, чого не чекали. Прогноз «завтра в Сахарі сухо» майже нічого не повідомляє, хоч і завжди правдивий.

    Де рахують біти

    • Добре питання ділить навпілШукаєте, після якої зміни зламався сайт: перевіряйте середину проміжку, а не останню зміну. Те саме з опитуваннями: питання, на яке всі відповідають «так», нічого не дає.
    • Сила пароля8 випадкових малих латинських літер — 37,6 біта. 4 випадкові слова зі списку Diceware на 7776 слів — 51,7 біта, і їх легше запам'ятати. Рахується лише випадковість: «Password1» має майже нуль біт, бо його вгадують першим.
    • Стиснення текстуДля 26 літер і пробілу log2 27 ≈ 4,75 біта на знак. Але наступну літеру часто можна вгадати. Шеннон у 1951 році просив людей угадувати текст літера за літерою і оцінив ентропію англійської мови в 0,6–1,3 біта на літеру. Тому архіватори стискають текст у кілька разів.
    • Дерева рішень і WordleАлгоритми машинного навчання обирають ознаку, яка найбільше знижує ентропію відповіді: це називають приростом інформації. Так само шукають найкраще перше слово у Wordle: те, чиї підказки найрівніше ділять можливі слова.
    Глибшеузагальнення, теорія, історія

    Шар «Глибше» приховано на всіх задачах.

    Менше питань, ніж log2 n

    Погода буває чотирьох видів, тож здається, що треба 2 питання: log2 4 = 2. Але якщо сонце буває в половині днів, хмари в чверті, дощ і сніг по 1/8, вигідніше питати по черзі: «сонце?», потім «хмарно?», потім «дощ?». Сонячний день упізнаємо за одне питання, хмарний за два, решту за три. У середньому виходить 1,75 питання, і це рівно ентропія такої погоди.

    ПогодаЙмовірністьПитаньЗдивування, біт
    Сонце1/211
    Хмарно1/422
    Дощ1/833
    Сніг1/833

    Шеннон довів, що в середньому менше за ентропію питань не буває, а наблизитися до неї можна завжди. Код Морзе діє за тим самим принципом: найчастішій англійській літері E дістався найкоротший знак, одна крапка. Девід Гаффмен у 1952 році показав, як будувати найкоротший такий код для будь-яких частот, і його метод досі працює всередині ZIP, JPEG і MP3.

    Звідки слова «біт» і «ентропія»

    Клод Шеннон з Bell Labs опублікував «Математичну теорію зв'язку» у 1948 році. Там уперше біт став одиницею інформації, а саме слово, скорочення від binary digit, Шеннон приписав колезі Джону Тьюкі. Назву «ентропія» він узяв із фізики, бо формула збігається з ентропією Больцмана і Гіббса. За переказом Майрона Трайбуса (Scientific American, 1971), назву підказав Джон фон Нейман: мовляв, ніхто насправді не знає, що таке ентропія, тож у суперечці ви завжди матимете перевагу. Чи було саме так, достеменно невідомо, але історія прижилася.

    Де це трапляється

    Ще в темі «Ймовірність»

    Усі терміни →