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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 9: Строка 9:
 
}}
 
}}
 
Пусть задан случайный источник.
 
Пусть задан случайный источник.
 
 
Пусть мы имеем вероятностную схему <tex>\mathcal{P}</tex> от этого источника с <tex>n</tex> исходами, и вероятности этих исходов равны <tex>p_1, p_2, ..., p_n</tex>.
 
Пусть мы имеем вероятностную схему <tex>\mathcal{P}</tex> от этого источника с <tex>n</tex> исходами, и вероятности этих исходов равны <tex>p_1, p_2, ..., p_n</tex>.
  
Строка 19: Строка 18:
 
== Свойства ==
 
== Свойства ==
  
# Функция <tex>H(p_1, p_2, ..., p_n)</tex> непрерывна.
+
* Функция <tex>H(p_1, p_2, ..., p_n)</tex> непрерывна.
# <tex>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>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>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_i, ..., q_{ik_i})</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(q_i, ..., q_{ik_i})</tex>
# <tex>H(\{\frac{1}{2}, \frac{1}{2}\}) = 1 </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> 
 +
* <tex>H(\{\frac{1}{2}, \frac{1}{2}\}) = 1 </tex>
  
 
==Вычисление энтропии==
 
==Вычисление энтропии==

Версия 10:26, 14 января 2011

Определение

Определение:
Энтропией случайной схемы называется мера содержащейся в этой схеме неопределенности.
Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.

Пусть задан случайный источник. Пусть мы имеем вероятностную схему [math]\mathcal{P}[/math] от этого источника с [math]n[/math] исходами, и вероятности этих исходов равны [math]p_1, p_2, ..., p_n[/math].

Тогда энтропия задается как вполне конкретная функция от вероятностей исходов.

[math]H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} [/math]
[math]H(p_1, p_2, ..., p_n)[/math]

Свойства

  • Функция [math]H(p_1, p_2, ..., p_n)[/math] непрерывна.
  • [math]H(\underbrace{\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}}_\text{n}) \lt H(\underbrace{\frac{1}{n+1}, \frac{1}{n+1}, ..., \frac{1}{n+1}}_\text{n+1})[/math]
  • [math]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_i, ..., q_{ik_i})[/math]
[math]\rhd[/math]
Рассмотрим схему [math]\mathcal{P}_m[/math] c [math]m[/math] исходами и вероятностями [math]\{p_1, p_2, ..., p_m\}[/math] и схему [math]\mathcal{R}_k[/math] с [math]k[/math] исходами и вероятностями [math]\{q_1, q_2, ..., 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, ..., m - 1, (m, 1), (m, 2), ..., (m, k)[/math]
с вероятностями
[math]p_1, p_2, ..., p_{m-1}, p_mq_1, p_mq_2, ..., p_mq_k[/math]
Легко видеть, что [math]H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)[/math].
Потребуем выполнения этого свойства для любой меры неопределенности.
[math]\lhd[/math]
  • [math]H(\{\frac{1}{2}, \frac{1}{2}\}) = 1 [/math]

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

Теорема:
[math]H(p_1, p_2, ..., p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i [/math]
Доказательство:
[math]\triangleright[/math]

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

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

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

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

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


[math]g(2)=1 \quad g(2^k)=k[/math]


[math]g(n) = \log_2(n) \quad \quad g(n^k)=k \cdot g(n)[/math]


[math]2^i \leq n^k \lt 2^i+1 \quad \quad g(2^i) \leq g(n^k) \lt g(2^{i+1})[/math]


[math]i=\lfloor \log_2 n^k\rfloor \quad \quad i \leq k \cdot g(n) \lt i+1[/math]


[math]\frac{i}{k} \leq g(n) \lt \frac{i+1}{k}[/math]


[math] k\rightarrow \infty \quad \quad g(n) = \log_2n = -k \log_2 \frac{1}{n}[/math]
[math]\triangleleft[/math]


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

Приведем дроби внутри функции к одному знаменателю, получаем: [math]H(\frac{a'_1}{b}, \frac{a'_2}{b}, ..., \frac{a'_n}{b})[/math]

Далее по свойству 3:

[math]g(b)= H(\frac{a'_1}{b}, \frac{a'_2}{b}, ..., \frac{a'_n}{b}) + \sum\limits_{i=1}^{n} \frac{a'_i}{b} g(a'_i)[/math]


[math]H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}) = \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}[/math]
[math]\triangleleft[/math]

Литература

  • И.В. Романовкий "Дискретный анализ"