Энтропия случайного источника — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 12 промежуточных версий 3 участников)
Строка 10: Строка 10:
 
'''Энтропия должна удовлетворять следующим требованиям:'''
 
'''Энтропия должна удовлетворять следующим требованиям:'''
  
* Функция <tex>H(p_1, p_2, ..., p_n)</tex> определена и непрерывна для всех таких наборов <tex>p_i\in[0,\;1]</tex>, что <tex> \sum\limits_{i = 1}^{n} p_i  = 1</tex>  
+
* Функция <tex>H(p_1, p_2, \dots, p_n)</tex> определена и непрерывна для всех таких наборов <tex>p_i\in[0,\;1]</tex>, что <tex> \sum\limits_{i = 1}^{n} p_i  = 1</tex>  
  
* <tex dpi ="130">H(\underbrace{\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}}_\text{n}) < H(\underbrace{\frac{1}{n+1}, \frac{1}{n+1}, ..., \frac{1}{n+1}}_\text{n+1})</tex>
+
* <tex dpi ="130">H(\underbrace{\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}}_\text{n}) < H(\underbrace{\dfrac{1}{n+1}, \dfrac{1}{n+1}, \dots, \dfrac{1}{n+1}}_\text{n+1})</tex>
  
* <tex dpi ="130"> H(p_{1}q_{11}, p_{1}q_{12}, ..., p_{n}q_{nk_n}) = H(p_1, p_2, ..., p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, ..., q_{ik_i})</tex>
+
* <tex dpi ="130"> H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, \dots, p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, \dots, q_{ik_i})</tex>
 
<tex>\rhd</tex>
 
<tex>\rhd</tex>
  
Рассмотрим схему <tex>\mathcal{P}_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\{p_1, p_2, ..., p_m\}</tex> и схему <tex>\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, ..., q_k\}</tex>.
+
Рассмотрим схему <tex>\mathcal{P}_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\{p_1, p_2, \dots, p_m\}</tex> и схему <tex>\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, \dots, q_k\}</tex>.
  
 
Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом:
 
Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом:
Строка 23: Строка 23:
 
Выбирается случайным образом один из исходов схемы <tex>\mathcal{P}_m</tex>, и если произошел <tex>m</tex>-й исход, выбирается случайно один из исходов схемы <tex>\mathcal{R}_k</tex>, а остальные <tex>m - 1</tex> исходов схемы <tex>\mathcal{P}_m</tex> считаются окончательными.
 
Выбирается случайным образом один из исходов схемы <tex>\mathcal{P}_m</tex>, и если произошел <tex>m</tex>-й исход, выбирается случайно один из исходов схемы <tex>\mathcal{R}_k</tex>, а остальные <tex>m - 1</tex> исходов схемы <tex>\mathcal{P}_m</tex> считаются окончательными.
  
В этой комбинированной схеме <tex>\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, ..., m - 1, (m, 1), (m, 2), ..., (m, k)</tex> с вероятностями <tex>p_1, p_2, ..., p_{m-1}, p_mq_1, p_mq_2, ..., p_mq_k</tex>
+
В этой комбинированной схеме <tex>\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)</tex> с вероятностями <tex>p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \dots, p_mq_k</tex>
  
 
Легко видеть, что <tex>H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)</tex>.
 
Легко видеть, что <tex>H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)</tex>.
Строка 34: Строка 34:
 
Для доказательства формулы вычисления энтропии сначала докажем лемму.
 
Для доказательства формулы вычисления энтропии сначала докажем лемму.
 
