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

Определение

Определение:

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

Пусть задан случайный источник.

Пусть мы имеем вероятностную схему [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]

Свойства

1. Функция [math]H(p_1, p_2, ..., p_n)[/math] непрерывна.
2. [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]
3. [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]
4. [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]

Литература

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