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

Определение

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

Энтропия случайного источника — функция от вероятностей исходов: [math]H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} [/math], характеризующая количество информации, приходящейся на одно сообщение источника.

Свойства

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

• Функция [math]H(p_1, p_2, ..., p_n)[/math] определена и непрерывна для всех [math]p_i\in[0,\;1][/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_{i1}, ..., 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]g(n) = H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}) = -k \log_2 \frac{1}{n} = k \log_2n[/math]

Доказательство:

[math]\triangleright[/math]

Будем рассматривать для [math]k=1[/math] (бит). Рассмотрим функцию [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[/math], тогда [math]g(2^t)=t[/math] и [math] \quad g(n^t)=t \cdot g(n)[/math] Рассмотрим такое [math] i [/math], что [math]2^i \leqslant n^t \lt 2^{i+1}[/math] Можно заметить, что если [math] i=[ \log_2 n^t ] [/math], то неравенство останется верным. По предыдущим рассуждениям получаем, что: [math]g(2^i) \leq g(n^t) \lt g(2^{i+1})[/math] [math] i \leq t \cdot g(n) \lt i+1 \quad \quad [/math] Делим неравенство на [math]t[/math]: [math]\frac{i}{t} \leq g(n) \lt \frac{i+1}{t}[/math] или [math]\frac{[ \log_2 n^t ]}{t} \leq g(n) \lt \frac{[ \log_2 n^t ]+1}{t}[/math] Отсюда ясно, что если [math] t\rightarrow \infty[/math], то получаем [math]g(n) = \log_2n[/math]

[math]\triangleleft[/math]

Теорема:

[math]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}[/math]

Доказательство:

[math]\triangleright[/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_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}) = H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \frac{x_n}{b})[/math] Далее по свойству энтропии и доказанной лемме: [math]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)[/math] [math]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}[/math] При [math] p_i = \frac{x_i}{b} [/math] получаем, что [math]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}[/math]

[math]\triangleleft[/math]

Ограниченность энтропии

Теорема:

[math]0 \leqslant H(p_1, p_2, ..., p_n) \leqslant \log_2n [/math]

Доказательство:

[math]\triangleright[/math]

1) Докажем первую часть неравенства: Так как [math] p_i\in[0,\;1][/math], тогда [math]\log_2\frac{1}{p_i} \geqslant 0 [/math]. Таким образом [math] H(p_1, p_2, ..., p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \frac{1}{p_i} \geqslant 0 [/math] 2) Докажем вторую часть неравенства: [math] f(x)=\log_2x [/math] — выпуклая вверх функция, [math] p_1,p_2,\ldots,p_n\gt 0[/math] и [math] \sum \limits_{i=1}^{n} p_i = 1 [/math], тогда для нее выполняется неравенство Йенсена: [math] \sum\limits_{i=1}^{n} p_i\log_2\frac{1}{p_i} \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\frac{1}{p_i})) [/math] Таким образом получаем, что [math] H(p_1, p_2, ..., p_n) \leqslant \log_2n [/math]

[math]\triangleleft[/math]

Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.

Литература

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