{{Лемма
 
{{Лемма
|statement = <tex dpi="140">g(n) = H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}) = -k \log_2 \frac{1}{n} = k \log_2n</tex>
+
|statement = <tex dpi="140">g(n) = H(\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}) = -k \log_2 \dfrac{1}{n} = k \log_2n</tex>
 
|proof =
 
|proof =
 
Будем рассматривать для <tex>k=1</tex> (бит).
 
Будем рассматривать для <tex>k=1</tex> (бит).
  
 
Рассмотрим функцию <tex>g(mn)</tex>:
 
Рассмотрим функцию <tex>g(mn)</tex>:
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \frac{1}{m} g(n) = g(m)+g(n)</tex>
+
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \dfrac{1}{m} g(n) = g(m)+g(n)</tex>
  
 
Пусть: <tex>g(2)=1 \quad</tex>, тогда <tex>g(2^t)=t</tex> и <tex> \quad g(n^t)=t \cdot g(n)</tex>
 
Пусть: <tex>g(2)=1 \quad</tex>, тогда <tex>g(2^t)=t</tex> и <tex> \quad g(n^t)=t \cdot g(n)</tex>
  
Рассмотрим такое <tex> i </tex>, что <tex>2^i \leqslant n^t < 2^{i+1}</tex>
+
Рассмотрим такое <tex> i </tex>, что <tex>2^i \leqslant n^t < 2^{i+1}</tex>
  
 
Можно заметить, что если <tex> i=[ \log_2 n^t ] </tex>, то неравенство останется верным.
 
Можно заметить, что если <tex> i=[ \log_2 n^t ] </tex>, то неравенство останется верным.
  
 
По предыдущим рассуждениям получаем, что:
 
По предыдущим рассуждениям получаем, что:
:<tex>g(2^i) \leq g(n^t) < g(2^{i+1})</tex>
+
:<tex>g(2^i) \leqslant g(n^t) < g(2^{i+1})</tex>
  
: <tex> i \leq t \cdot g(n) <i+1 \quad \quad </tex>
+
: <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex>
  
 
Делим неравенство на <tex>t</tex>:
 
Делим неравенство на <tex>t</tex>:
: <tex dpi="140">\frac{i}{t} \leq g(n) < \frac{i+1}{t}</tex>, то есть <tex dpi="140">\frac{[ \log_2 n^t ]}{t} \leq g(n) < \frac{[ \log_2 n^t ]+1}{t}</tex>
+
: <tex dpi="140">\dfrac{i}{t} \leqslant g(n) < \dfrac{i+1}{t}</tex>, то есть <tex dpi="140">\dfrac{[ \log_2 n^t ]}{t} \leqslant g(n) < \dfrac{[ \log_2 n^t ]+1}{t}</tex>
  
 
Отсюда ясно, что если <tex> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</tex>
 
Отсюда ясно, что если <tex> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</tex>
Строка 59: Строка 59:
  
 
{{Теорема
 
{{Теорема
|statement= <tex dpi="140">H(p_1, p_2, ..., p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\frac{1}{p_i}</tex>
+
|statement= <tex dpi="140">H(p_1, p_2, \dots, p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}</tex>
 
|proof =
 
|proof =
  
  
Теперь рассмотрим функцию <tex dpi="140">H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n})</tex>
+
Теперь рассмотрим функцию <tex dpi="140">H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})</tex>
  
Приведем дроби внутри функции к одному знаменателю, получаем: <tex dpi="140"> H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}) = H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \frac{x_n}{b})</tex>
+
Приведем дроби внутри функции к одному знаменателю, получаем: <tex dpi="140"> H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})</tex>
  
 
Далее по свойству энтропии и доказанной лемме:
 
Далее по свойству энтропии и доказанной лемме:
: <tex dpi="140">g(b)= H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \frac{x_n}{b}) + \sum\limits_{i=1}^{n} \frac{x_i}{b} g(x_i)</tex>
+
: <tex dpi="140">g(b)= H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) + \sum\limits_{i=1}^{n} \dfrac{x_i}{b} g(x_i)</tex>
  
: <tex dpi="140">H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \frac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \frac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \frac{x_i}{b} \log_2 \frac{x_i}{b}</tex>
+
: <tex dpi="140">H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}</tex>
При <tex dpi="140"> p_i = \frac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, ..., p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \frac{1}{p_i}</tex>  
+
При <tex dpi="140"> p_i = \dfrac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \dfrac{1}{p_i}</tex>  
 
}}
 
}}
 +
 +
== Примеры ==
 +
=== Энтропия честной монеты ===
 +
