Участник:Mk17.ru — различия между версиями
(→Вероятность смещения на d единиц вправо (влево)) |
(→Вероятность смещения на d единиц вправо (влево)) |
||
(не показано 12 промежуточных версий этого же участника) | |||
Строка 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 независимых испытаний Бернулли] с двумя исходами —- движением вправо, который мы будем называть успехом, и движением вправо (неудачей). | + | схеме [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>k</tex> прыжков вправо (или, что то же самое, <tex>n−k</tex> прыжков | ||
влево) задаётся формулой: | влево) задаётся формулой: | ||
− | *<tex>P = {C_{n}^k} p^k q^{n−k}, k = 0, 1, . . . , n</tex> | + | *<tex>P = {C_{n}^k} p^k q^{n−k}, \quad k = 0, 1, . . . , n </tex> |
− | Смещение частицы и число прыжков влево и вправо связаны | + | Смещение частицы и число прыжков влево и вправо связаны уравнением |
− | *<tex>d = 1 · k + (−1) · (n − k) = 2k − n \quad</tex> | + | *<tex>d = 1 · k + (−1) · (n − k) = 2k − n \quad</tex> |
− | откуда <tex>k = \frac{(n + d)}{2}</tex>. Понятно, что, поскольку частица сделала ровно n прыжков, | + | откуда <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>. Если же указанное | число прыжков вправо должно быть целым числом в интервале <tex>[0, n]</tex>, другими словами, <tex>P(\xi_n = m + d) = 0,</tex> если <tex>k = \frac{(n + d)}{2}, k \notin \{0, 1, . . . , n\}</tex>. Если же указанное | ||
− | ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли | + | ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли <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> | + | *<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> |
− | + | ||
− | можно понять и без расчётов: если <tex>|d| > n</tex>, то частица не успевает дойти из начальной в конечную точку за | + | '''Замечания'''. |
− | <tex>n</tex> шагов | + | |
− | + | <tex>1)</tex> Ограничение <tex>0 \leq k \leq n </tex> по формуле <tex>d = 1 · k + (−1) · (n − k) = 2k − n</tex> влечёт <tex>|d| \leq n</tex>. Это можно понять и без расчётов: если <tex>|d| > n</tex>, то частица не успевает дойти из начальной в конечную точку за <tex>n</tex> шагов. | |
− | + | ||
− | + | <tex>2)</tex> При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки | |
− | <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 + | ||
− | d)}{2}</tex>. Равенство | + | d)}{2}</tex>. Равенство <tex>P = {C_{n}^k} p^k q^{n−k}</tex> при этом можно интерпретировать так: вероятность того, что частица пройдет по одной из |
− | возможных траекторий, равна <tex>p^k q^{n−k}</tex>, и всего существуют <tex>{C_{n}^k}</tex> таких траекторий, таким образом, <tex>P = p^k | + | возможных траекторий, равна <tex>p^k q^{n−k}</tex>, и всего существуют <tex>{C_{n}^k}</tex> таких траекторий, таким |
− | + | образом, | |
− | + | *<tex>P = p^k \cdot q^{n−k}+...+p^k \cdot q^{n−k}={C_{n}^k} p^k q^{n−k}.</tex> | |
== Задача о разорении игрока == | == Задача о разорении игрока == | ||
− | + | Пусть начальный капитал <tex>\xi_0</tex> первого | |
− | игрока составляет <tex>k</tex> рублей, а капитал второго игрока | + | игрока составляет <tex>k</tex> рублей, а капитал второго игрока <tex> – (n − k)</tex> рублей. Первый игрок выигрывает |
или проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex> соответственно. Игра продолжается до тех пор, пока | или проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex> соответственно. Игра продолжается до тех пор, пока | ||
капитал первого игрока не уменьшится до нуля, либо не возрастет до <tex>n</tex>. Поглощение точки в правом | капитал первого игрока не уменьшится до нуля, либо не возрастет до <tex>n</tex>. Поглощение точки в правом | ||
Строка 87: | Строка 81: | ||
*<tex> \quad p_{kn}(t + 1) = p \cdot p_{k+1,n}(t) + q \cdot p_{k−1,n}(t), \quad k = 1, 2, . . . , n − 1.</tex> | *<tex> \quad p_{kn}(t + 1) = p \cdot p_{k+1,n}(t) + q \cdot p_{k−1,n}(t), \quad k = 1, 2, . . . , n − 1.</tex> | ||
− | + | Теорему о предельных вероятностях применить не можем, но заметим, что: | |
− | <tex> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . </tex> | + | <tex> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . </tex> |
Положим <tex>A =\cup_{t=1}^∞\{\xi_t = n\}</tex>. Тогда | Положим <tex>A =\cup_{t=1}^∞\{\xi_t = n\}</tex>. Тогда | ||
Строка 106: | Строка 100: | ||
теории линейных уравнений с постоянными коэффициентами. | теории линейных уравнений с постоянными коэффициентами. | ||
− | Пусть сначала <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 = q | + | Пусть сначала <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>. |
Значит, функции <tex>\lambda_1^k</tex> и <tex>\lambda_2^k</tex> удовлетворяют уравнению (2.2). Линейная комбинация | Значит, функции <tex>\lambda_1^k</tex> и <tex>\lambda_2^k</tex> удовлетворяют уравнению (2.2). Линейная комбинация | ||
Строка 114: | Строка 108: | ||
при любых <tex>C_1</tex> и <tex>C_2</tex> также является решением. Подставляя граничные условия в (2.3), при <tex>k = 0</tex> и <tex>k = n</tex> получим | при любых <tex>C_1</tex> и <tex>C_2</tex> также является решением. Подставляя граничные условия в (2.3), при <tex>k = 0</tex> и <tex>k = n</tex> получим | ||
− | <tex>\quad C_1 + C_2 = 0, \quad C_1 + (q | + | <tex>\quad C_1 + C_2 = 0, \quad C_1 + (\frac{q}{p})^nC_2 = 1.</tex> |
Отсюда и из (2.3) находим | Отсюда и из (2.3) находим | ||
Строка 127: | Строка 121: | ||
Так как <tex>p_{k0} + p_{kn} = 1</tex>, то с вероятностью <tex>1</tex> один из игроков выиграет. | Так как <tex>p_{k0} + p_{kn} = 1</tex>, то с вероятностью <tex>1</tex> один из игроков выиграет. | ||
− | Пусть теперь <tex>p = q = | + | Пусть теперь <tex>p = q = 0.5</tex>. В этом случае <tex>\lambda_1 = \lambda_2 = 1</tex> и решение уравнения (2.2) нужно искать в виде <tex>f_k = C_1 + kC_2 .</tex> |
С помощью граничных условий находим | С помощью граничных условий находим | ||
Строка 135: | Строка 129: | ||
В схеме блуждания по целым точкам с поглощением только в нуле вероятность события | В схеме блуждания по целым точкам с поглощением только в нуле вероятность события | ||
− | <tex>\quad A_n = \{\xi_t = 0</tex> | + | <tex>\quad A_n = \{\exists t : \quad \xi_t = 0 </tex>, <tex>\quad \forall t: \quad \xi_t ∈ [0, n)\}</tex> равна |
− | равна | ||
<tex> \quad p_{k0} = \begin{cases} \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)}, &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} | <tex> \quad p_{k0} = \begin{cases} \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)}, &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} |
Версия 00:13, 7 июня 2020
Содержание
Определение
Определение: |
Случайное блуждание (англ. Random walk) — математическая модель процесса случайных изменений — шагов в дискретные моменты времени, предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса. |
Случайные блуждания по прямой
Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку цепь Маркова:
и с положительной вероятностью перемещается в точку . Физической системе соответствуетЗаметим, что вернуться в какую-либо точку можно только за четное число шагов.
Вероятность смещения на d единиц вправо (влево)
Будем считать, что
. Это соответствует тому, что в начальный момент времени частица находилась в точке (здесь — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть — смещение частицы за шагов. Найдём для каждого .Справедливо равенство:
- , если
Представление через условную вероятность удобно, если нам необходимо явно указать, где находилась частица в начальный момент времени.
Наша физическая модель с математической точки зрения в точности отвечает схеме независимых испытаний Бернулли с двумя исходами —- движением вправо, который мы будем называть успехом, и движением вправо (неудачей). Пусть частица сделала прыжков. Вероятность того, что среди этих прыжков будет ровно прыжков вправо (или, что то же самое, прыжков влево) задаётся формулой:
Смещение частицы и число прыжков влево и вправо связаны уравнением
откуда
. Понятно, что, поскольку частица сделала ровно прыжков, число прыжков вправо должно быть целым числом в интервале , другими словами, если . Если же указанное ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли :- , при обязательном условии
Замечания.
Ограничение по формуле влечёт . Это можно понять и без расчётов: если , то частица не успевает дойти из начальной в конечную точку за шагов.
При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки в точку за шагов возможными являются все те и только те траектории длины , в которых ровно смещений вправо и смещений влево, где . Равенство при этом можно интерпретировать так: вероятность того, что частица пройдет по одной из возможных траекторий, равна , и всего существуют таких траекторий, таким образом,
Задача о разорении игрока
Пусть начальный капитал
первого игрока составляет рублей, а капитал второго игрока рублей. Первый игрок выигрывает или проигрывает рубль с вероятностями и соответственно. Игра продолжается до тех пор, пока капитал первого игрока не уменьшится до нуля, либо не возрастет до . Поглощение точки в правом конце отрезка соответствует выигрышу первого игрока.Рассмотрим конечную цепь Маркова:
и
(2.1)
Вероятность выигрыша для первого игрока в момент времени
естьПо формуле полной вероятности:
или
Теорему о предельных вероятностях применить не можем, но заметим, что:
Положим
. Тогда
Переходя к пределу в (2.1) при
, получим
Так как
вероятность выигрыша для первого игрока, то . Рассматриваемая как функция от , вероятность является решением уравнения в конечных разностях- (2.2)
удовлетворяющим граничным условиям
. Теория решения таких уравнений аналогична теории линейных уравнений с постоянными коэффициентами.Пусть сначала
. Решение будем искать в виде , где является корнем характеристического уравнения . Корнями такого уравнения являются .Значит, функции
и удовлетворяют уравнению (2.2). Линейная комбинация- (2.3)
при любых
и также является решением. Подставляя граничные условия в (2.3), при и получим
Отсюда и из (2.3) находим
Вероятности выигрыша первым игроком
тоже удовлетворяют уравнению (2.2). Но граничными условиями станут Определяя из этих условий и , получим
Так как
, то с вероятностью один из игроков выиграет.Пусть теперь
. В этом случае и решение уравнения (2.2) нужно искать в видеС помощью граничных условий находим
В схеме блуждания по целым точкам с поглощением только в нуле вероятность события
, равна
События
вложены последовательно друг в другапоэтому вероятность поглощения в нуле равна
Источники информации
Все источники нужно сделать кликабельными