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

У Вікіпедії є статті про інші значення цього терміна: Ентропія (значення).

Два біти ентропії: у випадку двох справедливих підкидань монети, ентропія інформації в бітах є логарифмом за основою 2 з числа можливих результатів; за двох монет існує чотири можливі результати, та два біти ентропії. Взагалі, інформаційна ентропія є усередненою кількістю інформації, що несе подія, за розгляду всіх можливих результатів.

Інформаці́йна ентропі́я (англ. information entropy) — це усереднена швидкість, із якою продукує інформацію стохастичне джерело даних.

Мірою інформаційної ентропії, пов'язаною з кожним можливим значенням даних, є від'ємний логарифм функції маси ймовірності для цього значення: ${\textstyle S=-\sum _{i}P_{i}\ln {P_{i}}}$ . Таким чином, коли джерело даних має менш імовірне значення (наприклад, коли стається низькоймовірна подія), то ця подія несе більше «інформації» («неочікуваності»), ніж коли джерело даних має більш імовірне значення. Визначена таким чином кількість інформації, що передається кожною подією, стає випадковою змінною, чиє математичне сподівання є інформаційною ентропією. Взагалі, ентропію позначають безлад або невизначеність, і визначення ентропії, що застосовують в теорії інформації, є прямим аналогом визначення, що застосовують у статистичній термодинаміці. Поняття інформаційної ентропії було введено Клодом Шенноном у його праці 1948 року «Математична теорія зв'язку».

Базова модель системи передавання даних складається з трьох елементів: джерела даних, каналу зв'язку та приймача, і, за виразом Шеннона, «фундаментальною задачею зв'язку» є те, щоби отримувач був здатен встановлювати, які дані було породжено джерелом, на основі сигналу, що він отримує каналом.^{:379–423 та 623–656} Ентропія забезпечує абсолютну межу найкоротшої можливої усередненої довжини безвтратного стиснювального кодування даних, продукованих джерелом, і якщо ентропія джерела є меншою за пропускну спроможність каналу зв'язку, то дані, породжувані цим джерелом, можливо надійно передавати приймачеві (принаймні теоретично, можливо, нехтуючи деякими практичними міркуваннями, такими як складність системи, потрібної для передавання даних, або кількості часу, що це передавання цих даних може забирати).

Інформаційну ентропію зазвичай вимірюють в бітах (що також називають «шеннонами», англ. bit, shannon), або іноді в «натуральних одиницях» (натах, англ. nat), або в десяткових цифрах (що називають «дитами», «банами» або «гартлі»). Одиниця вимірювання залежить від основи логарифма, що використовують для визначення ентропії.

Логарифм розподілу ймовірності є корисним як міра ентропії тому, що для незалежних джерел він є адитивним. Наприклад, ентропія підкидання справедливої монети складає 1 біт, а ентропією m підкидань є m біт. У простому поданні, для представлення величини, що може набувати одного з n значень, потрібно log₂(n) бітів, якщо n є степенем числа 2. Якщо ці значення є однаково ймовірними, то ентропія (в бітах) дорівнює цьому числу. Якщо ж трапляння одного з цих значень є ймовірнішим за інші, то спостереження трапляння цього значення є менш інформативним, ніж якби трапився не такий звичайний результат. І навпаки, рідкісніші події при їхньому спостереженні надають більше інформації. Оскільки спостереження менш імовірних подій трапляється рідше, в підсумку виходить, що ентропія (при розгляданні її як усередненої інформації), отримувана від нерівномірно розподілених даних, є завжди меншою або рівною до log₂(n). Якщо вихід є незмінним, то ентропія дорівнює нулеві. Коли розподіл імовірності джерела даних є відомим, ентропія виражає ці міркування кількісно. Зміст спостережуваних подій (зміст повідомлень) у визначенні ентропії значення не має. Ентропія враховує лише ймовірність спостереження певної події, тому інформація, яку вона включає, є інформацією про розподіл ймовірності, що лежить в основі, а не про зміст самих подій.

Введення

Основною ідеєю теорії інформації є те, що чим більше хтось знає про предмет, то менше нової інформації про нього вони здатні отримати. Якщо подія є дуже ймовірною, то коли вона трапляється, в цьому немає нічого неочікуваного, і відтак вона привносить мало нової інформації. І навпаки, якщо подія була малоймовірною, то її трапляння є набагато інформативнішим. Таким чином, інформаційний вміст є висхідною функцією оберненої ймовірності події (1/p, де p є ймовірністю події). Тепер, якщо може трапитися більше подій, ентропія вимірює усереднений інформаційний вміст, який ви можете очікувати отримати, якщо дійсно трапляється одна з цих подій. З цього випливає, що викидання грального кубика має більше ентропії, ніж підкидання монети, оскільки кожен з результатів грального кубика має меншу ймовірність, ніж кожен з результатів монети.

Отже, ентропія — це міра непередбачуваності (англ. unpredictability) стану, або, рівнозначно, його усередненого інформаційного вмісту (англ. average information content). Щоби отримати інтуїтивне розуміння цих термінів, розгляньмо приклад політичного опитування. Як правило, такі опитування відбуваються тому, що їхні результати не є заздалегідь відомими. Іншими словами, результати опитування є відносно непередбачуваними, і фактичне здійснення опитування та з'ясовування результатів дає деяку нову інформацію; це просто різні способи сказати, що апріорна ентропія результатів опитування є високою. Тепер розгляньмо випадок, коли таке ж опитування проводиться вдруге незабаром після першого опитування. Оскільки результати першого опитування вже є відомими, підсумки другого опитування можна передбачити добре, і ці результати не повинні містити багато нової інформації; в цьому випадку апріорна ентропія результатів другого опитування є низькою по відношенню до апріорної ентропії першого.

Тепер розгляньмо приклад з підкиданням монети. Якщо ймовірність випадання аверсу така ж, як і ймовірність випадання реверсу, то ентропія підкидання монети є настільки високою, наскільки це можливо. Причиною цього є те, що немає жодного способу передбачити результат підкидання монети заздалегідь — якщо нам треба було би обирати, то найкраще, що ми могли би зробити, це передбачити, що монета випаде аверсом догори, і цей прогноз був би правильним з імовірністю 1/2. Таке підкидання монети має один біт ентропії, оскільки є два можливі результати, які трапляються з однаковою ймовірністю, і з'ясування фактичного результату містить один біт інформації. На противагу до цього, підкидання монети, яка має два аверси й жодного реверсу, має нульову ентропію, оскільки монета завжди випадатиме аверсом, і результат може бути передбачено цілком. Аналогічно, бінарна подія з рівноймовірними результатами має ентропію Шеннона ${\displaystyle \log _{2}2=1}$ біт. Подібно до цього, один трит із рівноймовірними значеннями містить ${\displaystyle \log _{2}3}$ (близько 1.58496) бітів інформації, оскільки він може мати одне з трьох значень.

Англомовний текст, якщо розглядати його як стрічку символів, має досить низький рівень ентропії, тобто, він є доволі передбачуваним. Навіть якщо ми не знаємо точно, що буде далі, ми можемо бути доволі впевненими, що, наприклад, «e» там буде набагато поширенішою за «z», що поєднання «qu» зустрічатиметься набагато частіше за будь-які інші поєднання, які містять «q», і що поєднання «th» буде набагато поширенішим за «z», «q» або «qu». Після перших кількох літер часто можна вгадати решту слова. Англійський текст має між 0.6 та 1.3 біта ентропії на символ повідомлення.^:234