Рассмотрим [[Вероятностное пространство, элементарный исход, событие|вероятностное пространство]] {{---}} честная монета.
 +
Найдем для нее энтропию:
 +
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot (-1)} = 1</tex>
 +
Это означает что после броска честной монеты мы получим информацию в размере <tex>1</tex> бит, уменьшив степень неопределенности вдвое.
 +
 +
=== Энтропия нечестной монеты ===
 +
Найдем энтропию для [[Вероятностное пространство, элементарный исход, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] <tex>\{0,2; 0,8\}</tex>:
 +
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 < 1 </tex>
  
 
== Ограниченность энтропии ==
 
== Ограниченность энтропии ==
 
{{Теорема
 
{{Теорема
|statement= <tex>0 \leqslant H(p_1, p_2, ..., p_n) \leqslant \log_2n </tex>
+
|statement= <tex>0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n </tex>
 
|proof =
 
|proof =
 
1) Докажем первую часть неравенства:
 
1) Докажем первую часть неравенства:
  
Так как <tex> p_i\in[0,\;1]</tex>, тогда <tex dpi="140">\log_2\frac{1}{p_i} \geqslant 0 </tex>. Таким образом <tex dpi="140"> H(p_1, p_2, ..., p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \frac{1}{p_i} \geqslant 0 </tex>
+
Так как <tex> p_i\in[0,\;1]</tex>, тогда <tex dpi="140">\log_2\dfrac{1}{p_i} \geqslant 0 </tex>. Таким образом <tex dpi="140"> H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{1}{p_i} \geqslant 0 </tex>
  
 
2) Докажем вторую часть неравенства:
 
2) Докажем вторую часть неравенства:
  
 
<tex dpi="140"> f(x)=\log_2x </tex> {{---}} выпуклая вверх функция, <tex> p_1,p_2,\ldots,p_n>0</tex> и <tex> \sum \limits_{i=1}^{n} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена:
 
<tex dpi="140"> f(x)=\log_2x </tex> {{---}} выпуклая вверх функция, <tex> p_1,p_2,\ldots,p_n>0</tex> и <tex> \sum \limits_{i=1}^{n} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена:
<tex dpi="140"> \sum\limits_{i=1}^{n} p_i f(\frac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\frac{1}{p_i})) </tex>
+
<tex dpi="140"> \sum\limits_{i=1}^{n} p_i f(\dfrac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\dfrac{1}{p_i})) </tex>
Таким образом получаем, что <tex> H(p_1, p_2, ..., p_n) \leqslant \log_2n </tex>
+
Таким образом получаем, что <tex> H(p_1, p_2, \dots, p_n) \leqslant \log_2n </tex>
 
}}
 
}}
 
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
 
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
Строка 95: Строка 106:
 
<tex>H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex>
 
<tex>H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex>
 
{{Определение
 
{{Определение
|definition = '''Взаимная энтропия''' {{---}} энтропия объединения двух событий A и B.   
+
|definition = '''Взаимная энтропия''' (англ. ''joint entropy'') {{---}} энтропия объединения двух событий <tex>A</tex> и <tex>B</tex>.   
 
}}
 
}}
 
<tex> H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) </tex>
 
<tex> H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) </tex>
 
{{Утверждение
 
{{Утверждение
 
|statement= <tex> H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) </tex>
 
|statement= <tex> H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) </tex>
|proof= По формуле условной вероятности <tex dpi="130"> p(a_j|b_i)=\frac{p(a_j \cap b_i)}{p(b_i)} </tex>
+
|proof= По формуле условной вероятности <tex dpi="130"> p(a_j|b_i)=\dfrac{p(a_j \cap b_i)}{p(b_i)} </tex>
  
<tex dpi="140"> H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex> <tex dpi="140">= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \frac{p(a_j \cap b_i)}{p(b_i)}\log_2 \frac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \frac {p(a_j \cap b_i)}{p(b_i)} = </tex>  
+
<tex dpi="140"> H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex> <tex dpi="140">= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \dfrac{p(a_j \cap b_i)}{p(b_i)}\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = </tex>  
 
<tex dpi="140"> = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) </tex><tex dpi="140">= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = </tex>
 
<tex dpi="140"> = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) </tex><tex dpi="140">= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = </tex>
  
