Изменения

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

перемещается в точку <tex>k − 1</tex>. Физической системе соответствует [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C цепь Маркова]:

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

Выведем распределение случайной величины <tex>\xi_n</tex>. Будем считать, что <tex>P(\xi_0 = m) = 1</tex>. Это отвечает соответствует тому, что в начальный момент времени частица достоверно находилась в точке

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

схеме [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8#:~:text=%D0%A1%D1%85%D0%B5%D0%BC%D0%BE%D0%B9%20%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8%20(%D0%B0%D0%BD%D0%B3%D0%BB.,%2C%20%D0%B0%20%D0%BD%D0%B5%D1%83%D0%B4%D0%B0%D1%87%D0%B0%20%E2%80%94%20%D1%81%20%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E%20 независимых испытаний Бернулли ] с двумя исходами —- прыжком движением вправо, который мы будем называть успехом, и прыжком движением вправо (неудачей). В рамках этойматематической модели все вероятности рассчитываются на основании распределения Бернулли. Пусть частица сделала <tex>n</tex> прыжков. Вероятность того, что среди

*<tex>P = {C_{n}^k} p^k q^{n−k}, \quad k = 0, 1, . . . , n.</tex> (1)

Смещение частицы и число прыжков влево и вправо связаны простейшим уравнением*<tex>d = 1 · k + (−1) · (n − k) = 2k − n \quad</tex> (2)

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

*<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 dpi="140">H(X1) = -</tex> Ограничение <tex>0 \sumleq k \limits_{i=1}^{leq n} p_i \log_2p_i = -\sum\limits_{i</tex> по формуле <tex>d =1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot · k + (−1) · (-1n − k)} = 12k − n</tex> влечёт <tex>|d| \leq n</tex>. Это означает что после броска честной монеты мы получим информацию можно понять и без расчётов: если <tex>|d| > n</tex>, то частица не успевает дойти из начальной в размере конечную точку за <tex>1n</tex> бит, уменьшив степень неопределенности вдвоешагов.

=== Энтропия нечестной монеты ===<tex>2)</tex> При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки <tex>m</tex> в точку <tex>m</tex> за <tex>n</tex> шагов возможными являются все те и только те траектории длины Найдем энтропию для [[Вероятностное пространство<tex>n</tex>, элементарный исходв которых ровно <tex>k</tex> смещений вправо и <tex>n − k</tex> смещений влево, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] где <tex>k = \frac{(n + d)}{0,2; 0,8\}</tex>. Равенство <tex>P = {C_{n}^k} p^k q^{n−k}</tex> при этом можно интерпретировать так:вероятность того, что частица пройдет по одной из :возможных траекторий, равна <tex dpi="140">H(X) = -\sum\limits_p^k q^{i=1n−k}^</tex>, и всего существуют <tex>{C_{n} p_i \log_2p_i ^k}</tex> таких траекторий, таким образом, *<tex>P = -0.2p^k \log_2(0cdot q^{n−k}+.2)-0.8\log_2(0.8) +p^k \approx 0cdot q^{n−k}={C_{n}^k} p^k q^{n−k}.722 < 1 </tex>

== Ограниченность энтропии Случайные блуждания по прямой == Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точкив другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку <tex>k + 1</tex> и с положительной вероятностью <tex>q = 1 − p</tex>перемещается в точку <tex>k − 1</tex>.Физической системе соответствует [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C цепь Маркова]: *<tex>\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{Теоремаcases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p} \end{cases}</tex> |statementЗаметим, что вернуться в какую-либо точку можно только за четное число шагов. == Задача о разорении игрока == Пусть начальный капитал <tex>0 \leqslant Hxi_0</tex> первогоигрока составляет <tex>k</tex> рублей, а капитал второго игрока <tex> – (p_1n − k)</tex> рублей. Первый игрок выигрываетили проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex> соответственно. Игра продолжается до тех пор, p_2покакапитал первого игрока не уменьшится до нуля, либо не возрастет до <tex>n</tex>. Поглощение точки в правомконце отрезка <tex>[0, n]</tex> соответствует выигрышу первого игрока. Рассмотрим конечную цепь Маркова: <tex>\dotsquad\xi_{t+1} = \xi_t + \eta_t, p_n\quad P\{\eta_t = 1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = p,\quad P\{\eta_t = −1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = q</tex> и  <tex>\quad P\{\eta = 0|\xi_t = 0 ∨ \xi_t = n\} = 1. </tex> <tex>(2.1) </tex> Вероятность выигрыша для первого игрока в момент времени <tex>t</tex> есть <tex>p_{kn}(t) = P\leqslant {\eta_t = n|\eta_0 = k\log_2n }</tex> По формуле полной вероятности: *<tex> \quad P\{\xi_{t+1} = n\} = P\{\xi_1 = k + 1|\xi_0 = k\}P\{\xi_{t+1} = n|proof \xi_{1} =k + 1\} + P\{\xi_{1) Докажем первую часть неравенства:} = k − 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k - 1\} </tex> или

Так как *<tex> p_i\in[0,\;quad p_{kn}(t + 1]</tex>, тогда <tex dpi) ="140">\log_2p \dfraccdot p_{k+1,n}(t) + q \cdot p_{p_ik−1,n} (t), \geqslant 0 </tex>. Таким образом <tex dpiquad k ="140"> H(p_11, p_22, \dots. . . , p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{− 1}{p_i} \geqslant 0 .</tex>

2) Докажем вторую часть неравенстваТеорему о предельных вероятностях применить не можем, но заметим, что:

<tex dpi> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 ="140"> f(x)n\} ⊂ · · · ⊂ \{\xi_t =n\log_2x } ⊂ . . . </tex> {{---}} выпуклая вверх функция,  Положим <tex> p_1,p_2,A =\cup_{t=1}^∞\{\xi_t = n\ldots,p_n>0}</tex> и . Тогда <tex> \sum quad \limits_quad p_{ikn} =1P(A) = \lim_{t\to\infty}^P\{\xi_t = n|\xi_0 = k\} p_i = \lim_{t\to\infty}p_{kn}(t).</tex> Переходя к пределу в <tex>(2.1 )</tex> при <tex>t → ∞</tex>, тогда для нее выполняется неравенство Йенсена:получим <tex dpi="140"> \sumquad \limits_quad p_{ikn} =p \cdot p_{k+1,n}^+ q \cdot p_{k−1,n} p_i f(\dfrac</tex> Так как <tex>p_{kn}</tex> вероятность выигрыша для первого игрока, то <tex>p_{0n} = 0, p_{nn} = 1}</tex>. Рассматриваемая как функция от <tex>k</tex>, вероятность <tex>p_{p_ikn}) </tex> является решением уравнения в конечных разностях *<tex> \leqslant f(quad \sumquad p \limits_cdot f_{i=k+1}^− f_{nk} (p_i + q \cdot\dfracf_{1k−1}{p_i})= 0 </tex> <tex>(2.2) </tex>Таким образом получаем, что удовлетворяющим граничным условиям <tex> H(p_1, p_2, f_0 = 0 \dots, p_n) \leqslant \log_2n quad f_n = 1</tex>. Теория решения таких уравнений аналогичнатеории линейных уравнений с постоянными коэффициентами.}}Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятныПусть сначала <tex>p ≠ q</tex>.Решение будем искать в виде <tex>f_k =\lambda^k</tex>, где <tex>\lambda</tex> является корнем характеристического уравнения <tex>p\lambda^2 − \lambda + q = Условная и взаимная энтропия 0</tex>. Корнями такого уравнения являются <tex>\lambda_1 =1, \lambda_2 =\frac{q}{Определениеp}</tex>. |definition = '''Условная энтропия''' Значит, функции <tex>\lambda_1^k</tex> и <tex>\lambda_2^k</tex> удовлетворяют уравнению <tex>(англ2. ''conditional entropy''2) {{---}} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события </tex>. Линейная комбинация *<tex>\quad f_k = C_1λ^k_1 + C_2λ^k_2</tex>  при любых <tex>AC_1</tex> после того, как становится известным результат события и <tex>BC_2</tex>также является решением. Она называется ''энтропия Подставляя граничные условия в <tex>Af_k = C_1λ^k_1 + C_2λ^k_2</tex> , при условии <tex>Bk = 0</tex>'', и обозначается <tex>H(A|B)k = n</tex>получим}} <tex>H(A|B)\quad C_1 + C_2 = - 0, \sumquad C_1 + (\limits_frac{q}{ip})^nC_2 =1}.</tex> Отсюда и из <tex>f_k = C_1λ^k_1 + C_2λ^k_2</tex> находим *<tex>\quad p_{mkn}p(b_i)\sum= \limits_frac{j=(1− q/p)^k}^{n} (1 − (q/p(a_j|b_i)\log_2p(a_j|b_i^n) }.</tex> Вероятности выигрыша первым игроком <tex>p_{{Определениеk0}</tex> тоже удовлетворяют уравнению <tex>(2.2)</tex>. Но граничными|definition условиями станут <tex>f_0 = 1, f_n = '''Взаимная энтропия''' (англ0. ''joint entropy'') {{---}} энтропия объединения двух событий </tex> Определяя из этих условий <tex>AC_1</tex> и <tex>BC_2</tex>. , получим}}<tex> H(A \cap B) quad p_{k0} = -\sum\limits_frac{i=1}((q/p)^k − (q/p)^{mn)} \sum\limits_{j=(1}− (q/p)^{n)} p(a_j \cap b_i)\log_2p(a_j \cap b_i) .</tex> Так как <tex>p_{k0} + p_{Утверждениеkn} = 1</tex>, то с вероятностью <tex>1</tex> один из игроков выиграет. |statementПусть теперь <tex>p = q = 0.5</tex>. В этом случае <tex> H(A \cap B) lambda_1 = \lambda_2 = H1</tex> и решение уравнения <tex>(A|B)+H(B2.2)</tex> нужно искать в виде <tex>f_k =H(B|A)C_1 +H(A) kC_2 .</tex>|proof= По формуле условной вероятности С помощью граничных условий находим <tex dpi="130"> p(a_j|b_i)\quad p_{kn} =\dfracfrac{p(a_j k}{n}, \quad p_{k0} = 1 − \cap b_i)frac{k}{p(b_i)n} .</tex>

<tex dpi="140"> = H(A \cap B) +\sum\limits_{iquad A_n =1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A exists t : \cap B) +quad \sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) xi_t = 0 </tex>, <tex dpi="140">H(A \cap B) - H(Bquad \forall t: \quad \xi_t ∈ [0, n) \}</tex>равна

Таким образом получаем, что: <tex> H\quad p_{k0} = \begin{cases} \frac{((A \cap Bq/p)= H^k − (A|Bq/p)+H^n)}{(B1 − (q/p) ^n)}, &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} \end{cases}</tex>

Аналогично: События <tex>A_n</tex> вложены последовательно друг в друга*<tex>H(B \cap A)= H(B|A)+H(A) quad A_1 ⊂ A_2 ⊂ · · · ⊂ A_n ⊂ . . . ,</tex>

*<tex>p_k =\lim_{n\to\infty}P(A) = См. также =\lim_{n\to\infty}p_{k0}=*[[Вероятностное пространство\begin{cases} (\frac{q}{p})^k, элементарный исход &\text{если q меньше p}\\1, событие|Вероятностное пространство, элементарный исход, событие]]&\text{если q≥p}*[[Условная вероятность|Условная вероятность]] \end{cases}</tex>

[[Категория: Теория вероятности ]]