Якщо схема стиснення є вільною від втрат, — тобто, завжди можна відтворити повне первинне повідомлення шляхом розтискання, — то стиснене повідомлення має такий самий обсяг інформації, як і первинне, але переданий меншою кількістю символів. Тобто, воно має більше інформації, або вищу ентропію, на один символ. Це означає, що стиснене повідомлення має меншу надмірність. Грубо кажучи, ^[en] стверджує, що схема стиснення без втрат в середньому не може стиснути повідомлення так, щоби воно мало більше одного біту інформації на біт повідомлення, але що будь-яке значення менше одного біту інформації на біт повідомлення може бути досягнуто шляхом застосування відповідної схеми кодування. Ентропія повідомлення на біт, помножена на довжину цього повідомлення, є мірою того, наскільки багато інформації в цілому містить повідомлення.

Для наочності уявіть, що ми хочемо передати послідовність, до складу якої входять 4 символи, «А», «Б», «В» і «Г». Таким чином, повідомленням для передавання може бути «АБАГГВАБ». Теорія інформації пропонує спосіб обчислення найменшої можливої кількості інформації, яка передасть це. Якщо всі 4 літери є рівноймовірними (25 %), ми не можемо зробити нічого кращого (над двійковим каналом), аніж кодувати кожну літеру 2 бітами (у двійковому вигляді): «А» може бути кодовано як «00», «Б» — як «01», «В» — як «10», а «Г» — як «11». Тепер припустімо, що «А» трапляється з імовірністю 70 %, «Б» — 26 %, а «В» та «Г» — по 2 % кожна. Ми могли би призначити коди змінної довжини, так, що отримання «1» казало би нам дивитися ще один біт, якщо тільки ми не отримали вже перед цим 2 послідовні біти одиниць. В цьому випадку «А» було би кодовано як «0» (один біт), «Б» — як «10», а «В» і «Г» як «110» і «111». Легко побачити, що протягом 70 % часу потрібно надсилати лише один біт, 26 % часу — два біти, і лише протягом 4 % від часу — 3 біти. Тоді в середньому необхідно менше за 2 біти, оскільки ентропія є нижчою (через високу поширеність «А» з наступною за нею «Б» — разом 96 % символів). Обчислення суми зважених за ймовірностями логарифмічних імовірностей вимірює та схоплює цей ефект.

Теорема Шеннона також означає, що жодна схема стиснення без втрат не може скорочувати всі повідомлення. Якщо якісь повідомлення виходять коротшими, хоча б одне повинне вийти довшим в силу принципу Діріхле. В практичному застосуванні це зазвичай не є проблемою, оскільки нас, як правило, цікавить стиснення лише певних типів повідомлень, наприклад, документів англійською мовою на противагу до тексту тарабарщиною, або цифрових фотографій, а не шуму, і не важливо, якщо алгоритм стиснення робить довшими малоймовірні або нецікаві послідовності.

Означення

Назвавши її на честь ^[en], Шеннон означив ентропію Η (грецька літера ета) дискретної випадкової величини ${\textstyle X}$ з можливими значеннями ${\textstyle \left\{x_{1},\ldots ,x_{n}\right\}}$ та функцією маси ймовірності ${\textstyle \mathrm {P} (X)}$ як

${\displaystyle \mathrm {H} (X)=\mathbb {E} [\operatorname {I} (X)]=\mathbb {E} [-\log(\mathrm {P} (X))].}$

Тут ${\displaystyle \mathbb {E} }$ є оператором математичного сподівання (англ. expectation), а I є кількістю інформації X.^:11:19–20 I(X) і сама є випадковою величиною.

Ентропію може бути записано в явному вигляді як

${\displaystyle \mathrm {H} (X)=\sum _{i=1}^{n}{\mathrm {P} (x_{i})\,\mathrm {I} (x_{i})}=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log _{b}\mathrm {P} (x_{i})},}$

де b є ^[en] логарифма, який застосовується. Звичними значеннями b є 2, число Ейлера е, та 10, а відповідними одиницями ентропії є біти для b = 2, нати для b = e, та бани для b = 10.

У випадку P(x_i) = 0 для деякого i значення відповідного доданку 0 log_b(0) приймають рівним 0, що відповідає границі

${\displaystyle \lim _{p\to 0+}p\log(p)=0.}$

Можна також визначити умовну ентропію двох подій X та Y, які набувають значень x_i та y_j відповідно, як

${\displaystyle \mathrm {H} (X|Y)=-\sum _{i,j}p(x_{i},y_{j})\log {\frac {p(x_{i},y_{j})}{p(y_{j})}}}$

де p(x_i, y_j) є ймовірністю того, що X = x_i та Y = y_j. Цю величину слід розуміти як ступінь довільності випадкової величини X при заданій події Y.

Приклад

Ентропія Η(X) (тобто очікувана неочікуваність) підкидання монети, вимірювана в бітах, представлена графічно відносно упередження монети Pr(X = 1), де X = 1 є випадінням аверса.

Тут ентропія складає щонайбільше 1 біт, і для повідомлення результатів підкидання монети (2 можливі значення) потрібно в середньому не більше 1 біту (в точності 1 біт для справедливої монети). Результат справедливого грального кубика (6 можливих значень) потребуватиме в середньому log₂6 бітів.

Детальніші відомості з цієї теми ви можете знайти в статті ^[en] та ^[en].

Розгляньмо підкидання монети з відомими, але не обов'язково справедливими ймовірностями випадання аверсу чи реверсу; це можна змоделювати як ^[en].

Ентропія невідомого результату наступного підкидання монети є найбільшою, якщо монета є справедливою (тобто, якщо як аверси, так і реверси мають однакову ймовірність 1/2). Це є ситуацією максимальної невизначеності, оскільки в ній найскладніше передбачити результат наступного підкидання; результат кожного підкидання монети подає один повний біт інформації. Це є тому, що

${\displaystyle {\begin{aligned}\mathrm {H} (X)&=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log _{b}\mathrm {P} (x_{i})}\\&=-\sum _{i=1}^{2}{{\frac {1}{2}}\log _{2}{\frac {1}{2}}}\\&=-\sum _{i=1}^{2}{{\frac {1}{2}}\cdot (-1)}=1\end{aligned}}}$

Проте, якщо ми знаємо, що монета не є справедливою, а випадає аверсом чи реверсом з імовірностями p та q, де p ≠ q, то тоді невизначеності є менше. Кожного разу, як її підкидають, випадання однієї зі сторін є ймовірнішим, ніж випадання іншої. Зниження невизначеності отримує кількісну оцінку в вигляді меншої ентропії: в середньому кожне підкидання монети подає менше ніж один повний біт інформації. Наприклад, якщо p=0.7, то

$${\displaystyle {\begin{aligned}\mathrm {H} (X)&=-p\log _{2}(p)-q\log _{2}(q)\\&=-0.7\log _{2}(0.7)-0.3\log _{2}(0.3)\\&\approx -0.7\cdot (-0.515)-0.3\cdot (-1.737)\\&=0.8816<1\end{aligned}}}$$

Крайнім випадком є двоаверсова монета, яка ніколи не випадає реверсом, або двореверсова монета, яка ніколи не дає в результаті аверс. Тут немає ніякої невизначеності. Ентропія дорівнює нулеві: кожне підкидання монети не подає жодної нової інформації, оскільки результати кожного підкидання монети завжди визначені.