Строка 115: Строка 126:
  
 
== См. также ==
 
== См. также ==
*[[Формула Байеса|Формула Байеса]]
+
*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]
 +
*[[Условная вероятность|Условная вероятность]]
  
 
== Источники информации ==
 
== Источники информации ==
 
* И.В. Романовский "Дискретный анализ"
 
* И.В. Романовский "Дискретный анализ"
* [http://ru.wikipedia.org/wiki/Информационная_энтропия: Информационная энтропия]
+
* [http://ru.wikipedia.org/wiki/Информационная_энтропия Википедия {{---}} Информационная энтропия]
 +
* [https://en.wikipedia.org/wiki/Entropy_(information_theory) Wkipedia {{---}} Entropy(information_theory)]  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
 
[[Категория: Теория вероятности ]]
 
[[Категория: Теория вероятности ]]

Версия 22:48, 4 марта 2018

Определение

Определение:
Энтропия случайного источника (англ. Shannon entropy) — функция от вероятностей исходов: [math]H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} [/math], характеризующая количество информации, приходящейся на одно сообщение источника.


Свойства

Энтропия должна удовлетворять следующим требованиям:

  • Функция [math]H(p_1, p_2, \dots, p_n)[/math] определена и непрерывна для всех таких наборов [math]p_i\in[0,\;1][/math], что [math] \sum\limits_{i = 1}^{n} p_i = 1[/math]
  • [math]H(\underbrace{\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}}_\text{n}) \lt H(\underbrace{\dfrac{1}{n+1}, \dfrac{1}{n+1}, \dots, \dfrac{1}{n+1}}_\text{n+1})[/math]
  • [math] H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, \dots, p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, \dots, q_{ik_i})[/math]

[math]\rhd[/math]

Рассмотрим схему [math]\mathcal{P}_m[/math] c [math]m[/math] исходами и вероятностями [math]\{p_1, p_2, \dots, p_m\}[/math] и схему [math]\mathcal{R}_k[/math] с [math]k[/math] исходами и вероятностями [math]\{q_1, q_2, \dots, q_k\}[/math].

Образуем комбинированную схему c [math]m + k - 1[/math] исходами следующим образом:

Выбирается случайным образом один из исходов схемы [math]\mathcal{P}_m[/math], и если произошел [math]m[/math]-й исход, выбирается случайно один из исходов схемы [math]\mathcal{R}_k[/math], а остальные [math]m - 1[/math] исходов схемы [math]\mathcal{P}_m[/math] считаются окончательными.

В этой комбинированной схеме [math]\mathcal{PR}[/math] мы получаем исходы [math]1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)[/math] с вероятностями [math]p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \dots, p_mq_k[/math]

Легко видеть, что [math]H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)[/math].

Потребуем выполнения этого свойства для любой меры неопределенности. [math]\lhd[/math]

Вычисление энтропии

Для доказательства формулы вычисления энтропии сначала докажем лемму.

Лемма:
[math]g(n) = H(\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}) = -k \log_2 \dfrac{1}{n} = k \log_2n[/math]
Доказательство:
[math]\triangleright[/math]

Будем рассматривать для [math]k=1[/math] (бит).

Рассмотрим функцию [math]g(mn)[/math]:

[math]g(mn)=g(m)+ \sum\limits_{i=1}^{m} \dfrac{1}{m} g(n) = g(m)+g(n)[/math]

Пусть: [math]g(2)=1 \quad[/math], тогда [math]g(2^t)=t[/math] и [math] \quad g(n^t)=t \cdot g(n)[/math]

Рассмотрим такое [math] i [/math], что [math]2^i \leqslant n^t \lt 2^{i+1}[/math]

Можно заметить, что если [math] i=[ \log_2 n^t ] [/math], то неравенство останется верным.

По предыдущим рассуждениям получаем, что:

