Энтропия случайного источника — различия между версиями
Odintsova (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 24 промежуточные версии 8 участников) | |||
Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
− | |definition = '''Энтропия случайного источника''' | + | |definition = '''Энтропия случайного источника''' (англ. ''Shannon entropy'') {{---}} функция от вероятностей исходов: <tex>H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} </tex>, характеризующая количество информации, приходящейся на одно сообщение источника. |
}} | }} | ||
+ | |||
== Свойства == | == Свойства == | ||
'''Энтропия должна удовлетворять следующим требованиям:''' | '''Энтропия должна удовлетворять следующим требованиям:''' | ||
− | * Функция <tex>H(p_1, p_2, | + | * Функция <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 | + | * <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}, | + | * <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, | + | Рассмотрим схему <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> исходами следующим образом: | ||
Строка 22: | Строка 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, | + | В этой комбинированной схеме <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>. | ||
Потребуем выполнения этого свойства для любой меры неопределенности. | Потребуем выполнения этого свойства для любой меры неопределенности. | ||
− | <tex>\lhd</tex> | + | <tex>\lhd</tex> |
==Вычисление энтропии== | ==Вычисление энтропии== | ||
Строка 33: | Строка 34: | ||
Для доказательства формулы вычисления энтропии сначала докажем лемму. | Для доказательства формулы вычисления энтропии сначала докажем лемму. | ||
{{Лемма | {{Лемма | ||
− | |statement = <tex dpi="140">g(n) = H(\ | + | |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} \ | + | : <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) \ | + | :<tex>g(2^i) \leqslant g(n^t) < g(2^{i+1})</tex> |
− | : <tex> i \ | + | : <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex> |
Делим неравенство на <tex>t</tex>: | Делим неравенство на <tex>t</tex>: | ||
− | : <tex dpi="140">\ | + | : <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> | ||
Строка 58: | Строка 59: | ||
{{Теорема | {{Теорема | ||
− | |statement= <tex dpi="140">H(p_1, p_2, | + | |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(\ | + | Теперь рассмотрим функцию <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(\ | + | Приведем дроби внутри функции к одному знаменателю, получаем: <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(\ | + | : <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(\ | + | : <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 = \ | + | При <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, | + | |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\ | + | Так как <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 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(\ | + | <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, | + | Таким образом получаем, что <tex> H(p_1, p_2, \dots, p_n) \leqslant \log_2n </tex> |
}} | }} | ||
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны. | Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны. | ||
== Условная и взаимная энтропия == | == Условная и взаимная энтропия == | ||
{{Определение | {{Определение | ||
− | |definition = '''Условная энтропия''' | + | |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> | <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 = '''Взаимная энтропия''' | + | |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)=\ | + | |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} \ | + | <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> | ||
<tex dpi="140"> = 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) = </tex><tex dpi="140">H(A \cap B) - H(B) </tex> | <tex dpi="140"> = 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) = </tex><tex dpi="140">H(A \cap B) - H(B) </tex> | ||
− | Таким образом получаем, что: <tex> H(A \cap B)= H(B | + | Таким образом получаем, что: <tex> H(A \cap B)= H(A|B)+H(B) </tex> |
− | Аналогично: <tex>H(B \cap A)= H(A | + | Аналогично: <tex>H(B \cap A)= H(B|A)+H(A) </tex> |
Из двух полученных равенств следует, что <tex> H(A|B)+H(B)=H(B|A)+H(A) </tex> | Из двух полученных равенств следует, что <tex> H(A|B)+H(B)=H(B|A)+H(A) </tex> | ||
}} | }} | ||
− | == | + | |
+ | == См. также == | ||
+ | *[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]] | ||
+ | *[[Условная вероятность|Условная вероятность]] | ||
+ | *[[Арифметическое кодирование|Арифметическое кодирование]] | ||
+ | |||
+ | == Источники информации == | ||
* И.В. Романовский "Дискретный анализ" | * И.В. Романовский "Дискретный анализ" | ||
− | * [http://ru.wikipedia.org/wiki/Информационная_энтропия | + | * [http://ru.wikipedia.org/wiki/Информационная_энтропия Википедия {{---}} Информационная энтропия] |
+ | * [https://en.wikipedia.org/wiki/Entropy_(information_theory) Wkipedia {{---}} Entropy(information_theory)] | ||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория: Теория вероятности ]] | [[Категория: Теория вероятности ]] |
Текущая версия на 19:28, 4 сентября 2022
Содержание
Определение
Определение: |
Энтропия случайного источника (англ. Shannon entropy) — функция от вероятностей исходов: | , характеризующая количество информации, приходящейся на одно сообщение источника.
Свойства
Энтропия должна удовлетворять следующим требованиям:
- Функция определена и непрерывна для всех таких наборов , что
Рассмотрим схему
c исходами и вероятностями и схему с исходами и вероятностями .Образуем комбинированную схему c
исходами следующим образом:Выбирается случайным образом один из исходов схемы
, и если произошел -й исход, выбирается случайно один из исходов схемы , а остальные исходов схемы считаются окончательными.В этой комбинированной схеме
мы получаем исходы с вероятностямиЛегко видеть, что
.Потребуем выполнения этого свойства для любой меры неопределенности.
Вычисление энтропии
Для доказательства формулы вычисления энтропии сначала докажем лемму.
Лемма: |
Доказательство: |
Будем рассматривать для (бит).Рассмотрим функцию :Пусть: , тогда иРассмотрим такое , чтоМожно заметить, что если , то неравенство останется верным.По предыдущим рассуждениям получаем, что: Делим неравенство на :
|
Теорема: |
Доказательство: |
Теперь рассмотрим функцию Приведем дроби внутри функции к одному знаменателю, получаем: Далее по свойству энтропии и доказанной лемме: |
Примеры
Энтропия честной монеты
Рассмотрим вероятностное пространство — честная монета. Найдем для нее энтропию:
Это означает что после броска честной монеты мы получим информацию в размере
бит, уменьшив степень неопределенности вдвое.Энтропия нечестной монеты
Найдем энтропию для вероятностного пространства нечестная монета с распределением Бернулли :
Ограниченность энтропии
Теорема: |
Доказательство: |
1) Докажем первую часть неравенства: Так как , тогда . Таким образом2) Докажем вторую часть неравенства: Таким образом получаем, что — выпуклая вверх функция, и , тогда для нее выполняется неравенство Йенсена: |
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
Условная и взаимная энтропия
Определение: |
Условная энтропия (англ. conditional entropy) — определяет количество остающейся энтропии (то есть, остающейся неопределенности) события | после того, как становится известным результат события . Она называется энтропия при условии , и обозначается
Определение: |
Взаимная энтропия (англ. joint entropy) — энтропия объединения двух событий | и .
Утверждение: |
По формуле условной вероятности
Таким образом получаем, что: Аналогично: Из двух полученных равенств следует, что |
См. также
- Вероятностное пространство, элементарный исход, событие
- Условная вероятность
- Арифметическое кодирование
Источники информации
- И.В. Романовский "Дискретный анализ"
- Википедия — Информационная энтропия
- Wkipedia — Entropy(information_theory)