Ентропію може бути нормалізовано шляхом ділення її на довжину інформації. Це співвідношення називається ^[en], воно є мірою хаотичності інформації.

Обґрунтування

Щоби зрозуміти сенс ∑ p_i log(1/p_i), спершу спробуймо визначити функцію інформації I з точки зору події i з імовірністю p_i. Кількість інформації, отримувана через спостереження події i, випливає з шеннонового розв'язку фундаментальних властивостей інформації:

1. I(p) є монотонно спадною в p — збільшення ймовірності події зменшує інформацію зі спостереження події, і навпаки.
2. I(p) ≥ 0 — інформація є невід'ємною величиною.
3. I(1) = 0 — події, які відбуваються завжди, не несуть інформації.
4. I(p₁ p₂) = I(p₁) + I(p₂) — інформація від незалежних подій є адитивною.

Остання властивість є ключовою. Вона стверджує, що спільна ймовірність незалежних джерел інформації несе стільки ж інформації, скільки й ці дві окремі події по одній. Зокрема, якщо перша подія може видавати один з n ^[en] результатів, а інша має один із m рівноймовірних результатів, то існує mn можливих результатів спільної події. Це означає, що якщо для кодування першого значення потрібно log₂(n) біт, а для кодування другого — log₂(m), то для кодування обох потрібно log₂(mn) = log₂(m) + log₂(n). Шеннон виявив, що правильним вибором функції для кількісної оцінки інформації, яка зберігала би цю адитивність, є логарифмічна, тобто

${\displaystyle \mathrm {I} (p)=\log \left({\tfrac {1}{p}}\right)=-\log(p):}$

нехай ${\textstyle I}$ є інформаційною функцією, що є двічі неперервно диференційовною, тоді

