147
правок
Изменения
Нет описания правки
== Определение ==
Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
}}
Пусть задан случайный источник.
: <tex>H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} </tex>
: <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(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 </tex>
==Вычисление энтропии==
{{Теорема
|statement= <tex>H(p_1, p_2, ..., p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i </tex>
|proof =
Для доказательства теоремы сначала докажем лемму.
{{Лемма
|statement = <tex>g(n) = H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}) = -k \log_2 \frac{1}{n}</tex>
|proof =
Будем рассматривать для <tex>k=1</tex> (1 бит).
Рассмотрим функцию <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 g(2^k)=k</tex>
: <tex>g(n) = \log_2(n) \quad \quad g(n^k)=k \cdot g(n)</tex>
: <tex>2^i \leq n^k < 2^i+1 \quad \quad g(2^i) \leq g(n^k) < g(2^{i+1})</tex>
: <tex>i=\lfloor \log_2 n^k\rfloor \quad \quad i \leq k \cdot g(n) <i+1</tex>
: <tex>\frac{i}{k} \leq g(n) < \frac{i+1}{k}</tex>
: <tex> k\rightarrow \infty \quad \quad g(n) = \log_2n = -k \log_2 \frac{1}{n}</tex>
}}
Теперь рассмотрим функцию <tex>H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n})</tex>
}}
