|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 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>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>* <texdpi ="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\mathcal{P}_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\{p_1, 2p_2, ..., m - 1, (mp_m\}</tex> и схему <tex>\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, 1), (m, 2)q_2, ..., (m, k)q_k\}</tex>.
Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом::с вероятностями
::Выбирается случайным образом один из исходов схемы <tex>p_1\mathcal{P}_m</tex>, p_2и если произошел <tex>m</tex>-й исход, ...выбирается случайно один из исходов схемы <tex>\mathcal{R}_k</tex>, p_{а остальные <tex>m-1</tex> исходов схемы <tex>\mathcal{P}, p_mq_1, p_mq_2, ..., p_mq_k_m</tex>считаются окончательными.
::Легко видеть, что В этой комбинированной схеме <tex>H(\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, ..., m - 1, (m, 1) = H, (\mathcal{P}_mm, 2) + p_mH, ..., (\mathcalm, k)</tex> с вероятностями <tex>p_1, p_2, ..., p_{Rm-1}_k), 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>
==Вычисление энтропии==
{{Теорема|statement= <tex>H(p_1, p_2, ..., p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i </tex>|proof = Для доказательства теоремы формулы вычисления энтропии сначала докажем лемму.
{{Лемма
|statement = <texdpi="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)=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>g(n) = \log_2(n) \quad i </tex>, что <tex>2^i \quad g(leqslant n^t)=t \cdot g(n)< 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>g(2^i) \leq t \cdot g(n^t) < g(2^{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> i t\leq t rightarrow \cdot infty</tex>, то получаем <tex>g(n) <i+1 \quad \quad i=\lfloor \log_2 n^t\rfloor 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>t</tex> получаем
: <tex>\frac{i}{t} \leq g(n) < \frac{i+1}{t}</tex>
Теперь рассмотрим функцию <tex dpi="140">H(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n})</tex>
Отсюда ясноПриведем дроби внутри функции к одному знаменателю, что еслиполучаем: <texdpi="140"> tH(\rightarrow frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}) = H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \inftyfrac{x_n}{b})</tex>
то получаемДалее по свойству энтропии и доказанной лемме::<texdpi="140">g(nb)= H(\frac{x_1}{b}, \frac{x_2}{b}, ..., \frac{x_n}{b}) + \sum\limits_{i= 1}^{n} \log_2nfrac{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>H(p_i\frac{a_1}{b_1}in[0, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n});1]</tex> Приведем дроби внутри функции к одному знаменателю, получаем: тогда <texdpi="140">H(\frac{a'_1}{b}, log_2\frac{a'_21}{bp_i}, ..., \frac{a'_n}{b})geqslant 0 </tex> Далее по свойству 3:: . Таким образом <texdpi="140">g(b)= H(\frac{a'_1}{b}p_1, \frac{a'_2}{b}p_2, ..., \frac{a'_n}{b}p_n) + = \sum\limits_{i=1}^{n} p_i\log_2 \frac{a'_i1}{bp_i} g(a'_i)\geqslant 0 </tex>
2) Докажем вторую часть неравенства:
: <texdpi="140">Hf(x)=\frac{a_1}{b_1}log_2x </tex> — выпуклая вверх функция, <tex> p_1,p_2, \fracldots,p_n>0</tex> и <tex> \sum \limits_{a_2i=1}^{b_2n}p_i = 1 </tex>, тогда для нее выполняется [http://ru.wikipedia.., \frac{a_n}{b_n}) org/wiki/Неравенство_Йенсена: неравенство Йенсена]:<tex dpi= \log_2b - "140"> \sum\limits_{i=1}^{n} p_i\log_2\frac{a_i1}{b_ip_i} \log_2a'_i = -leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\frac{a_i1}{b_ip_i} )) </tex>Таким образом получаем, что <tex> H(p_1, p_2, ..., p_n) \log_2 leqslant \frac{a_i}{b_i}log_2n </tex>
}}
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
== Условная и взаимная энтропия ==
== Литература ==