${\displaystyle {\begin{array}{lcl}I(p_{1}p_{2})&=&I(p_{1})+I(p_{2})\\p_{2}I'(p_{1}p_{2})&=&I'(p_{1})\\I'(p_{1}p_{2})+p_{1}p_{2}I''(p_{1}p_{2})&=&0\\I'(u)+uI''(u)&=&0\\(u\mapsto uI'(u))'&=&0\end{array}}}$

Це диференціальне рівняння веде до розв'язку ${\displaystyle I(u)=k\log u}$ для будь-якого ${\displaystyle k\in \mathbb {R} }$. Умова 2 веде до ${\displaystyle k<0}$, а надто, ${\displaystyle k}$ може обиратися з вигляду ${\displaystyle k=-1/\log x}$, де ${\displaystyle x>1}$, що рівнозначне обиранню конкретної . Різні одиниці інформації (біти для двійкового логарифма log₂, нати для натурального логарифма ln, бани для десяткового логарифма log₁₀ і так далі) є лише сталим домноженням одна одної. Наприклад, у випадку підкидання справедливої монети аверс дає log₂(2) = 1 біт інформації, що становить приблизно 0.693 нат, або 0.301 десяткових цифр. В силу адитивності, n підкидань дають n біт інформації, що становить приблизно 0.693n нат, або 0.301n десяткових цифр.

Якщо існує розподіл, в якому подія i може траплятися з імовірністю p_i, з нього було взято N проб, і результат i трапився n_i = N p_i разів, то загальною кількістю інформації, яку ми отримали, є

${\displaystyle \sum _{i}{n_{i}\mathrm {I} (p_{i})}=-\sum _{i}{Np_{i}\log {p_{i}}}}$.

Отже, усередненою кількістю інформації, яку ми отримуємо на подію, є

${\displaystyle -\sum _{i}{p_{i}\log {p_{i}}}.}$

Аспекти

Відношення до термодинамічної ентропії

Детальніші відомості з цієї теми ви можете знайти в статті ^[en].

Натхнення прийняти слово ентропія в теорії інформації виникло від близької подібності між формулою Шеннона, і дуже схожими відомими формулами зі статистичної механіки.

У статистичній термодинаміці найзагальнішою формулою для термодинамічної ентропії S термодинамічної системи є ентропія Гіббса,

${\displaystyle S=-k_{\text{B}}\sum p_{i}\ln p_{i}\,}$

де k_B є сталою Больцмана, а p_i є ймовірністю ^[en]. Ентропію Гіббса було визначено Віллардом Гіббсом 1878 року після ранішої праці Больцмана (1872 року).

Ентропія Гіббса переноситься майже беззмінною до світу квантової фізики, даючи ентропію фон Неймана, введену Джоном фон Нейманом 1927 року,

${\displaystyle S=-k_{\text{B}}\,{\rm {Tr}}(\rho \ln \rho )\,}$

де ρ є матрицею густини квантової механічної системи, а Tr є слідом.

На побутовому практичному рівні зв'язок між інформаційною та термодинамічною ентропією очевидним не є. Фізики та хіміки схильні більше цікавитися змінами ентропії при спонтанному розвитку системи від її первісних умов, у відповідності з другим законом термодинаміки, ніж незмінним розподілом імовірності. І, як вказує малість сталої Больцмана k_B, зміни в S / k_B навіть для невеликих кількостей речовин у хімічних та фізичних процесах являють собою обсяги ентропії, які є надзвичайно великими порівняно з чим завгодно в стисненні даних та обробці сигналів. Крім того, в класичній термодинаміці ентропія визначається в термінах макроскопічних вимірювань, і не робить жодних посилань на будь-який розподіл імовірності, що є головним у визначенні ентропії інформаційної.

Зв'язок між термодинамікою і тим, що зараз відомо як теорія інформації, було вперше зроблено Людвігом Больцманом, і виражено його ^[en]:

${\displaystyle S=k_{\text{B}}\ln(W)}$

де S є термодинамічною ентропією окремого макростану (визначену термодинамічними параметрами, такими як температура, об'єм, енергія тощо), W є числом мікростанів (різних комбінацій частинок у різних енергетичних станах), які можуть дати даний макростан, а k_B є сталою Больцмана. Передбачається, що кожен мікростан є однаково правдоподібним, так що ймовірністю заданого мікростану є p_i = 1/W. При підставленні цих імовірностей до наведеного вище виразу для ентропії Гіббса (або, рівнозначно, ентропії Шеннона, помноженої на k_B) в результаті виходить рівняння Больцмана. В термінах теорії інформації інформаційна ентропія системи є кількістю інформації, якої «бракує» для визначення мікростану при відомому макростані.

На думку ^[en] (1957 року), термодинамічну ентропію, як пояснюється статистичною механікою, слід розглядати як застосування теорії інформації Шеннона: термодинамічна ентропія інтерпретується як така, що є пропорційною до кількості додаткової інформації Шеннона, необхідної для визначення детального мікроскопічного стану системи, яка залишається не повідомленою описом виключно в термінах макроскопічних величин класичної термодинаміки, з коефіцієнтом пропорційності, який є просто сталою Больцмана. Наприклад, додавання теплоти до системи підвищує її термодинамічну ентропію, оскільки це збільшує число можливих мікроскопічних станів системи, які узгоджуються з вимірюваними значеннями його макроскопічних величин, роблячи таким чином будь-який повний опис стану довшим. (Див. статтю ^[en]). Демон Максвелла може (гіпотетично) знижувати термодинамічну ентропію системи з використанням інформації про стан окремих молекул, але, як показали ^[en] (з 1961 року) з колегами, щоби діяти, цей демон мусить сам підвищувати термодинамічну ентропію в цьому процесі, принаймні на кількість інформації Шеннона, яку він пропонує спочатку отримати й зберегти; і, таким чином, загальна термодинамічна ентропія не знижується (що розв'язує парадокс). Принцип Ландауера встановлює нижню межу кількості тепла, яке комп'ютер повинен генерувати для обробки заданого обсягу інформації, хоча сучасні комп'ютери є набагато менш ефективними.

Ентропія як кількість інфромації

Детальніші відомості з цієї теми ви можете знайти в статті ^[en].

Ентропія визначається в контексті ймовірнісної моделі. Незалежні підкидання справедливої монети мають ентропію по 1 біту на підкидання. Джерело, яке завжди породжує довгий рядок «Б», має ентропію 0, оскільки наступним символом завжди буде «Б».

Ентропійна швидкість джерела даних означає усереднене число бітів на символ, потрібне для його кодування. Експерименти Шеннона з передбаченням людьми показують швидкість інформації на символ англійською мовою між 0.6 і 1.3 біта; Алгоритм стиснення PPM може досягати рівня стиснення в 1.5 біти на символ англомовного тексту.

Зверніть увагу на наступні моменти з попереднього прикладу:

1. Кількість ентропії не завжди є цілим числом бітів.
2. Багато бітів даних можуть не нести інформації. Наприклад, структури даних часто зберігають інформацію надмірно, або мають ідентичні розділи, незалежно від інформації в структурі даних.

Шеннонівське визначення ентропії, при застосуванні до джерела інформації, може визначати мінімальну пропускну здатність каналу, необхідну для надійного передавання джерела у вигляді закодованих двійкових цифр (див. застереження нижче курсивом). Цю формулу може бути виведено шляхом обчислення математичного сподівання кількості інформації, яка міститься в одній цифрі з джерела інформації. Див. також теорему Шеннона — Гартлі.

Ентропія Шеннона вимірює інформацію, яка міститься в повідомленні, на противагу до тієї частини повідомлення, яка є визначеною (або передбачуваною). Приклади останнього включають надмірність у структурі мови та статистичні властивості, які стосуються частот трапляння пар, трійок тощо літер або слів. Див. ланцюги Маркова.

Ентропія як міра різноманітності

Докладніше: Міра різноманітності

Ентропія є одним з декількох способів вимірювання різноманітності. Зокрема, ентропія Шеннона є логарифмом ¹D, індексу істинної різноманітності з параметром, який дорівнює 1.

Стиснення даних

Докладніше: Стиснення даних

Ентропія ефективно обмежує продуктивність найсильнішого можливого стиснення без втрат, яке може бути реалізовано теоретично з допомогою ^[en], або практично із застосуванням кодування Хаффмана, Лемпеля — Зіва, або арифметичного кодування. Див. також колмогоровську складність. На практиці для захисту від помилок алгоритми стиснення навмисно включають деяку розумну надмірність у вигляді контрольних сум.

Світовий технологічний потенціал для зберігання та передавання інформації

Дослідження 2011 року в журналі «Science» оцінює світовий технологічний потенціал для зберігання та передавання оптимально стисненої інформації, нормалізований за найефективнішими алгоритмами стиснення, доступними в 2007 році, оцінюючи таким чином ентропію технологічно доступних джерел.^:60–65

Всі числа — в ентропійно стиснених ексабайтах

Тип інформації	1986	2007
Зберігання	2.6	295
Широкомовлення	432	1900
Телекомунікації	0.281	65

Автори оцінюють технологічний потенціал людства у зберіганні інформації (повністю ентропійно стисненої) 1986 року, і знову 2007 року. Вони ділять інформацію на три категорії — зберігання інформації на носії, отримування інформації через мережі однобічного широкомовлення, та обмін інформацією через двобічні телекомунікаційні мережі.

Обмеження ентропії як кількості інформації

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

• власна інформація окремого повідомлення або символу, взятого із заданого розподілу ймовірності,
• ентропія заданого розподілу ймовірності повідомлень або символів, та
• ентропійна швидкість стохастичного процесу.

(Для конкретної послідовності повідомлень або символів, породженої заданим стохастичним процесом, також може бути визначено «швидкість власної інформації»: у випадку стаціонарного процесу вона завжди дорівнюватиме швидкості ентропії.) Для порівняння різних джерел інформації, або встановлення зв'язку між ними, використовуються й інші Кількості інформації.

Важливо не плутати наведені вище поняття. Яке з них мається на увазі, часто може бути зрозумілим лише з контексту. Наприклад, коли хтось говорить, що «ентропія» англійської мови становить близько 1 біта на символ, вони насправді моделюють англійську мову як стохастичний процес, і говорять про швидкість її ентропії. Шеннон і сам використовував цей термін таким чином.

Проте, якщо ми використовуємо дуже великі блоки, то оцінка посимвольної ентропійної швидкості може стати штучно заниженою. Це відбувається тому, що насправді розподіл ймовірності послідовності не є пізнаваним точно; це лише оцінка. Наприклад, припустімо, що розглядаються тексти всіх будь-коли опублікованих книг як послідовність, у якій кожен символ є текстом цілої книги. Якщо існує N опублікованих книг, і кожну книгу опубліковано лише одного разу, то оцінкою ймовірності кожної книги є 1/N, а ентропією (в бітах) є −log₂(1/N) = log₂(N). Як практичний код, це відповідає призначенню кожній книзі унікального ідентифікатора і використання його замість тексту книги будь-коли, коли потрібно послатися на цю книгу. Це надзвичайно корисно для розмов про книги, але не дуже корисно для характеризування кількості інформації окремих книг або мови в цілому: неможливо відтворити книгу з її ідентифікатора, не знаючи розподілу ймовірності, тобто повного тексту всіх книг. Ключова ідея полягає в тому, що повинна братися до уваги складність імовірнісної моделі. Колмогоровська складність являє собою теоретичне узагальнення цієї ідеї, яке дозволяє розглядати кількість інформації послідовності незалежно від конкретної ймовірнісної моделі; воно розглядає найкоротшу програму для універсального комп'ютера, яка виводить цю послідовність. Такою програмою є код, який досягає ентропійної швидкості послідовності для заданої моделі, плюс кодовий словник (тобто, ймовірнісна модель), але вона не може бути найкоротшою.

Наприклад, послідовністю Фібоначчі є 1, 1, 2, 3, 5, 8, 13, …. При розгляді цієї послідовності як повідомлення, а кожного числа як символу, існує майже стільки ж символів, скільки є символів у повідомленні, даючи ентропію близько log₂(n). Таким чином, перші 128 символів послідовності Фібоначчі мають ентропію приблизно 7 біт/символ. Проте цю послідовність може бути виражено за допомогою формули [F(n) = F(n−1) + F(n−2) для n = 3, 4, 5, …, F(1) =1, F(2) = 1], і ця формула має значно нижчу ентропію, і застосовується до послідовності Фібоначчі будь-якої довжини.

Обмеження ентропії в криптографії

В криптоаналізі ентропію часто грубо використовують як міру непередбачуваності криптографічного ключа, хоча її справжня невизначеність є незмірною. Наприклад, 128-бітовий ключ, який породжено рівномірно випадково, має 128 біт ентропії. Він також вимагає (усереднено) ${\displaystyle 2^{128-1}}$ спроб для зламу грубою силою. Проте, ентропія не відображає число потрібних спроб, якщо можливі ключі вибирають не рівномірно. Натомість, для вимірювання зусиль, необхідних для атаки грубою силою, можна використовувати міру, що називають здогадом (англ. guesswork).

Через нерівномірність розподілів, що застосовують в криптографії, можуть виникати й інші проблеми. Наприклад, розгляньмо 1 000 000-цифровий двійковий шифр Вернама із застосуванням виключного «або». Якщо цей шифр має 1 000 000 біт ентропії, це чудово. Якщо цей шифр має 999 999 біт ентропії, які розподілено рівномірно (коли кожен окремий біт шифру має 0.999999 біт ентропії), то він може пропонувати добру безпеку. Але якщо цей шифр має 999 999 біт ентропії, так, що перший біт є незмінним, а решта 999 999 бітів вибирають випадково, то перший біт шифрованого тексту не буде шифровано взагалі.

Дані як марковський процес

Звичний спосіб визначення ентропії для тексту ґрунтується на марковській моделі тексту. Для джерела нульового порядку (кожен символ обирається незалежно від останніх символів) двійковою ентропією є

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum p_{i}\log _{2}p_{i},}$

де p_i є ймовірністю i. Для ^[en] першого порядку (такого, в якому ймовірність вибору символу залежить лише від безпосередньо попереднього символу) ентропійною швидкістю є

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}\ p_{i}(j)\log _{2}p_{i}(j),}$ ^[]