[math]g(2^i) \leqslant g(n^t) \lt g(2^{i+1})[/math]
[math] i \leqslant t \cdot g(n) \lt i+1 \quad \quad [/math]

Делим неравенство на [math]t[/math]:

[math]\dfrac{i}{t} \leqslant g(n) \lt \dfrac{i+1}{t}[/math], то есть [math]\dfrac{[ \log_2 n^t ]}{t} \leqslant g(n) \lt \dfrac{[ \log_2 n^t ]+1}{t}[/math]
Отсюда ясно, что если [math] t\rightarrow \infty[/math], то получаем [math]g(n) = \log_2n[/math]
[math]\triangleleft[/math]
Теорема:
[math]H(p_1, p_2, \dots, p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}[/math]
Доказательство:
[math]\triangleright[/math]

Теперь рассмотрим функцию [math]H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})[/math]

Приведем дроби внутри функции к одному знаменателю, получаем: [math] H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})[/math]

Далее по свойству энтропии и доказанной лемме:

[math]g(b)= H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) + \sum\limits_{i=1}^{n} \dfrac{x_i}{b} g(x_i)[/math]
[math]H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}[/math]
При [math] p_i = \dfrac{x_i}{b} [/math] получаем, что [math]H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \dfrac{1}{p_i}[/math]
[math]\triangleleft[/math]

Примеры

Энтропия честной монеты

Рассмотрим вероятностное пространство — честная монета. Найдем для нее энтропию:

[math]H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot (-1)} = 1[/math]

Это означает что после броска честной монеты мы получим информацию в размере [math]1[/math] бит, уменьшив степень неопределенности вдвое.

Энтропия нечестной монеты

Найдем энтропию для вероятностного пространства нечестная монета с распределением Бернулли [math]\{0,2; 0,8\}[/math]:

[math]H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 \lt 1 [/math]

Ограниченность энтропии

Теорема:
[math]0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math]
Доказательство:
[math]\triangleright[/math]

1) Докажем первую часть неравенства:

Так как [math] p_i\in[0,\;1][/math], тогда [math]\log_2\dfrac{1}{p_i} \geqslant 0 [/math]. Таким образом [math] H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{1}{p_i} \geqslant 0 [/math]

2) Докажем вторую часть неравенства:

[math] f(x)=\log_2x [/math] — выпуклая вверх функция, [math] p_1,p_2,\ldots,p_n\gt 0[/math] и [math] \sum \limits_{i=1}^{n} p_i = 1 [/math], тогда для нее выполняется неравенство Йенсена: [math] \sum\limits_{i=1}^{n} p_i f(\dfrac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\dfrac{1}{p_i})) [/math]

Таким образом получаем, что [math] H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math]
[math]\triangleleft[/math]

Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.

Условная и взаимная энтропия

Определение:
Условная энтропия (англ. conditional entropy) — определяет количество остающейся энтропии (то есть, остающейся неопределенности) события [math]A[/math] после того, как становится известным результат события [math]B[/math]. Она называется энтропия [math]A[/math] при условии [math]B[/math], и обозначается [math]H(A|B)[/math]

[math]H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) [/math]

Определение:
Взаимная энтропия (англ. joint entropy) — энтропия объединения двух событий [math]A[/math] и [math]B[/math].

[math] H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) [/math]

Утверждение:
[math] H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) [/math]
[math]\triangleright[/math]

По формуле условной вероятности [math] p(a_j|b_i)=\dfrac{p(a_j \cap b_i)}{p(b_i)} [/math]

[math] H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) [/math] [math]= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \dfrac{p(a_j \cap b_i)}{p(b_i)}\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = [/math] [math] = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) [/math][math]= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = [/math]

[math] = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) = [/math][math]H(A \cap B) - H(B) [/math]

Таким образом получаем, что: [math] H(A \cap B)= H(A|B)+H(B) [/math]

Аналогично: [math]H(B \cap A)= H(B|A)+H(A) [/math]

Из двух полученных равенств следует, что [math] H(A|B)+H(B)=H(B|A)+H(A) [/math]
[math]\triangleleft[/math]

См. также

Источники информации