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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Вероятность смещения на d единиц вправо (влево))
Строка 19: Строка 19:
 
==Вероятность смещения на d единиц вправо (влево)==
 
==Вероятность смещения на d единиц вправо (влево)==
  
Выведем распределение случайной величины <tex>\xi_n</tex>. '''Кажется, это предложение можно выкинуть и ничего не изменится''' Будем считать, что <tex>P(\xi_0 = m) = 1</tex>. Это отвечает тому, '''переформулируй, пожалуйста, не очень корректный оборот''' что в начальный момент времени частица достоверно '''лишнее слово''' находилась в точке
+
Будем считать, что <tex>P(\xi_0 = m) = 1</tex>. Это соответствует тому, что в начальный момент времени частица находилась в точке
 
<tex>x = m</tex> (здесь <tex>m</tex> — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть <tex>d</tex> — смещение частицы за <tex>n</tex> шагов.
 
<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)</tex> для каждого <tex>d ∈ Z</tex>.
Строка 29: Строка 29:
  
 
Наша физическая модель с математической точки зрения в точности отвечает
 
Наша физическая модель с математической точки зрения в точности отвечает
схеме независимых испытаний Бернулли '''лучше сделать ссылку на конспекты, если в них это есть, или хотя бы на Википедию''' с двумя исходами —- прыжком вправо, который мы будем называть успехом, и прыжком '''лишнее определение, можно писать "перемещение" или "движение"''' вправо (неудачей). В рамках этой
+
схеме [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>n</tex> прыжков. Вероятность того, что среди
 
этих прыжков будет ровно <tex>k</tex> прыжков вправо (или, что то же самое, <tex>n−k</tex> прыжков
 
этих прыжков будет ровно <tex>k</tex> прыжков вправо (или, что то же самое, <tex>n−k</tex> прыжков
Строка 46: Строка 46:
  
 
Замечание. Ограничение <tex>0 \leq k \leq n </tex> по формуле (2) влечёт <tex>|d| \leq n</tex>. Это
 
Замечание. Ограничение <tex>0 \leq k \leq n </tex> по формуле (2) влечёт <tex>|d| \leq n</tex>. Это
можно понять и без расчётов: если <tex>|d| > n</tex>, то частица «не успевает» '''в научных текстах не должно быть ненаучных выражений в кавычках''' дойти из начальной в конечную точку за  
+
можно понять и без расчётов: если <tex>|d| > n</tex>, то частица не успевает дойти из начальной в конечную точку за  
 
<tex>n</tex> шагов, даже двигаясь строго в одном направлении
 
<tex>n</tex> шагов, даже двигаясь строго в одном направлении
 
(налево при <tex>d < 0</tex> и направо при <tex>d > 0</tex>). Ограничение на значения <tex>k</tex> согласовано
 
(налево при <tex>d < 0</tex> и направо при <tex>d > 0</tex>). Ограничение на значения <tex>k</tex> согласовано
Строка 55: Строка 55:
 
шагов <tex>n</tex> (номером члена последовательности)  
 
шагов <tex>n</tex> (номером члена последовательности)  
 
и смещением <tex>d</tex>.
 
и смещением <tex>d</tex>.
При своём движении частица случайным образом «выбирает» '''то же самое''' одну из возможных траекторий. Для перехода из точки  
+
При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки  
 
<tex>m</tex> в точку <tex>m</tex> за <tex>n</tex> шагов возможными являются все те и только те траектории длины  
 
<tex>m</tex> в точку <tex>m</tex> за <tex>n</tex> шагов возможными являются все те и только те траектории длины  
 
<tex>n</tex>, в которых ровно <tex>k</tex> смещений вправо и <tex>n − k</tex> смещений влево, где <tex>k = \frac{(n +  
 
<tex>n</tex>, в которых ровно <tex>k</tex> смещений вправо и <tex>n − k</tex> смещений влево, где <tex>k = \frac{(n +  

Версия 20:57, 2 июня 2020

Определение

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


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

Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку [math]k + 1[/math] и с положительной вероятностью [math]q = 1 − p[/math] перемещается в точку [math]k − 1[/math]. Физической системе соответствует цепь Маркова:

  • [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]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) (1) и (2) разным шрифтом. И такие собственные сноски тоже лучше делать кликабельными. Можно вынести их в отдельные разделы статьи

откуда [math]k = \frac{(n + d)}{2}[/math]. Понятно, что, поскольку частица сделала ровно n прыжков, Тех число прыжков вправо должно быть целым числом в интервале [math][0, n][/math], другими словами, [math]P(\xi_n = m + d) = 0,[/math] если [math]k = \frac{(n + d)}{2}, k \notin \{0, 1, . . . , n\}[/math]. Если же указанное ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли (1): вот тут хочется кликнуть на (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], то частица не успевает дойти из начальной в конечную точку за [math]n[/math] шагов, даже двигаясь строго в одном направлении (налево при [math]d \lt 0[/math] и направо при [math]d \gt 0[/math]). Ограничение на значения [math]k[/math] согласовано и с (3): биномиальный коэффициент [math]{C_{n}^k}[/math] не определён при [math] k \notin \{0, 1, . . . , n\}[/math]. Мы можем даже считать формулу (3) верной при любом [math]k[/math], если положим по определению[math]C_{n}^k = 0 [/math] для [math] k \notin \{0, 1, . . . , n\}[/math]. Число шагов [math]n[/math] и смещение [math]d[/math] должны иметь как целые числа одну чётность. Вероятность (3) не зависит от начального положения [math]m[/math] и определяется только числом шагов [math]n[/math] (номером члена последовательности) и смещением [math]d[/math]. При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки [math]m[/math] в точку [math]m[/math] за [math]n[/math] шагов возможными являются все те и только те траектории длины [math]n[/math], в которых ровно [math]k[/math] смещений вправо и [math]n − k[/math] смещений влево, где [math]k = \frac{(n + d)}{2}[/math]. Равенство (1) при этом можно интерпретировать так: вероятность того, что частица пройдет по одной из возможных траекторий, равна [math]p^k q^{n−k}[/math], и всего существуют [math]{C_{n}^k}[/math] таких траекторий, таким образом, [math]P = p^k*q^{n−k}+...+p^k*q^{n−k}={C_{n}^k} p^k q^{n−k}.[/math]

Хотелось бы чуть структурировать, выглядит, как стена текста. Оформить замечание в специальную сноску или в отдельный блок, выделить главное. Сейчас замечание выглядит важнее, чем факт, к которому оно приложено, а это не должно быть так

Задача о разорении игрока

Обсудим блуждание на примере задачи о разорении. Лишнее предложение Пусть начальный капитал [math]\xi_0[/math] первого игрока составляет [math]k[/math] рублей, а капитал второго игрока поставь теховское тире[math](n − k)[/math] рублей. Первый игрок выигрывает или проигрывает рубль с вероятностями [math]p[/math] и [math]q[/math] соответственно. Игра продолжается до тех пор, пока капитал первого игрока не уменьшится до нуля, либо не возрастет до [math]n[/math]. Поглощение точки в правом конце отрезка [math][0, n][/math] соответствует выигрышу первого игрока.

Рассмотрим конечную цепь Маркова:

[math]\quad\xi_{t+1} = \xi_t + \eta_t,\quad P\{\eta_t = 1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = p,\quad P\{\eta_t = −1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = q[/math] и

[math]\quad P\{\eta = 0|\xi_t = 0 ∨ \xi_t = n\} = 1. [/math] (2.1)

Вероятность выигрыша для первого игрока в момент времени [math]t[/math] есть [math]p_{kn}(t) = P\{\eta_t = n|\eta_0 = k\}[/math]

По формуле полной вероятности:

  • [math] \quad P\{\xi_{t+1} = n\} = P\{\xi_1 = k + 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k + 1\} + P\{\xi_{1} = k − 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k - 1\} [/math]

или

  • [math] \quad p_{kn}(t + 1) = p*p_{k+1,n}(t) + q*p_{k−1,n}(t), \quad k = 1, 2, . . . , n − 1.[/math]

в формулах следует писать не *, а \cdot

Заметим, что:

[math] \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . [/math] Это события? Не очень понятно, что ты имеешь ввиду

Положим [math]A =\cup_{t=1}^∞\{\xi_t = n\}[/math]. Тогда

[math] \quad \quad p_{kn} = P(A) = \lim_{t\to\infty}P\{\xi_t = n|\xi_0 = k\} = \lim_{t\to\infty}p_{kn}(t).[/math]

Переходя к пределу в (2.1) при [math]t → ∞[/math], получим

[math]\quad \quad p_{kn} = p*p_{k+1,n} + q*p_{k−1,n}[/math]

Так как [math]p_{kn}[/math] вероятность выигрыша для первого игрока, то [math]p_{0n} = 0, p_{nn} = 1[/math]. Рассматриваемая как функция от [math]k[/math], вероятность [math]p_{kn}[/math] является решением уравнения в конечных разностях

  • [math] \quad \quad p*f_{k+1} − f_{k} + q*f_{k−1} = 0 [/math] (2.2)

удовлетворяющим граничным условиям [math]f_0 = 0 \quad f_n = 1[/math]. Теория решения таких уравнений аналогична теории линейных уравнений с постоянными коэффициентами.

Пусть сначала [math]p ≠ q[/math]. Решение будем искать в виде [math]f_k = \lambda^k[/math], где [math]\lambda[/math] является корнем характеристического уравнения [math]p\lambda^2 − \lambda + q = 0[/math]. Корнями такого уравнения являются [math]\lambda_1 = 1, \lambda_2 = q/p[/math].

Значит, функции [math]\lambda_1^k[/math] и [math]\lambda_2^k[/math] удовлетворяют уравнению (2.2). Линейная комбинация

  • [math]\quad f_k = C_1λ^k_1 + C_2λ^k_2[/math] (2.3)

при любых [math]C_1[/math] и [math]C_2[/math] также является решением. Подставляя граничные условия в (2.3), при [math]k = 0[/math] и [math]k = n[/math] получим

[math]\quad C_1 + C_2 = 0, \quad C_1 + (q/p)^nC_2 = 1.[/math]

Отсюда и из (2.3) находим

  • [math]\quad p_{kn} = (1 − q/p)^k/(1 − (q/p)^n).[/math] Оформи дроби через \frac

Вероятности выигрыша первым игроком [math]p_{k0}[/math] тоже удовлетворяют уравнению (2.2). Но граничными условиями станут [math]f_0 = 1, f_n = 0.[/math] Определяя из этих условий [math]C_1[/math] и [math]C_2[/math], получим

[math]\quad p_{k0} = ((q/p)^k − (q/p)^n)/(1 − (q/p)^n).[/math]

Так как [math]p_{k0} + p_{kn} = 1[/math], то с вероятностью [math]1[/math] один из игроков выиграет.

Пусть теперь [math]p = q = 1/2[/math]. В этом случае [math]\lambda_1 = \lambda_2 = 1[/math] и решение уравнения (2.2) нужно искать в виде [math]f_k = C_1 + kC_2 .[/math]

С помощью граничных условий находим

[math]\quad p_{kn} = \frac{k}{n}, \quad p_{k0} = 1 − \frac{k}{n}.[/math]

В схеме блуждания по целым точкам с поглощением только в нуле вероятность события

[math]\quad A_n = \{\xi_t = 0[/math] в некоторый момент времени [math]t[/math], [math]\xi_t ∈ [0, n)[/math] во все моменты [math]t\}[/math] Лучше не писать текстом в математических объектах и не использовать математические объекты как сокращения в тексте. тут лучше ввести новую переменную и раскрыть её смысл вне системы равна

[math] \quad p_{k0} = \begin{cases} ((q/p)^k − (q/p)^n)/(1 − (q/p)^n), &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} \end{cases}[/math]

События [math]A_n[/math] вложены последовательно друг в друга

  • [math]\quad A_1 ⊂ A_2 ⊂ · · · ⊂ A_n ⊂ . . . ,[/math]

поэтому вероятность поглощения в нуле равна

  • [math]p_k = \lim_{n\to\infty}P(A) = \lim_{n\to\infty}p_{k0}=\begin{cases} (q/p)^k, &\text{если q меньше p}\\1, &\text{если q≥p} \end{cases}[/math]

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

Все источники нужно сделать кликабельными