де i є станом (деякими попередніми символами), а ${\displaystyle p_{i}(j)}$ є ймовірністю j за заданого попереднього символу i.

Для марковського джерела другого порядку ентропійною швидкістю є

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\sum _{k}p_{i,j}(k)\ \log _{2}\ p_{i,j}(k).}$

b-арна ентропія

В загальному випадку b-арна ентропія джерела ${\displaystyle {\mathcal {S}}}$ = (S, P) з первинною абеткою S = {a₁, …, a_n} і дискретним розподілом ймовірності P = {p₁, …, p_n}, де p_i є імовірністю a_i (скажімо, p_i = p(a_i)), визначається як

${\displaystyle \mathrm {H} _{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i},}$

Зауваження: b у «b-арній ентропії» є числом різних символів ідеальної абетки, яка використовується як стандартне мірило для вимірювання первинних абеток. В теорії інформації для абетки для кодування інформації є необхідними і достатніми два символи. Тому стандартним є брати b = 2 («двійкова ентропія»). Таким чином, ентропія первинної абетки, з її заданим емпіричним розподілом імовірності, — це число, яке дорівнює числу (можливо дробовому) символів «ідеальної абетки», з оптимальним розподілом імовірності, необхідних для кодування кожного символу первинної абетки. Також зверніть увагу, що «оптимальний розподіл імовірності» тут означає рівномірний розподіл: первинна абетка з n символів має найвищу можливу ентропію (для абетки з n символів), коли розподіл імовірності абетки є рівномірним. Цією оптимальною ентропією виявляється log_b(n).

Ефективність

Первинна абетка з нерівномірним розподілом матиме меншу ентропію, ніж якби ці символи мали рівномірний розподіл (тобто, були «оптимальною абеткою»). Цю дефективність ентропії може бути виражено відношенням, яке називається ефективністю:^[]

${\displaystyle \eta (X)=-\sum _{i=1}^{n}{\frac {p(x_{i})\log _{b}(p(x_{i}))}{\log _{b}(n)}}=\log _{n}(\prod _{i=1}^{n}p(x_{i})^{-p(x_{i})})}$^[]

Ефективність є корисною для кількісної оцінки ефективності використання каналу зв'язку. Це формулювання також називають нормалізованою ентропією, оскільки ентропія ділиться на максимальну ентропію ${\displaystyle {\log _{b}(n)}}$. Крім того, ефективності байдужий вибір (додатної) бази b, про що свідчить нечутливість до неї в кінцевому логарифмі.

Характеризування

Ентропія Шеннона ^[en] невеликим числом критеріїв, перерахованих нижче. Будь-яке визначення ентропії, яке задовольняє ці припущення, має вигляд

${\displaystyle -K\sum _{i=1}^{n}p_{i}\log(p_{i})}$

де K є сталою, яка відповідає виборові одиниць вимірювання.

Далі p_i = Pr(X = x_i), а Η_n(p₁, …, p_n) = Η(X).

Неперервність

Ця міра повинна бути неперервною, так що зміна значень ймовірностей на дуже незначну величину повинна змінювати ентропію лише на незначну величину.

Симетричність

При перевпорядкуванні виходів x_i ця міра повинна залишатися незмінною.

${\displaystyle \mathrm {H} _{n}\left(p_{1},p_{2},\ldots \right)=\mathrm {H} _{n}\left(p_{2},p_{1},\ldots \right)}$ тощо

Максимум

Ця міра повинна бути максимальною тоді, коли всі виходи є однаково правдоподібними (невизначеність є найвищою, коли всі можливі події є рівноймовірними).

${\displaystyle \mathrm {H} _{n}(p_{1},\ldots ,p_{n})\leq \mathrm {H} _{n}\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)=\log _{b}(n).}$

Для рівноймовірних подій ентропія повинна зростати зі збільшенням числа виходів.

${\displaystyle \mathrm {H} _{n}{\bigg (}\underbrace {{\frac {1}{n}},\ldots ,{\frac {1}{n}}} _{n}{\bigg )}=\log _{b}(n)<\log _{b}(n+1)=\mathrm {H} _{n+1}{\bigg (}\underbrace {{\frac {1}{n+1}},\ldots ,{\frac {1}{n+1}}} _{n+1}{\bigg )}.}$

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

Адитивність

Величина ентропії повинна не залежати від того, який поділ процесу на частини розглядається.

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

При заданому ансамблі n рівномірно розподілених елементів, які поділяються на k блоків (підсистем) з b₁, ..., b_k елементами в кожному, ентропія всього ансамблю повинна дорівнювати сумі ентропії системи блоків і окремих ентропій блоків, кожна з яких є зваженою на ймовірність знаходження в цьому відповідному блоці.

Для додатних цілих чисел b_i, де b₁ + … + b_k = n,

${\displaystyle \mathrm {H} _{n}\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)=\mathrm {H} _{k}\left({\frac {b_{1}}{n}},\ldots ,{\frac {b_{k}}{n}}\right)=\sum _{i=1}^{k}{\frac {b_{i}}{n}}\,\mathrm {H} _{b_{i}}\left({\frac {1}{b_{i}}},\ldots ,{\frac {1}{b_{i}}}\right).}$

При обранні k = n, b₁ = … = b_n = 1 це означає, що ентропія незмінного виходу дорівнює нулеві: Η₁(1) = 0. Це означає, що ефективність первинної абетки з n символами може бути визначено просто як таку, що дорівнює її n-арній ентропії. Див. також надмірність інформації.

Додаткові властивості

Ентропія Шеннона задовольняє наступні властивості, для деяких з яких корисно інтерпретувати ентропію як кількість пізнаної інформації (або усуненої невизначеності) при розкритті значення випадкової величини X:

• Додавання або усування подій з нульовою ймовірністю не впливає на ентропію:

