Определение
| Определение: |
| Случайное блуждание (англ. Random walk) — математическая модель процесса случайных изменений — шагов в дискретные моменты времени. При этом предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса. |
Двумерный случай случайных блужданий
Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки
в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку k + 1 и с положительной вероятностью q = 1 − p
перемещается в точку k − 1. Физической системе соответствует цепь Маркова
- [math]\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{cases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p}
\end{cases}[/math]
Заметим, что вернуться в какую-либо точку можно только за четное число шагов.
- [math]H(\underbrace{\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}}_\text{n}) \lt H(\underbrace{\dfrac{1}{n+1}, \dfrac{1}{n+1}, \dots, \dfrac{1}{n+1}}_\text{n+1})[/math]
- [math] H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, \dots, p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, \dots, q_{ik_i})[/math]
[math]\rhd[/math]
Рассмотрим схему [math]\mathcal{P}_m[/math] c [math]m[/math] исходами и вероятностями [math]\{p_1, p_2, \dots, p_m\}[/math] и схему [math]\mathcal{R}_k[/math] с [math]k[/math] исходами и вероятностями [math]\{q_1, q_2, \dots, 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, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)[/math] с вероятностями [math]p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \dots, 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(\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}) = -k \log_2 \dfrac{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} \dfrac{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) \leqslant g(n^t) \lt g(2^{i+1})[/math]
- [math] i \leqslant t \cdot g(n) \lt i+1 \quad \quad [/math]
Делим неравенство на [math]t[/math]:
- [math]\dfrac{i}{t} \leqslant g(n) \lt \dfrac{i+1}{t}[/math], то есть [math]\dfrac{[ \log_2 n^t ]}{t} \leqslant g(n) \lt \dfrac{[ \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, \dots, p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Теперь рассмотрим функцию [math]H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})[/math]
Приведем дроби внутри функции к одному знаменателю, получаем: [math] H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})[/math]
Далее по свойству энтропии и доказанной лемме:
- [math]g(b)= H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) + \sum\limits_{i=1}^{n} \dfrac{x_i}{b} g(x_i)[/math]
- [math]H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}[/math]
При [math] p_i = \dfrac{x_i}{b} [/math] получаем, что [math]H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \dfrac{1}{p_i}[/math] |
| [math]\triangleleft[/math] |
Примеры
Энтропия честной монеты
Рассмотрим вероятностное пространство — честная монета.
Найдем для нее энтропию:
- [math]H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot (-1)} = 1[/math]
Это означает что после броска честной монеты мы получим информацию в размере [math]1[/math] бит, уменьшив степень неопределенности вдвое.
Энтропия нечестной монеты
Найдем энтропию для вероятностного пространства нечестная монета с распределением Бернулли [math]\{0,2; 0,8\}[/math]:
- [math]H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 \lt 1 [/math]
Ограниченность энтропии
| Теорема: |
[math]0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
1) Докажем первую часть неравенства:
Так как [math] p_i\in[0,\;1][/math], тогда [math]\log_2\dfrac{1}{p_i} \geqslant 0 [/math]. Таким образом [math] H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{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 f(\dfrac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\dfrac{1}{p_i})) [/math]
Таким образом получаем, что [math] H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math] |
| [math]\triangleleft[/math] |
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
Условная и взаимная энтропия
| Определение: |
| Условная энтропия (англ. conditional entropy) — определяет количество остающейся энтропии (то есть, остающейся неопределенности) события [math]A[/math] после того, как становится известным результат события [math]B[/math]. Она называется энтропия [math]A[/math] при условии [math]B[/math], и обозначается [math]H(A|B)[/math] |
[math]H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) [/math]
| Определение: |
| Взаимная энтропия (англ. joint entropy) — энтропия объединения двух событий [math]A[/math] и [math]B[/math]. |
[math] H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) [/math]
| Утверждение: |
[math] H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) [/math] |
| [math]\triangleright[/math] |
|
По формуле условной вероятности [math] p(a_j|b_i)=\dfrac{p(a_j \cap b_i)}{p(b_i)} [/math]
[math] H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) [/math] [math]= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \dfrac{p(a_j \cap b_i)}{p(b_i)}\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = [/math]
[math] = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) [/math][math]= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = [/math]
[math] = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) = [/math][math]H(A \cap B) - H(B) [/math]
Таким образом получаем, что: [math] H(A \cap B)= H(A|B)+H(B) [/math]
Аналогично: [math]H(B \cap A)= H(B|A)+H(A) [/math]
Из двух полученных равенств следует, что [math] H(A|B)+H(B)=H(B|A)+H(A) [/math] |
| [math]\triangleleft[/math] |
См. также
Источники информации
