Энтропия случайного источника

2014-02-15T09:32:15Z

188.162.64.126: /* Свойства */

__TOC__
== Определение ==

{{Определение
|definition = '''Энтропия случайного источника''' {{---}} функция от вероятностей исходов: <tex>H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} </tex>, характеризующая количество информации, приходящейся на одно сообщение источника.
}}
== Свойства ==

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

* Функция <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 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(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>\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>.

Образуем комбинированную схему 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, ..., 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>H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)</tex>.

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

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

Для доказательства формулы вычисления энтропии сначала докажем лемму.
{{Лемма
|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>
|proof =
Будем рассматривать для <tex>k=1</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(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=[ \log_2 n^t ] </tex>, то неравенство останется верным.

По предыдущим рассуждениям получаем, что:
:<tex>g(2^i) \leq g(n^t) < g(2^{i+1})</tex>

: <tex> i \leq t \cdot g(n) <i+1 \quad \quad </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> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</tex>
}}

{{Теорема
|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>
|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(\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">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">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"> 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>
}}

== Ограниченность энтропии ==
{{Теорема
|statement= <tex>0 \leqslant H(p_1, p_2, ..., p_n) \leqslant \log_2n </tex>
|proof =
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>

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(\frac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\frac{1}{p_i})) </tex>
Таким образом получаем, что <tex> H(p_1, p_2, ..., p_n) \leqslant \log_2n </tex>
}}
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
== Условная и взаимная энтропия ==
{{Определение
|definition = '''Условная энтропия''' {{---}} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события <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 = '''Взаимная энтропия''' {{---}} энтропия объединения двух событий A и B.
}}
<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)=\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} \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"> = -\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> H(A \cap B)= H(A|B)+H(B) </tex>

Аналогично: <tex>H(B \cap A)= H(B|A)+H(A) </tex>

Из двух полученных равенств следует, что <tex> H(A|B)+H(B)=H(B|A)+H(A) </tex>
}}
== Литература ==
* И.В. Романовский "Дискретный анализ"
* [http://ru.wikipedia.org/wiki/Информационная_энтропия: Информационная энтропия]
[[Категория:Дискретная математика и алгоритмы]]

[[Категория: Теория вероятности ]]

Викиконспекты - Вклад участника [ru]

Энтропия случайного источника