${\displaystyle \mathrm {H} _{n+1}(p_{1},\ldots ,p_{n},0)=\mathrm {H} _{n}(p_{1},\ldots ,p_{n})}$.

• Ентропія дискретної випадкової змінної є невід'ємним числом:

${\displaystyle \mathrm {H} (X)\geq 0}$.^:15

• За допомогою нерівності Єнсена може бути підтверджено, що

${\displaystyle \mathrm {H} (X)=\operatorname {E} \left[\log _{b}\left({\frac {1}{p(X)}}\right)\right]\leq \log _{b}\left(\operatorname {E} \left[{\frac {1}{p(X)}}\right]\right)=\log _{b}(n)}$.^:29

Ця максимальна ентропія log_b(n) ефективно досягається первинною абеткою, яка має рівномірний розподіл ймовірності: невизначеність є максимальною, коли всі можливі події є однаково ймовірними.

• Ентропія, або обсяг інформації, розкритої шляхом визначення (X,Y) (тобто визначення X та Y одночасно) дорівнює інформації, розкритої шляхом проведення двох послідовних експериментів: спершу виявлення значення Y, а потім виявлення значення X, за умови, що ви знаєте значення Y. Це може бути записано як

${\displaystyle \mathrm {H} (X,Y)=\mathrm {H} (X|Y)+\mathrm {H} (Y)=\mathrm {H} (Y|X)+\mathrm {H} (X).}$

• Якщо ${\displaystyle Y=f(X)}$, де ${\displaystyle f}$ є функцією, то ${\displaystyle H(f(X)|X)=0}$. Застосування попередньої формули до ${\displaystyle H(X,f(X))}$ дає

${\displaystyle \mathrm {H} (X)+\mathrm {H} (f(X)|X)=\mathrm {H} (f(X))+\mathrm {H} (X|f(X)),}$

отже, ${\displaystyle H(f(X)|X)\leq H(X)}$, таким чином, ентропія величини може тільки зменшуватися, коли остання проходить через функцію.

• Якщо X та Y в є двома незалежними випадковими змінними, то знання значення Y не впливає на наше знання про значення X (оскільки ці двоє не впливають одне на одне в силу незалежності):

${\displaystyle \mathrm {H} (X|Y)=\mathrm {H} (X).}$

• Ентропія двох одночасних подій є не більшою за суму ентропій кожної з окремих подій, і дорівнює їй, якщо ці дві події є незалежними. Точніше, якщо X та Y є двома випадковими величинами на одному й тому ж імовірнісному просторі, а (X, Y) позначає їхній декартів добуток, то

${\displaystyle \mathrm {H} (X,Y)\leq \mathrm {H} (X)+\mathrm {H} (Y).}$

• Ентропія ${\displaystyle \mathrm {H} (p)}$ є угнутою за функцією маси ймовірності ${\displaystyle p}$, тобто,

${\displaystyle \mathrm {H} (\lambda p_{1}+(1-\lambda )p_{2})\geq \lambda \mathrm {H} (p_{1})+(1-\lambda )\mathrm {H} (p_{2})}$

для всіх функцій маси ймовірності ${\displaystyle p_{1},p_{2}}$ та ${\displaystyle 0\leq \lambda \leq 1}$.^:32

Розширення дискретної ентропії до неперервного випадку

Диференціальна ентропія

Докладніше: Диференціальна ентропія

Ентропію Шеннона обмежено випадковими величинами, які набувають дискретних значень. Відповідна формула для неперервної випадкової величини з функцією густини ймовірності f(x) зі скінченною або нескінченною областю визначення ${\displaystyle \mathbb {X} }$ на дійсній осі визначається аналогічно, з допомогою наведеного вище вираження ентропії як математичного сподівання:

${\displaystyle h[f]=\operatorname {E} [-\ln(f(x))]=-\int _{\mathbb {X} }f(x)\ln(f(x))\,dx.}$

Цю формулу зазвичай називають непере́рвною ентропі́єю (англ. continuous entropy), або диференціальною ентропією. Попередником неперервної ентропії h[f] є вираз функціоналу Η в ^[en].

Хоча аналогія між обома функціями й наводить на роздуми, мусить бути поставлено наступне питання: чи є диференціальна ентропія обґрунтованим розширенням дискретної ентропії Шеннона? Диференціальній ентропії бракує ряду властивостей, якими володіє дискретна ентропія Шеннона, — вона навіть може бути від'ємною, — і відтак було запропоновано поправки, зокрема, ^[en].

Щоби відповісти на це питання, ми мусимо встановити зв'язок між цими двома функціями:

Ми хочемо отримати загальну скінченну міру при прямуванні розміру засіків до нуля. В дискретному випадку розмір засіків є (неявною) шириною кожного з n (скінченних або нескінченних) засіків, чиї ймовірності позначаються через p_n. Оскільки ми робимо узагальнення до неперервної області визначення, ми мусимо зробити цю ширину явною.

Щоби зробити це, почнімо з неперервної функції f, дискретизованої засіками розміру ${\displaystyle \Delta }$. Згідно теореми про середнє значення, в кожному засіку існує таке значення x_i, що

${\displaystyle f(x_{i})\Delta =\int _{i\Delta }^{(i+1)\Delta }f(x)\,dx}$

і відтак інтеграл функції f може бути наближено (в рімановому сенсі) за допомогою

${\displaystyle \int _{-\infty }^{\infty }f(x)\,dx=\lim _{\Delta \to 0}\sum _{i=-\infty }^{\infty }f(x_{i})\Delta }$

де ця границя і «розмір засіку прямує до нуля» є рівноцінними.

Позначмо

${\displaystyle \mathrm {H} ^{\Delta }:=-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log \left(f(x_{i})\Delta \right)}$

і, розкриваючи цього логарифма, ми маємо

${\displaystyle \mathrm {H} ^{\Delta }=-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(f(x_{i}))-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(\Delta ).}$

При Δ → 0 ми маємо

${\displaystyle {\begin{aligned}\sum _{i=-\infty }^{\infty }f(x_{i})\Delta &\to \int _{-\infty }^{\infty }f(x)\,dx=1\\\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(f(x_{i}))&\to \int _{-\infty }^{\infty }f(x)\log f(x)\,dx.\end{aligned}}}$

Але зауважте, що log(Δ) → −∞ при Δ → 0, отже, нам потрібне особливе визначення диференціалу або неперервної ентропії:

${\displaystyle h[f]=\lim _{\Delta \to 0}\left(\mathrm {H} ^{\Delta }+\log \Delta \right)=-\int _{-\infty }^{\infty }f(x)\log f(x)\,dx,}$

що, як було сказано раніше, називають диференціа́льною ентропі́єю (англ. differential entropy). Це означає, що диференціальна ентропія не є границею ентропії Шеннона при n → ∞. Вона радше відрізняється від границі ентропії Шеннона нескінченним зсувом (див. також статтю про ^[en]).

Взяття границі щільності дискретних точок

Детальніші відомості з цієї теми ви можете знайти в статті ^[en].

