Участник:Mk17.ru — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вероятность смещения на d единиц вправо или влево)
(Вероятность смещения на d единиц вправо или влево)
Строка 43: Строка 43:
 
ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли (1):
 
ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли (1):
  
*<tex> P(\xi_n = m + d) = {C_{n}^k} p^k q^{n−k}, \quad k = (n + d) / 2 </tex>, при обязательном условии <tex>k ∈ {0, 1, . . . , n}.</tex> (3)
+
*<tex> P(\xi_n = m + d) = {C_{n}^k} p^k q^{n−k}, \quad k = \frac{(n + d)}{2} </tex>, при обязательном условии <tex>k ∈ {0, 1, . . . , n}.</tex> (3)
  
Замечание. Ограничение <tex>0 <= k <= n </tex> по формуле (2) влечёт <tex>|d| <= n</tex>. Это
+
Замечание. Ограничение <tex>0 \leq k \leq n </tex> по формуле (2) влечёт <tex>|d| \leq n</tex>. Это
можно понять и без расчётов: если |d| > n, то частица «не успевает» дойти из начальной в конечную точку за n шагов, даже двигаясь строго в одном направлении
+
можно понять и без расчётов: если <tex>|d| > n</tex>, то частица «не успевает» дойти из начальной в конечную точку за n шагов, даже двигаясь строго в одном направлении
(налево при d < 0 и направо при d > 0). Ограничение на значения k согласовано
+
(налево при <tex>d < 0</tex> и направо при <tex>d > 0</tex>). Ограничение на значения <tex>k</tex> согласовано
и с (2.4): биномиальный коэффициент C
+
и с (3): биномиальный коэффициент <tex>{C_{n}^k}</tex> не определён при <tex> k /∈ {0, 1, . . . , n}</tex>. Мы
k
+
можем даже считать формулу (3) верной при любом k, если положим по определению C
n не определён при k /∈ {0, 1, . . . , n}. Мы
 
можем даже считать формулу (2.4) верной при любом k, если положим по определению C
 
 
k
 
k
 
n = 0 для k /∈ {0, 1, . . . , n}. Число шагов n и смещение d должны иметь как
 
n = 0 для k /∈ {0, 1, . . . , n}. Число шагов n и смещение d должны иметь как

Версия 14:14, 19 мая 2020

Определение

Определение:
Случайное блуждание (англ. Random walk) — математическая модель процесса случайных изменений — шагов в дискретные моменты времени. При этом предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса.


Случайные блуждания по прямой

Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку [math]k + 1[/math] и с положительной вероятностью [math]q = 1 − p[/math] перемещается в точку 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]

Заметим, что вернуться в какую-либо точку можно только за четное число шагов.

Вероятность смещения на d единиц вправо или влево

Выведем распределение случайной величины [math]\xi_n[/math]. Будем считать, что [math]P(\xi_0 = m) = 1[/math]. Это отвечает тому, что в начальный момент времени частица достоверно находилась в точке [math]x = m[/math] (здесь [math]m[/math] — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть [math]d[/math] — смещение частицы за [math]n[/math] шагов. Найдём [math]P(\xi_n = m + d)[/math] для каждого [math]d ∈ Z[/math].

Справедливо очевидное равенство:

  • [math]P(\xi_n = m + d) = P(\xi_n = m + d | \xi_0 = m)[/math], если [math]P(\xi_0 = m) = 1.[/math]

Представление через условную вероятность удобно, если нам необходимо явно указать, где находилась частица в начальный момент времени.

Наша физическая модель с математической точки зрения в точности отвечает схеме независимых испытаний Бернулли с двумя исходами —- прыжком вправо, который мы будем называть успехом, и прыжком вправо (неудачей). В рамках этой математической модели все вероятности рассчитываются на основании распределения Бернулли. Пусть частица сделала [math]n[/math] прыжков. Вероятность того, что среди этих прыжков будет ровно [math]k[/math] прыжков вправо (или, что то же самое, [math]n−k[/math] прыжков влево) задаётся формулой:

  • [math]P = {C_{n}^k} p^k q^{n−k}, k = 0, 1, . . . , n.[/math] (1)

Смещение частицы и число прыжков влево и вправо связаны простейшим уравнением

  • [math]d = 1 · k + (−1) · (n − k) = 2k − n \quad[/math] (2)

откуда [math]k = (n + d)/2[/math]. Понятно, что, поскольку частица сделала ровно n прыжков, число прыжков вправо должно быть целым числом в интервале [math][0, n][/math], другими словами, [math]P(\xi_n = m + d) = 0,[/math] если [math]k = (n + d)/2 ∈ \{ / 0, 1, . . . , n\}[/math]. Если же указанное ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли (1):

  • [math] P(\xi_n = m + d) = {C_{n}^k} p^k q^{n−k}, \quad k = \frac{(n + d)}{2} [/math], при обязательном условии [math]k ∈ {0, 1, . . . , n}.[/math] (3)

Замечание. Ограничение [math]0 \leq k \leq n [/math] по формуле (2) влечёт [math]|d| \leq n[/math]. Это можно понять и без расчётов: если [math]|d| \gt n[/math], то частица «не успевает» дойти из начальной в конечную точку за n шагов, даже двигаясь строго в одном направлении (налево при [math]d \lt 0[/math] и направо при [math]d \gt 0[/math]). Ограничение на значения [math]k[/math] согласовано и с (3): биномиальный коэффициент [math]{C_{n}^k}[/math] не определён при [math] k /∈ {0, 1, . . . , n}[/math]. Мы можем даже считать формулу (3) верной при любом k, если положим по определению C k n = 0 для k /∈ {0, 1, . . . , n}. Число шагов n и смещение d должны иметь как целые числа одну чётность. Вероятность (2.4) не зависит от начального положения m и определяется только числом шагов n (номером члена последовательности) и смещением d.

Примеры

Энтропия честной монеты

Рассмотрим вероятностное пространство — честная монета. Найдем для нее энтропию:

[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]

См. также

Источники информации