Изменения
→Вероятность смещения на d единиц вправо (влево)
{{Определение
|definition = '''Случайное блуждание''' (англ. ''Random walk'') {{---}} математическая модель процесса случайных изменений — шагов в дискретные моменты времени. При этом , предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса.
}}
Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки
в другую происходит через равные промежутки времени. За один шаг частица из точки 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}
Заметим, что вернуться в какую-либо точку можно только за четное число шагов.
==Вероятность смещения на d единиц вправо или (влево)==
<tex>x = m</tex> (здесь <tex>m</tex> — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть <tex>d</tex> — смещение частицы за <tex>n</tex> шагов.
Найдём <tex>P(\xi_n = m + d)</tex> для каждого <tex>d ∈ Z</tex>.
Справедливо очевидное равенство:
*<tex>P(\xi_n = m + d) = P(\xi_n = m + d | \xi_0 = m)</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>k</tex> прыжков вправо (или, что то же самое, <tex>n−k</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>\xi_0</tex> первого|statement= игрока составляет <tex>k</tex> рублей, а капитал второго игрока <tex>0 \leqslant H– (p_1n − k)</tex> рублей. Первый игрок выигрываетили проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex> соответственно. Игра продолжается до тех пор, p_2покакапитал первого игрока не уменьшится до нуля, \dotsлибо не возрастет до <tex>n</tex>. Поглощение точки в правомконце отрезка <tex>[0, p_n) \leqslant \log_2n n]</tex>|proof =1) Докажем первую часть неравенства:соответствует выигрышу первого игрока.
<tex dpi>\quad P\{\eta ="140"> f(x)0|\xi_t = 0 ∨ \xi_t =n\log_2x } = 1. </tex> {{---}} выпуклая вверх функция, (2.1) Вероятность выигрыша для первого игрока в момент времени <tex> p_1,p_2,\ldots,p_n>0t</tex> и есть <tex> p_{kn}(t) = P\sum {\limits_{ieta_t =1}^{n|\eta_0 = k\} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена По формуле полной вероятности: *<tex dpi="140"> \sumquad P\{\limits_xi_{i=t+1}^{= n\} p_i f(= P\dfrac{\xi_1 = k + 1|\xi_0 = k\}P\{\xi_{p_it+1}) = n|\xi_{1} = k + 1\leqslant f(} + P\sum{\limits_xi_{i1} =k − 1|\xi_0 = k\}^P\{\xi_{t+1} = n} (p_i \cdot|\dfracxi_{1}{p_i= k - 1\})) </tex>Таким образом получаем, что или *<tex> H\quad p_{kn}(p_1, p_2t + 1) = p \cdot p_{k+1, n}(t) + q \dotscdot p_{k−1, p_nn}(t) , \leqslant \log_2n quad k = 1, 2, . . . , n − 1.</tex>}}Тогда из теоремы и доказанной выше леммы следуетТеорему о предельных вероятностях применить не можем, но заметим, что для : <tex> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n исходов энтропия максимальна, если они все равновероятны\} ⊂ . . .</tex> Положим <tex>A =\cup_{t= Условная и взаимная энтропия =1}^∞\{\xi_t =n\}</tex>. Тогда <tex> \quad \quad p_{{Определение|definition kn} = '''Условная энтропия''' P(англ. ''conditional entropy''A) = \lim_{t\to\infty}P\{\xi_t = n|\xi_0 = k\} = \lim_{---t\to\infty}p_{kn} определяет количество остающейся энтропии (то есть, остающейся неопределенностиt) события .</tex>A Переходя к пределу в (2.1) при <tex>t → ∞</tex> после того, получим <tex>\quad \quad p_{kn} = p \cdot p_{k+1,n} + q \cdot p_{k−1,n}</tex> Так как становится известным результат события <tex>Bp_{kn}</tex>. Она называется ''энтропия вероятность выигрыша для первого игрока, то <tex>Ap_{0n} = 0, p_{nn} = 1</tex> при условии . Рассматриваемая как функция от <tex>Bk</tex>'', и обозначается вероятность <tex>H(A|B)p_{kn}</tex>является решением уравнения в конечных разностях *<tex> \quad \quad p \cdot f_{k+1} − f_{k}+ q \cdot f_{k−1} = 0 </tex>H(A|B2.2) удовлетворяющим граничным условиям <tex>f_0 = - \sum0 \limits_{iquad f_n =1}</tex>. Теория решения таких уравнений аналогичнатеории линейных уравнений с постоянными коэффициентами. Пусть сначала <tex>p ≠ q</tex>. Решение будем искать в виде <tex>f_k = \lambda^{m}k</tex>, где <tex>\lambda</tex> является корнем характеристического уравнения <tex>p(b_i)\sumlambda^2 − \limits_{jlambda + q = 0</tex>. Корнями такого уравнения являются <tex>\lambda_1 =1, \lambda_2 = \frac{q}^{np} p</tex>. Значит, функции <tex>\lambda_1^k</tex> и <tex>\lambda_2^k</tex> удовлетворяют уравнению (a_j|b_i2.2). Линейная комбинация *<tex>\log_2pquad f_k = C_1λ^k_1 + C_2λ^k_2</tex> (a_j|b_i2.3) при любых <tex>C_1</tex> и <tex>C_2</tex>{{Определение|definition = '''Взаимная энтропия''' также является решением. Подставляя граничные условия в (англ2. ''joint entropy''3) {{---}} энтропия объединения двух событий , при <tex>Ak = 0</tex> и <tex>Bk = n</tex>. получим}}<tex> H(A \cap B) quad C_1 + C_2 = -0, \sumquad C_1 + (\limits_frac{q}{ip})^nC_2 =1}^.</tex> Отсюда и из (2.3) находим *<tex>\quad p_{mkn} = \sum\limits_frac{j=(1− q/p)^k}^{n} (1 − (q/p(a_j \cap b_i)\log_2p(a_j \cap b_i^n) }.</tex> Вероятности выигрыша первым игроком <tex>p_{{Утверждениеk0}</tex> тоже удовлетворяют уравнению (2.2). Но граничными|statementусловиями станут <tex>f_0 = 1, f_n = 0.</tex> Определяя из этих условий <tex>C_1</tex> и <tex>C_2</tex>, получим <tex> H(A \cap B) quad p_{k0} = H\frac{(A|B(q/p)+H^k − (Bq/p)^n)=H}{(1 − (B|Aq/p)^n)}.</tex> Так как <tex>p_{k0} +H(A) p_{kn} = 1</tex>, то с вероятностью <tex>1</tex>один из игроков выиграет.|proofПусть теперь <tex>p = q = По формуле условной вероятности 0.5</tex>. В этом случае <tex dpi>\lambda_1 = \lambda_2 ="130"1</tex> pи решение уравнения (a_j|b_i2.2)нужно искать в виде <tex>f_k = C_1 + kC_2 .</tex> С помощью граничных условий находим <tex>\quad p_{kn} =\dfracfrac{k}{n}, \quad p_{p(a_j 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>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>
== Источники информации ==
* [https://en.wikipedia.org/wiki/Random_walk "Википедия - Random_walk"]
* [https://www.youtube.com/watch?v=6wUD_gp5WeE "Лекция MIT Random Walks"]
* [http://math.csu.ru/new_files/students/lectures/teor_slych_proc/solovev_teor_slych_proc.pdf Конспект лекций по теории случайных процессов А.А. Соловьев]
* [https://cmp.phys.msu.ru/sites/default/files/02_RandomWalks.pdf Случайные блуждания по прямой]
*[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D0%BE%D1%80%D0%B5%D0%BD%D0%B8%D0%B8_%D0%B8%D0%B3%D1%80%D0%BE%D0%BA%D0%B0 "Задача о разорении игрока"]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности ]]