В результаті виходить, що, на відміну від ентропії Шеннона, диференціальна ентропія не є в цілому доброю мірою невизначеності або інформації. Наприклад, диференціальна ентропія може бути від'ємною; крім того, вона не є інваріантною відносно неперервних перетворень координат. Цю проблему може бути проілюстровано зміною одиниць вимірювання, коли x є розмірною величиною. f(x) тоді матиме одиниці 1/x. Аргумент логарифма мусить бути безрозмірним, інакше він є неправильним, бо така диференціальна ентропія, як наведено вище, буде неправильною. Якщо ${\displaystyle \Delta }$ є деяким «стандартним» значенням x (тобто, «розміром засіку»), і відтак має такі ж одиниці вимірювання, то видозмінену диференціальну ентропію може бути записано в належному вигляді як

${\displaystyle H=\int _{-\infty }^{\infty }f(x)\log(f(x)\,\Delta )\,dx}$

і результат буде однаковим при будь-якому виборі одиниць вимірювання для x. Насправді границя дискретної ентропії при N → 0 включала би також і член log(N), який в загальному випадку був би нескінченним. Це є очікуваним, неперервні величини при дискретизації зазвичай матимуть нескінченну ентропію. ^[en] в дійсності є мірою того, наскільки розподіл є простішим для опису за розподіл, який є рівномірним над своєю схемою квантування.

Відносна ентропія

Детальніші відомості з цієї теми ви можете знайти в статті ^[en].

Іншою корисною мірою ентропії, яка однаково добре працює в дискретному та неперервному випадках, є відно́сна ентропі́я (англ. relative entropy) розподілу. Вона визначається як відстань Кульбака — Лейблера від розподілу до еталонної міри m наступним чином. Припустімо, що розподіл імовірності p є абсолютно неперервним відносно міри m, тобто має вигляд p(dx) = f(x)m(dx) для деякої невід'ємної m-інтегрованої функції f з m-інтегралом 1, тоді відносну ентропію може бути визначено як

${\displaystyle D_{\mathrm {KL} }(p\|m)=\int \log(f(x))p(dx)=\int f(x)\log(f(x))m(dx).}$

В такому вигляді відносна ентропія узагальнює (з точністю до зміни знака) як дискретну ентропію, коли міра m є лічильною мірою, так і диференціальну ентропію, коли міра m є мірою Лебега. Якщо міра m і сама є розподілом ймовірності, то відносна ентропія є невід'ємною, і нульовою, якщо p = m як міри. Вона визначається для будь-якого простору мір, отже, не залежить від координат, і є інваріантною відносно перепараметризації координат, якщо перетворення міри m береться до уваги правильно. Відносна ентропія, і неявно ентропія та диференціальна ентропія, залежать від «базової» міри m.

Застосування в комбінаториці

Ентропія стала корисною величиною в комбінаториці.

Нерівність Люміса — Уїтні

Простим прикладом цього є альтернативне доведення ^[en]: для будь-якої підмножини A ⊆ Z^d ми маємо

${\displaystyle |A|^{d-1}\leq \prod _{i=1}^{d}|P_{i}(A)|}$

де P_i є ортогональною проєкцією в i-й координаті:

${\displaystyle P_{i}(A)=\{(x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{d}):(x_{1},\ldots ,x_{d})\in A\}.}$

Це доведеня випливає як простий наслідок ^[en]: якщо X₁, …, X_d є випадковими величинами, а S₁, …, S_n є підмножинами {1, …, d}, такими, що кожне ціле число між 1 і d лежить точно в r з цих підмножин, то

