1632
правки
Изменения
м
Энтропия — это количество информации* <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>nm</tex> исходами, и вероятности этих исходов равны вероятностями <tex>\{p_1, p_2, ...\dots, p_np_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>H: \bigcup\limits_mathcal{i=1P}^{_m</tex>, и если произошел <tex>m</tex>-й исход, выбирается случайно один из исходов схемы <tex>\infty} \mathbb{R}^i \rightarrow \mathbbmathcal{R} _k</tex>, а остальные <tex>m - 1</tex>: исходов схемы <tex>H(p_1, p_2, ..., p_n)\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(p_1, p_2, ...Легко видеть, p_n)</tex> непрерывна.# что <tex>H(\underbrace{\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}}_\textmathcal{nPR}) < = H(\underbrace{\fracmathcal{1P}{n_m) +1}, \frac{1}{n+1}, ..., \frac{1}{n+1}}_p_mH(\textmathcal{n+1R}_k)</tex>. # <tex>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(p_i, ..., p_{ik_i})</tex># <tex>H(\{\frac{1}{2}, \frac{1}{2}\}) = 1 lhd</tex>
{{Теорема|statement= <tex>H(p_1, p_2, ..., p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i </tex>|proof = Для доказательства теоремы формулы вычисления энтропии сначала докажем лемму.
: Рассмотрим такое <tex> i </tex>, что <tex>g(2)=1 ^i \quad g(leqslant n^t < 2^k)=k{i+1}</tex>
: {{Теорема|statement= <texdpi="140">iH(p_1, p_2, \dots, p_n) =-k \lfloor sum\log_2 limits_{i=1}^{n^} p_i\log_2p_i = k\rfloor \quad sum\quad limits_{i =1}^{n} p_i\leq k log_2\cdot g(n) <i+dfrac{1}{p_i}</tex>|proof =
: Теперь рассмотрим функцию <texdpi="140">H(\dfrac{a_1}{b_1}, \fracdfrac{ia_2}{kb_2} , \leq g(n) < dots, \fracdfrac{i+1a_n}{kb_n})</tex>
Теперь рассмотрим функцию <texdpi="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"> = -\fracsum\limits_{a_1i=1}^{b_1m}, \fracsum\limits_{a_2j=1}^{b_2n}, ..., p(a_j \cap b_i)\log_2p(a_j \fraccap b_i) + \sum\limits_{a_ni=1}^{b_nm}\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>
Приведем дроби внутри функции к одному знаменателю, получаем: <texdpi="140">= H(A \fraccap B) +\sum\limits_{a'_1i=1}^{bm}, \fraclog_2p(b_i)\sum\limits_{a'_2j=1}^{bn}, ..., p(a_j \fraccap b_i) = H(A \cap B) +\sum\limits_{a'_ni=1}^{bm}\log_2p(b_i)p(b_i) = </tex><tex dpi="140">H(A \cap B) - H(B)</tex>
Далее по свойству 3:Таким образом получаем, что: <tex>gH(bA \cap B)= H(\frac{a'_1}{b}, \frac{a'_2}{b}, ..., \frac{a'_n}{b}A|B) + \sum\limits_{i=1}^{n} \frac{a'_i}{b} gH(a'_iB)</tex>
: Из двух полученных равенств следует, что <tex>H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}A|B)+H(B) = \log_2b - \sum\limits_{i=1}^{n} \frac{a_i}{b_i} \log_2a'_i = -\sum\limits_{i=1}^{n} \frac{a_i}{b_i} \log_2 \frac{a_i}{b_i}H(B|A)+H(A) </tex>
rollbackEdits.php mass rollback
{{Определение
|definition ='''Энтропия случайного источника''' (англ. ''Shannon entropy'') {{---}} функция от вероятностей исходов: <tex>H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} </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{ \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}<br/tex>
==Вычисление энтропии==
{{Лемма
|statement = <texdpi="140">g(n) = H(\fracdfrac{1}{n}, \fracdfrac{1}{n}, ...\dots, \fracdfrac{1}{n}) = -k \log_2 \fracdfrac{1}{n}= k \log_2n</tex>
|proof =
Будем рассматривать для <tex>k=1</tex> (1 бит).
Рассмотрим функцию <tex>g(mn)</tex>:
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \fracdfrac{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> i=[ \log_2 n^t ] </tex>, то неравенство останется верным.
По предыдущим рассуждениям получаем, что:: <tex>g(n) = \log_2(n2^i) \quad \quad leqslant g(n^kt)=k \cdot < g(n2^{i+1})</tex>
: <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex>
Делим неравенство на <tex>t</tex>:: <texdpi="140">2^\dfrac{i }{t} \leq leqslant g(n^k ) < 2^\dfrac{i+1 }{t}</tex>, то есть <tex dpi="140">\quad dfrac{[ \quad g(2log_2 n^i) t ]}{t} \leq leqslant g(n^k) < g(2\dfrac{[ \log_2 n^{it ]+1}){t}</tex>
Отсюда ясно, что если <tex> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</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>
Далее по свойству энтропии и доказанной лемме:: <texdpi="140"> kg(b)= H(\rightarrow dfrac{x_1}{b}, \infty dfrac{x_2}{b}, \quad dots, \quad g(ndfrac{x_n}{b}) = \log_2n = -k + \log_2 sum\fraclimits_{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} 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, \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 исходов энтропия максимальна, если они все равновероятны.
== Условная и взаимная энтропия ==
{{Определение
|definition = '''Условная энтропия''' (англ. ''conditional entropy'') {{---}} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события <tex>A</tex> после того, как становится известным результат события <tex>B</tex>. Она называется ''энтропия <tex>A</tex> при условии <tex>B</tex>'', и обозначается <tex>H(A|B)</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 = '''Взаимная энтропия''' (англ. ''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>
{{Утверждение
|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)=\dfrac{p(a_j \cap b_i)}{p(b_i)} </tex>
Аналогично: <tex>H(B \cap A)= H(B|A)+H(A) </tex>
}}
== Литература См. также ==*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]*[[Условная вероятность|Условная вероятность]]*[[Арифметическое кодирование|Арифметическое кодирование]] == Источники информации ==* И.В. Романовкий Романовский "Дискретный анализ"* [http://ru.wikipedia.org/wiki/Информационная_энтропия Википедия {{---}} Информационная энтропия]* [https://en.wikipedia.org/wiki/Entropy_(information_theory) Wkipedia {{---}} Entropy(information_theory)] [[Категория:Дискретная математика и алгоритмы]] [[Категория: Теория вероятности ]]
