7
правок
Изменения
→См. также
'''Энтропия должна удовлетворять следующим требованиям:'''
* Функция <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{\left( \dfrac{1}{n}, \dfrac{1}{n}, ...\dots, \dfrac{1}{n}\right)}_\text{n}) < H(\underbrace{\left( \dfrac{1}{n+1}, \dfrac{1}{n+1}, ...\dots, \dfrac{1}{n+1}\right) }_\text{n+1})</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>\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> исходами следующим образом:
Выбирается случайным образом один из исходов схемы <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, ...\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>.
Для доказательства формулы вычисления энтропии сначала докажем лемму.
{{Лемма
|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 =
Будем рассматривать для <tex>k=1</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 =
Теперь рассмотрим функцию <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(\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(\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(\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 = \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} pi 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} pi 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, ...\dots, p_n) \leqslant \log_2n </tex>
|proof =
1) Докажем первую часть неравенства:
Так как <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) Докажем вторую часть неравенства:
<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(\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, ...\dots, p_n) \leqslant \log_2n </tex>
}}
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
<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 = '''Взаимная энтропия''' (англ. ''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>
*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]
*[[Условная вероятность|Условная вероятность]]
*[[Арифметическое кодирование|Арифметическое кодирование]]
== Источники информации ==