${\displaystyle \mathrm {H} [(X_{1},\ldots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}\mathrm {H} [(X_{j})_{j\in S_{i}}]}$

де ${\displaystyle (X_{j})_{j\in S_{i}}}$ є декартовим добутком випадкових величин X_j з індексами j в S_i (тому розмірність цього вектора дорівнює розмірові S_i).

Ми зробимо нарис, як з цього випливає Люміс — Уїтні: справді, нехай X є рівномірно розподіленою випадковою величиною зі значеннями в A, і такою, що кожна точка з A трапляється з однаковою ймовірністю. Тоді (згідно додаткових властивостей ентропії, згадуваних вище) Η(X) = log|A|, де |A| позначає потужність A. Нехай S_i = {1, 2, …, i−1, i+1, …, d}. Діапазон ${\displaystyle (X_{j})_{j\in S_{i}}}$ міститься в P_i(A) і, отже, ${\displaystyle \mathrm {H} [(X_{j})_{j\in S_{i}}]\leq \log |P_{i}(A)|}$. Тепер застосуймо це, щоби обмежити праву частину нерівності Ширера, і піднести до степеня протилежні частини нерівності, яку ви отримали в результаті.

Наближення до біноміального коефіцієнту

Для цілих чисел 0 < k < n покладімо q = k/n. Тоді

${\displaystyle {\frac {2^{n\mathrm {H} (q)}}{n+1}}\leq {\tbinom {n}{k}}\leq 2^{n\mathrm {H} (q)},}$

де

${\displaystyle \mathrm {H} (q)=-q\log _{2}(q)-(1-q)\log _{2}(1-q).}$^:43

Нижче наведено схематичне доведення. Зауважте, що ${\displaystyle {\tbinom {n}{k}}q^{qn}(1-q)^{n-nq}}$ є одним із членів суми

${\displaystyle \sum _{i=0}^{n}{\tbinom {n}{i}}q^{i}(1-q)^{n-i}=(q+(1-q))^{n}=1.}$

Відповідно, з нерівності ${\displaystyle {\tbinom {n}{k}}q^{k}(1-q)^{n-k}\leq 1}$ після логарифмування отримується верхня межа.

Для отримання нижньої межі спочатку шляхом певних перетворень показується, що доданок ${\displaystyle {\tbinom {n}{k}}q^{qn}(1-q)^{n-nq}}$ є найбільшим членом у наведеній сумі. Але тоді

${\displaystyle {\binom {n}{k}}q^{qn}(1-q)^{n-nq}\geq {\frac {1}{n+1}}}$

оскільки біном містить n + 1 членів. Звідси випливає нижня межа.

Наведені результати інтерпретуються, наприклад, таким чином: число двійкових стрічок довжини n, які містять рівно k одиниць, можна оцінити як ${\displaystyle 2^{n\mathrm {H} (k/n)}}$.

Див. також

• Взаємна інформація
• Випадковість
• Відстань Геммінга
• Відстань Левенштейна
• ^[en]
• Ентропійна швидкість
• Ентропійне кодування — схема кодування, яка призначає коди символам таким чином, щоби довжини кодів відповідали ймовірностям символів
• ^[en]
• ^[en]
• ^[en] в динамічних системах
• Ентропія Реньї — узагальнення ентропії Шеннона; вона є однією з сімейства функціоналів для кількісної оцінки різноманіття, невизначеності або випадковості системи.
• Ентропія Цалліса
• Індекс різноманітності — альтернативні підходи до кількісної оцінки різноманітності в розподілі ймовірності
• Індекс Тейла
• Індекс Шеннона
• Інформація за Фішером
• ^[en]
• ^[en]
• ^[en] — міра розрізнюваності між двома квантовими станами
• Множник Лагранжа
• Негентропія
• ^[en]
• Типоглікемія
• ^[en]
• Перехресна ентропія — є мірою усередненого числа бітів, необхідних для ідентифікації події з набору можливостей між двома розподілами ймовірності
• Перплексивність
• Спільна ентропія — це міра того, як багато ентропії міститься в спільній системі з двох випадкових величин.
• Умовна ентропія
• ^[en] — інші міри статистичної дисперсії для номінальних розподілів

Примітки

1. Pathria, R. K.; Beale, Paul (2011). . Academic Press. с. 51. ISBN . Архів оригіналу за 17 червня 2020. Процитовано 13 грудня 2018. (англ.)
2. Shannon, Claude E. (July–October 1948). A Mathematical Theory of Communication. ^[en]. 27 (3): 379—423. doi:10.1002/j.1538-7305.1948.tb01338.x. (, заархівовано звідси [ 20 червня 2014 у Wayback Machine.]) (англ.)
3. Shannon, Claude E. (1948). (PDF). ^[en]. 27. Архів оригіналу (PDF) за 15 лютого 2019. Процитовано 13 грудня 2018., July and October (англ.)
4. Schneier, B: Applied Cryptography, Second edition, John Wiley and Sons. (англ.)
5. Borda, Monica (2011). . Springer. ISBN . Архів оригіналу за 15 лютого 2017. Процитовано 6 червня 2017. (англ.)
6. Han, Te Sun & Kobayashi, Kingo (2002). . American Mathematical Society. ISBN . Архів оригіналу за 15 лютого 2017. Процитовано 6 червня 2017. (англ.)
7. Schneider, T.D, Information theory primer with an appendix on logarithms^{[недоступне посилання]}, National Cancer Institute, 14 April 2007. (англ.)
8. Carter, Tom (March 2014). (PDF). Santa Fe. Архів оригіналу (PDF) за 4 червня 2016. Процитовано 4 серпня 2017. (англ.)
9. Compare: Boltzmann, Ludwig (1896, 1898). Vorlesungen über Gastheorie : 2 Volumes – Leipzig 1895/98 UB: O 5262-6. English version: Lectures on gas theory. Translated by Stephen G. Brush (1964) Berkeley: University of California Press; (1995) New York: Dover (англ.)
10. Mark Nelson (24 August 2006). . Архів оригіналу за 1 березня 2018. Процитовано 27 листопада 2008. (англ.)
11. "The World's Technological Capacity to Store, Communicate, and Compute Information" [ 27 липня 2013 у Wayback Machine.], Martin Hilbert and Priscila López (2011), Science, 332(6025); free access to the article through here: martinhilbert.net/WorldInfoCapacity.html (англ.)
12. Massey, James (1994). (PDF). Proc. IEEE International Symposium on Information Theory. Архів оригіналу (PDF) за 1 січня 2014. Процитовано 31 грудня 2013. (англ.)
13. Malone, David; Sullivan, Wayne (2005). (PDF). Proceedings of the Information Technology & Telecommunications Conference. Архів оригіналу (PDF) за 15 квітня 2016. Процитовано 31 грудня 2013. (англ.)
14. Pliam, John (1999). Guesswork and variation distance as measures of cipher security. International Workshop on Selected Areas in Cryptography. doi:10.1007/3-540-46513-8_5. (англ.)
15. Thomas M. Cover; Joy A. Thomas (18 липня 2006). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN . (англ.)
16. Aoki, New Approaches to Macroeconomic Modeling. (англ.)
17. Probability and Computing, M. Mitzenmacher and E. Upfal, Cambridge University Press (англ.)

Література

Підручники з теорії інформації

• Теорія інформації і кодування: навч. посіб. / А. Я. Кулик, С. Г. Кривогубченко; Вінниц. нац. техн. ун-т. — Вінниця, 2008. — 145 c.
• Теорія інформації: навч. посіб. / Н. О. Тулякова; Сум. держ. ун-т. — Суми, 2008. — 212 c.
• Теорія інформації: навч. посіб. / В. В. Дядичев, Б. М. Локотош, А. В. Колєсніков; Східноукр. нац. ун-т ім. В. Даля. — Луганськ, 2009. — 249 c.
• Теорія інформації та кодування / В. С. Василенко, О. Я. Матов; НАН України, Ін-т пробл. реєстрації інформації. — Київ : ІПРІ НАН України, 2014. — 439 c.
• Теорія інформації та кодування: підручник / В. І. Барсов, В. А. Краснобаєв, З. В. Барсова, О. І. Тиртишніков, І. В. Авдєєв; ред.: В. І. Барсов; МОНМС України, Укр. інж.-пед. акад., Полтав. нац. техн. ун-т ім. Ю. Кондратюка. — Полтава, 2011. — 321 c.
• Теорія інформації та кодування: Підруч. для студ. вищ. техн. навч. закл. / Ю. П. Жураковський, В. П. Полторак. — К. : «Вища шк.», 2001. — 255 c.
• Arndt, C. (2004), Information Measures: Information and its Description in Science and Engineering, Springer, (англ.)
• Cover, T. M., Thomas, J. A. (2006), Elements of information theory, 2nd Edition. Wiley-Interscience. . (англ.)
• Gray, R. M. (2011), Entropy and Information Theory, Springer. (англ.)
• ^[en]. Information Theory, Inference, and Learning Algorithms [ 17 лютого 2016 у Wayback Machine.] Cambridge: Cambridge University Press, 2003. (англ.)
• Martin, Nathaniel F.G. & England, James W. (2011). . Cambridge University Press. ISBN . Архів оригіналу за 19 березня 2015. Процитовано 6 червня 2017. (англ.)
  • Мартин Н., Ингленд Дж. Математическая теория энтропии. — М. : Мир, 1988. — 350 с. (рос.)
• Shannon, C.E., Weaver, W. (1949) The Mathematical Theory of Communication, Univ of Illinois Press. (англ.)
• Stone, J. V. (2014), Chapter 1 of Information Theory: A Tutorial Introduction [ 3 червня 2016 у Wayback Machine.], University of Sheffield, England. . (англ.)
• Хэмминг Р. В. (1983). Теория информации и теория кодирования. Москва: Радио и Связь. (рос.)

Посилання

• Hazewinkel, Michiel, ред. (2001), Entropy, Математична енциклопедія, , ISBN  (англ.)
• Введення в ентропію та інформацію [ 17 травня 2016 у Wayback Machine.] на ^[en] (англ.)
• Entropy [ 31 травня 2016 у Wayback Machine.], міждисциплінарний журнал про всі аспекти поняття ентропії. Відкритий доступ. (англ.)
• (англ.)
• Аплет Java, який представляє експеримент Шеннона з обчислення ентропії англійської мови [ 13 травня 2016 у Wayback Machine.]
• (англ.)
• An Intuitive Guide to the Concept of Entropy Arising in Various Sectors of Science — вікікнига про інтерпретацію поняття ентропії. (англ.)
• Network Event Detection With Entropy Measures [ 13 квітня 2016 у Wayback Machine.], Dr. Raimund Eimann, University of Auckland, PDF; 5993 kB — докторська праця, яка демонструє, як вимірювання ентропії можуть застосовуватися для виявлення мережевих аномалій. (англ.)
• Entropy [ 4 червня 2016 у Wayback Machine.] — репозитарій ^[en] реалізацій ентропії Шеннона різними мовами програмування.
• "Information Theory for Intelligent People" [ 13 червня 2020 у Wayback Machine.]. Коротке введення до аксіом теорії інформації, ентропії, взаємної інформації, відстані Кульбака — Лейблера та відстані Єнсена — Шеннона. (англ.)
• Інтерактивний інструмент для обчислення ентропії (простого тексту ASCII) [ 15 квітня 2022 у Wayback Machine.]
• Інтерактивний інструмент для обчислення ентропії (двійкового входу)