Лекция 1.Случайные события. Вероятность.
Рассмотрим дискретное множество \(\Omega\)[Kolmogorov1],[Boss1],[Grimmet1]. Каждому элементу \(\omega_i\in\Omega\) поставим в соответствие число \(p_i\in[0\ldots1]\) таким образом, чтобы \(\sum\limits_{p_i\in\Omega}p_i = 1\). Тогда любое подмножество \(A\in\Omega\) называется случайным событием \(A\), а величина \(p(A)=\sum\limits_{p_i\in A}p_i \) есть вероятность случайного события \(A\).
  1. А.Н. Колмогоров Основные понятия теории вероятностей. -Ленанд. 2018г.
  2. В. Босс Лекции по математике: вероятность, информация, статистика. Т. 4
  3. Geoffrey R. Grimmett David R. Stirzaker Probability And Random Processes. Oxford University Press. 2004
Лекция 2.Энтропия дискретного источника.
Рассмотрим два текстовых файла: первый файл содержит произвольные случайные символы. Второй файл содержит лишь символы A и B в произвольном порядке. Каждый файл содержит 1000 символов. Каждый символ представляется байтовым значением 0..255. Объем второго файла можно значительно сократить, если использовать лишь один бит для представления символов A и B. Например, символ A представляется значением 0, а символ B - значением 1. В этом случае объем второго файла будет равен 1000 бит. А объем первого файла составляет по-прежнему 8000 бит. На основании этого примера можно определить количество информации в файле как минимальный размер такого файла позволяющий сохранить всю информацию без потерь. Рассмотрим второй пример: Файл содержит символы A,B,C,D в произвольном порядке, при этом количество символов A-500, количество символов B-480, количество символов С-15 и количество символов D-5. Необходимо определить количество информации в файле. Так как количество различных символов равно 4, то для их представления требуется 2 бита на символ. В этом случае размер файла составляет 4*1000=4000 бит. Этот формат представления не является оптимальным так как никак не учитывает, что количество символов A и B значительно превышает количество символов C и D. Вместо поиска оптимального правила для хранения такого набора символов используем вероятностное описание. Будем рассматривать факт появления каждого из символов A,B,C,D как наступление одного из четырех случайных событий \(A, B, C, D\) с вероятностями \(p(A)=\frac{500}{1000}\), \(p(B)=\frac{480}{1000}\), \(p(C)=\frac{15}{1000}\) и \(p(D)=\frac{5}{1000}\), составляющими полную группу. Определим количество информации необходимое для хранения каждого из четырех типов символов. Символ A появляется в файле с вероятностью \(p(A)=0.5\). Если рассматривать такой символ отдельно, то соответсвующая ему полная группа равновероятных событий будет содержать два события: \(A\) и не-\(A\). Количество бит необходимое для представления элемента такой группы равно 1. Но используется такой символ с вероятностью \(0.5\), т.е. в среднее количество бит для представления этого символа без потерь равно \(0.5\). Полная группа несовместных событий для второго символа содержит дробное количество элементов \(\frac{1000}{480}\). Понимать это следует "в среднем". Т.е. в большинстве случаев эта группа состоит из двух элементов, но иногда из трех. Среднее количество бит для этого символа \(\log_2\left(\frac{1000}{480}\right)\), но сспользоваться такой символ будет с вероятностью \(p(B)=\frac{480}{1000}\). Поэтому окончательно для символа \(B\) получаем \(\frac{480}{1000}\log_2\left(\frac{1000}{480}\right)\). Общее количество информации в этом файле: \(\left[\frac{500}{1000}\log_2\left(\frac{1000}{500}\right) + \frac{480}{1000}\log_2\left(\frac{1000}{480}\right) + \frac{15}{1000}\log_2\left(\frac{1000}{15}\right) + \frac{5}{1000}\log_2\left(\frac{1000}{5}\right) \right]\times1000=1137.37165703039 \)
Обобщая на произвольный размер алфавита, информационная энтропия (количество информации) дискретного источника может быть представлена в виде(\ref{Entropy}): \begin{equation} H = \sum_{i=1}^{n}p_i\log_2\frac{1}{p_i}=-\sum_{i=1}^{n}p_i\log_2 p_i \label{Entropy} \end{equation}
  1. C. E. Shannon, Bell Syst. Tech. J. 27, 379 (1948).
 Вероятность того, что переменная \(y\) примет значение \(j\) при условии, что переменная \(x\) приняла значение \(i\): \begin{equation} p_i(j)=\frac{p(i,j)}{\sum_{j}p(i,j)} \end{equation} Условная энтропия \(H_x(y)\) : \begin{aligned} H_x(y) = -\sum_{i,j}p(i,j)\log p_i(j)=-\sum_{i,j}p(i,j)\log \frac{p(i,j)}{\sum_{j}p(i,j)}= \\ -\sum_{i,j}p(i,j)\log p(i,j)+\sum_{i,j}p(i,j)\log \sum_{j}p(i,j)=\\ H(x,y)-H(x) \end{aligned} Таким образом \begin{equation} H(x,y) = H_x(y) + H(x) \end{equation} Условная энтропия показывает меру неопределенности \(y\) при условии, что \(x\) известно. \begin{equation} H(x)+H(y) \geq H(x,y)=H_x(y) + H(x) \\ \end{equation} \begin{equation} H(y) \geq H_x(y) \end{equation}