Изменения

|definition = '''Энтропия случайного источника''' — (англ. ''Shannon entropy'') {{---}} функция от вероятностей исходов: <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(\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_{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, 2, ..., m - 1, H(mp_1, 1)p_2, (m\dots, 2p_n)</tex> определена и непрерывна для всех таких наборов <tex>p_i\in[0, ...\;1]</tex>, (m, k)что <tex> \sum\limits_{i = 1}^{n} p_i = 1</tex>

::* <texdpi ="130">H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, ...\dots, p_p_n) + \sum\limits_{m-i=1}^{n} p_iH(q_{i1}, p_mq_1\dots, p_mq_2, ..., p_mq_kq_{ik_i})</tex><tex>\rhd</tex>

::Легко видеть, что Рассмотрим схему <tex>H(\mathcal{PRP}) = H(_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\mathcal{Pp_1, p_2, \dots, p_m\}_m) + p_mH(</tex> и схему <tex>\mathcal{R}_k)</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, \dots, q_k\}</tex>.

Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом::Потребуем выполнения этого свойства для любой меры неопределенности.:Выбирается случайным образом один из исходов схемы <tex>\lhdmathcal{P}_m</tex>, и если произошел <tex>m</tex> * -й исход, выбирается случайно один из исходов схемы <tex>H(\mathcal{R}_k</tex>, а остальные <tex>m - 1</tex> исходов схемы <tex>\fracmathcal{1P}_m</tex> считаются окончательными. В этой комбинированной схеме <tex>\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)</tex> с вероятностями <tex>p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \fracdots, p_mq_k</tex> Легко видеть, что <tex>H(\mathcal{1PR}) = H(\mathcal{2P}_m) + p_mH(\mathcal{R}_k) = 1 </tex>. Потребуем выполнения этого свойства для любой меры неопределенности.<tex>\lhd</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(\fracdfrac{1}{n}, \fracdfrac{1}{n}, ...\dots, \fracdfrac{1}{n}) = -k \log_2 \fracdfrac{1}{n}= k \log_2n</tex>

: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \fracdfrac{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> i </tex>, что <tex>2^i \leqslant n^t < 2^{i+1}</tex> Можно заметить, что если <tex> i=[ \log_2 n^t ] </tex>, то неравенство останется верным. По предыдущим рассуждениям получаем, что::<tex>g(2^i) \leqslant g(n^t) < g(2^{i+1})</tex> : <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex>

Заметим, чтоДелим неравенство на <tex>t</tex>:: <texdpi="140">\dfrac{i}{t} \leqslant g(2n)< \dfrac{i+1}{t}</tex>, то есть <tex dpi=1 "140">\dfrac{[ \log_2 n^t ]}{t} \quad leqslant g(2n) < \dfrac{[ \log_2 n^t)=]+1}{t}</tex>

Аналогично:: Отсюда ясно, что если <tex>g(n) = t\log_2(n) rightarrow \quad \quad infty</tex>, то получаем <tex>g(n^t)=t \cdot g(n)log_2n</tex>}}

По предыдущим рассуждениямПриведем дроби внутри функции к одному знаменателю, получаем:<texdpi="140">gH(2^i) \leq g(n^tdfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) < g= H(2^\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{i+1b})</tex>

: <texdpi="140"> i H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \leq t dots, \cdot g(ndfrac{x_n}{b}) <= \log_2b - \sum\limits_{i+=1 }^{n} \quad dfrac{x_i}{b} \quad log_2x_i = -\sum\limits_{i=1}^{n} \lfloor dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}</tex>При <tex dpi="140"> p_i = \dfrac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^t{n} p_i \rfloor log_2 \dfrac{1}{p_i}</tex>}}

Разделив на === Энтропия нечестной монеты ===Найдем энтропию для [[Вероятностное пространство, элементарный исход, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] <tex>t\{0,2; 0,8\}</tex> получаем:: <texdpi="140">H(X) = -\sum\fraclimits_{i=1}^{tn} p_i \leq glog_2p_i = -0.2\log_2(n0.2)-0.8\log_2(0.8) \approx 0.722 < \frac{i+1}{t}</tex>

Отсюда ясноТак как <tex> p_i\in[0, что если: \;1]</tex> t, тогда <tex dpi="140">\log_2\dfrac{1}{p_i} \geqslant 0 </tex>. Таким образом <tex dpi="140"> H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \rightarrow dfrac{1}{p_i} \inftygeqslant 0 </tex>

то получаем2) Докажем вторую часть неравенства:<tex>g(n) = \log_2n</tex>

Теперь рассмотрим функцию <texdpi="140">= H(A \fraccap B) +\sum\limits_{a_1i=1}^{b_1m}, \fraclog_2p(b_i)\sum\limits_{a_2j=1}^{b_2n}, ..., p(a_j \fraccap b_i) = H(A \cap B) +\sum\limits_{a_ni=1}^{b_nm}\log_2p(b_i)p(b_i) = </tex><tex dpi="140">H(A \cap B) - H(B)</tex>

Приведем дроби внутри функции к одному знаменателюТаким образом получаем, получаемчто: <tex>H(A \frac{a'_1}{b}, \frac{a'_2}{b}, ..., \frac{a'_n}{b}cap B)= H(A|B)+H(B)</tex>

Далее по свойству 3:Аналогично: <tex>gH(bB \cap A)= H(\frac{a'_1}{b}, \frac{a'_2}{b}, ..., \frac{a'_n}{b}B|A) + \sum\limits_{i=1}^{n} \frac{a'_i}{b} gH(a'_iA)</tex>

: <tex>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}</tex>}}*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]*[[Условная вероятность|Условная вероятность]]*[[Арифметическое кодирование|Арифметическое кодирование]]

== Литература Источники информации ==