Случайные блуждания (Феллер теория вероятности)

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

Обычно рассматривается случайное блуждание, порождаемое суммами взаимно независимых одинаково распределённых величин X₁, X₂, ..., X_n или цепями Маркова.
Пусть S₀=0, S_n= X₁ + X₂ + ... + X_n, тогда последовательность координат (n, S_n), n=0, 1, 2, ..., описывает траекторию случайного блуждания.

Основные черты общих случайных блужданий можно охарактеризовать на примере простейшего случайного блуждания, порождаемого схемой испытаний Бернулли. Описание случайного блуждания принято в терминах частицы, которая движется по точкам вида k (k - целое) оси x. Движение начинается в момент t = 0, и положение частицы меняется только в дискретные моменты времени 0, 1, 2, ... На каждом шаге координата частицы увеличивается или уменьшается на величину 1 с вероятностями p и q = p-1, соответственно, независимо от предшествующего движения.

Обычно случайные блуждания изображают геометрически, беря ось t за ось абсцисс, а ось x - за ось ординат. Пусть X_j - случайная величина, равная величине перемещения частицы на j-м шаге, т. е. X₁ = 1 с вероятностью p и X₁ = -1 с вероятностью q. Тогда X₁, X₂, ..., X_n, ... образуют последовательность независимых бернуллиевских случайных величин (схема Бернулли).

Пьяница стоит на расстоянии одного шага от края пропасти. Он шагает случайным образом либо к краю утеса либо от него. На каждом шагу вероятность отойти от края равна 2/3, а шаг к краю имеет вероятность 1/3. Каковы шансы пьяницы избежать падения?

Координата блуждающей частицы в момент n равна сумме S_n= X₁ + X₂ + ... + X_n. Можно по аналогии определить случайные блуждания по точкам вида kh (h > 0) такое, что координата частицы увеличивается или уменьшается на величину h в дискретные моменты времени 0, ∆t, 2∆t, ... (∆t > 0). График такого случайного блуждания даёт наглядное представление о поведении нарастающих сумм случайных величин, причём многие характерные закономерности сохраняются и для сумм значительно более общих случайных величин. Классическая интерпретация таких процессов - это изменение капитала одного из игроков в задаче о разорении.

Обычно случайное блуждание, как одномерное, так и его многомерное обобщение, используют для приближённого описания процессов диффузии и броуновского движения частиц. Случайное блуждание является примером марковского процесса, и во многих случаях могут быть описаны как цепи Маркова или ветвящиеся процессы. Однако при их анализе возникает ряд специфических задач, например: распределение максимума последовательности сумм, распределение первого момента достижения некоторой точки, возвращение траектории в начало координат. Пусть движение начинается из нуля (при h = 1, ∆t = 1). Тогда вероятность хотя бы одного возвращения в нуль равна 1 при p = q =1/2 (симметричный случай) и меньше 1 при p ≠ q. При p > q или p < q частица уходит с вероятностью 1 в +∞ или -∞ соответственно. В симметричном случае время до N-го возвращения в нуль растёт как N², а среднее число возвращений за 2n шагов растёт как √n. Отсюда можно сделать парадоксальный вывод: при p = q =1/2 промежутки между последовательными возвращениями в нуль оказываются поразительно длинными. Кроме того, значения доли времени, которое траектория проводит выше оси абсцисс, близкие к 1/2, оказываются наименее вероятными. Точное утверждение даётся так называемым законом арксинуса.

Часто рассматривают случайные блуждания с отражающими или поглощающими границами. Наличие в точке поглощающего экрана проявляется в том, что по достижении этой точки частица перестаёт двигаться. При наличии в точке k + 1/2 отражающего экрана частица с вероятностью q переходит из k в k - 1 и с вероятностью p = 1 - q остаётся на месте. Основным средством вычисления вероятностей поглощения и достижения тех или иных точек служат разностные уравнения. Предельным переходом случайное блуждание сводится к процессам диффузии. Пусть, например, p = q = 1/2, ∆t = 1/N, h = 1/√N, тогда при N → ∞ многие вероятности, вычисленные в схеме случайного блуждания, стремятся к аналогичным вероятностям для процесса броуновского движения. Для более полного описания предельных соотношений необходимо совершить переход от дискретного процесса нарастающих сумм к непрерывному случайному процессу (см. Винеровский процесс).

Схема случайных блужданий оказывается очень удобной для наглядного объяснения общих закономерностей поведения сумм случайных величин. Случайные блуждания возникают как в теоретических задачах, так и в приложениях теории вероятностей, таких, например, как последовательный статистический анализ или теория массового обслуживания.

Постановка задачи
Пьяница стоит на расстоянии одного шага от края пропасти. Он шагает случайным образом либо к краю утеса либо от него. На каждом шагу вероятность отойти от края равна 2/3, а шаг к краю имеет вероятность 1/3. Каковы шансы пьяницы избежать падения?
 
Решение задачи
Перед решением задачи полезно задуматься о возможном ответе. Посмотрим, что может случиться на нескольких первых шагах. Схема на рисунке 35.1 иллюстрирует тот факт, что человек может упасть вниз только через нечетное число шагов. После одного шага вероятность упасть вниз равна 1/3 (рис. 35.1). Путь 1 → 2 → 1 → 0 добавляет еще 2/27 к вероятности падения, давая общую вероятность несчастья 11/27. После пяти шагов пути 1 → 2 → 1 → 2 → 1 → 0 и 1 → 2 → 3 → 2 → 1 → 0 вместе добавляют 8/243 к вероятности падения, давая общий результат 107/243. Этот список можно продолжить, но мы обратимся теперь к иному подходу.

Настоящая задача о блуждании весьма популярна и имеет много формулировок. Далее мы будем трактовать ее как задачу о частице, движущейся по оси.

Рассмотрим частицу, которая сначала находится в положении x = 1 на оси. Структура задачи будет яснее, если вероятность шага направо вместо 2/3 будет равна p. Частица движется из положения 1 либо в точку x = 2 с вероятностью p, либо в точку x = 0 с вероятностью 1 - p (рис. 35.2). Вообще, если частица находится в положении x = n, n > 0, n - целое число, то она сдвигается либо в точку x = n + 1 с вероятностью p, либо в точку x = n - 1 с вероятностью 1 - p. Если частица попадает в положение x = 0, то там она поглощается (не делает других шагов). Нас интересует значение вероятности P₁ того, что частица поглощается в точке x = 0, если она выходит из точки x = 1. Разумеется, значение P₁ зависит от p. Кажется естественным, что если p близко к 1, то вероятность P₁ мала, а если p близко к нулю, то P₁ мало отличается от 1.

 

Рассмотрим ситуацию после первого шага: либо частица сдвинулась налево, попала в точку x = 0 и поглотилась там (это событие имеет вероятность 1 - p), либо сдвинулась направо в точку x = 2 (это событие происходит с вероятностью p). Пусть P₂ обозначает вероятность того, что частица поглощается в начале координат x = 0, если она выходит из точки x = 2. Тогда мы имеем
P₁ = 1 - p + p•P₂, (1)
так как 1 - p есть вероятность поглощения на первом шаге и p•P₂ - вероятность поглощения на последующих шагах.

Каждый путь, ведущий к поглощению из x = 2, можно разбить на две части:
(1) Путь, идущий из точки x = 2 и достигающий положения x = 1 в первый раз (не обязательно за один шаг)
и
(2) Путь, идущий из точки x = 1 в точку x = 0 (также не обязательно за один шаг). Вероятность пути из положения x = 2 в x = 1 есть P₁ поскольку структура блуждания здесь идентична структуре первоначального блуждания (см. рис. 35.1), за исключением того, что начало координат переносится на один шаг направо. Вероятность попасть из точки x = 1 в x = 0 также равна P₁ как и в исходной задаче. Величина P₂ поэтому есть P₁², так как события A (частица идет по пути от точки x = 2 к x = 1) и B (частица движется по пути от точки x = 1 до x = 0) независимы, и P(A) = P( = P₁.
Мы можем переписать уравнение (1) как
P₁ = 1 - p + p•P₁², (2)
Уравнение (2) - квадратное относительно P₁ и имеет два решения:
P₁ = 1; P₁ = (1 - p)/p. (3)

В таких задачах одно или оба решения могут быть подходящими, в зависимости от значений р.

Если p = 1/2, то оба решения совпадают, и P₁ = 1. Когда p = 1, P₁ = 0, так как частица всегда движется вправо. И когда p = 0, очевидно, P₁ = 1. При p < 1/2 второе решение (3) не подходит, так как тогда (1 - p)/p > 1, а по смыслу задачи P₁ ≤ 1. Поэтому при 0 ≤ p ≤ 1/2 мы имеем P₁ = 1.

Чтобы доказать, что второе решение P₁ = (1 - p)/p имеет место при p > 1/2, нам достаточно установить, что P₁ является непрерывной функцией от p (грубо говоря, что P₁ не слишком изменяется, когда p меняется мало). Мы предполагаем эту непрерывность, но не доказываем ее.
Кривая (см. рис. 35.3) начинается в точке P₁ = 1 при p = 1/2; она должна спуститься к P = 0 при p = 1, и ее ордината всегда должна равняться 1 или (1 - p)/p. Кривая не имеет разрывов только в том случае, когда при p > 1/2 соответствующее значение равно (1 - p)/p. Итак, при предположении непрерывности функции P₁ мы получаем P₁ = (1 - p)/p при p > 1/2.
Поэтому наш пьяница с вероятностью 1/2 упадет вниз.



Приведем другую интерпретацию. Рассмотрим игрока, имеющего начальный капитал в одну денежную единицу (x = 1). Он может играть неограниченно долго, причем в каждом туре игры он с какими-то вероятностями выигрывает или проигрывает эту единицу. Чтобы вероятность банкротства игрока была не более 1/2, вероятность выигрыша в отдельной партии должна быть не менее 2/3. То, что банкротство неизбежно при p = 1/2, для большинства из нас неожиданность.

Приведем еще один взгляд на задачу. Рассмотрим игрока с начальным капиталом x = 1, играющего неограниченно долго против казино с бесконечным капиталом в "безобидную игру" (p = 1/2), при которой он выигрывает или проигрывает единицу в каждом туре. Он наверное обанкротится (P₁ = 1). Чтобы он не стал банкротом с вероятностью 1/2, вероятность его выигрыша в каждой отдельной партии должна быть p = 2/3.

То, что банкротство неизбежно даже при p WIN = 1/2 (чистые 50%), является неожиданным для большинства из нас.

Обычно считают, что если отдельные партии "безобидны" (средняя потеря равна нулю), то и вся игра безобидна. Разумеется, это представление в обычном смысле верно. Если мы представим такую игру с р = 1/2 и большим числом партий, то среднее значение денежной суммы на руках после n туров равно 1 для каждого конечного числа n.

Таким образом, отсутствие "безобидности" является одним из парадоксов бесконечного.

Другой удивительный факт состоит в том, что при p = 1/2 среднее число шагов, требуемое для поглощения, бесконечно. Случай р = 1/2 является странным и глубоким.
Вас может заинтересовать применение указанного здесь метода к частице, выходящей из точки x = m, а не из точки x = 1. Обобщение приведенного выше результата, показывает, что вероятность поглощения с абсциссы x = m есть [(1 - p)/p]^m или 1, в зависимости от того, будет ли p больше или меньше 1/2. Если p > 1/2 и m велико, то весьма вероятно, что частица избежит поглощения, и поэтому вероятность поглощения мала, а не равна 1.
Если частица выходит из начала координат 0 и ей разрешается делать шаги в обоих направлениях с вероятностью p = 1/2, то в другой классической задаче о блуждании ставится вопрос о том, вернется ли частица когда-либо в начало координат. Мы уже видели, что так действительно будет, ибо она заведомо вернется из положений x = 1 и x = -1.

Дальнейшие сведения об этой задаче прослеживаются в задаче "Разорение игрока".
 

Coin пишет: Приветствую alt2005 и все майнеры! 

Вопрос в том, на чем строить прогнозы.

Ошибкой является мнение о подравнивании перекосов всей системы.

Подравнивание имеет место, но намного превышает ожидания игрока во времени. Вы играете 100-200 спинов, видите, что 3я дюжина явно местами доминирует и в ее сторону идет явный перекос бросков.

Правильно использовать существующий тренд, чем идти на противовес фактам сессии и рассчитывать, что 3я дюжина уже перевыполнила план и сейчас замерзнет.

1) Рынок практически всегда идет дальше за самые смелые ожидания участников.
2) Подравнивание может быть очень растянутым во времени (например за следующие 1000 спинов) и практически незаметным на глаз.

P.S. Все дороги ведут в Rim.

Возьмем произвольную статистику рулетки из соседней темы с раскладкой по дюжинам:

NUM D
29 - 3
31 - 3
20 - 2
23 - 2
26 - 3
11 - 1
7 - 1
6 - 1
22 - 2
10 - 1
6 - 1
22 - 2
9 - 1
7 - 1
17 - 2
25 - 3
5 - 1
7 - 1
29 - 3
33 - 3
28 - 3
35 - 3
7 - 1
18 - 2
0 - 0
29 - 3
0 - 0
21 - 2
25 - 3
24 - 2

26 - 3
9 - 1
0 - 0
36 - 3
0 - 0
14 - 2
10 - 1
26 - 3
36 - 3
17 - 2
25 - 3
31 - 3
1 - 1
28 - 3
31 - 3
36 - 3
17 - 2
29 - 3
29 - 3
7 - 1
18 - 2
10 - 1
24 - 2
22 - 2
36 - 3
21 - 2
16 - 2
27 - 3
4 - 1
26 - 3

14 - 2
0 - 0
8 - 1
26 - 3
30 - 3
7 - 1
8 - 1
30 - 3
4 - 1
15 - 2
2 - 1
15 - 2
3 - 1
22 - 2
8 - 1
14 - 2
15 - 2
24 - 2
1 - 1
0 - 0
27 - 3
21 - 2
2 - 1
32 - 3
3 - 1
17 - 2
18 - 2
28 - 3
3 - 1
24 - 2

Высчитаем смещения от текущей дюжины: вправо +1, влево -1, на месте 0. Зеро расцениваем как 0 смещение. Переходы кольцевые, т.е. если после 3й дюжины упала 1я, то это вправо +1.

Соберем все полученные перемещения в один график, т.е. к текущей координате добавляем текущий переход +/-1 или 0. Получим классический график случайного блуждания



В этом конкретном случае нет сильных отклонений и долгих компенсаций - игра идет нормально.

Меня всегда удивляло, почему люди строят фундамент и бросают его?

Очевидный вывод из предыдущего поста, что нужно пересмотреть RM атом "Signatur".

1) Вести график случайного блуждания предикатов сессии.
2) Прогноз строить на продолжении ГРУПП самых частых бросков короткого и среднего горизонтов статистики.
3) В работу на реальные ставки отдавать только в тех случаях, когда направление прогноза совпадает с текущим перекосом (полуплоскостью) графика случайных блужданий.

P.S. п.2 можно углубить анализом IN/OUT бросков именно из текущего сектора колеса

в Одессе ты сказал, что в рулетке все похоже на моток резины и сколько бы не оттягивали принудительно в какую-то сторону, потом все возвращается в начальное положение... = это было очень правильное замечание

Двумерное случайное блуждание
Выходя из начала координат 0, частица с равной вероятностью сдвигается на один шаг либо на юг, либо на север, и одновременно (и тоже с равной вероятностью) на один шаг либо на восток, либо на запад. После того как шаг сделан, движение продолжается аналогичным образом из нового положения и так далее до бесконечности. Какова вероятность того, что частица когда-нибудь вернется в начало координат?

классические выкладки по случайным блужданиям, вопреки логике, доказывают, что

...частица не только вернется, но будет возвращаться бесконечное число раз. Более точно, надо сказать, что почти каждая частица возвращается бесконечно часто, так как существуют пути такие, например как постоянное направление на северо-восток, которые позволяют некоторым частицам уходить в бесконечность. Но доля таких частиц равна нулю.

///////////////
в предикатах нужно не просто использовать самые частые векторы, соблюдать тренд, но и знать критический уровень "натяжения", после чего система начнет возврат к началу координат.... = компенсировать отклонение
мы бы использовали и рост волны, и ее обратный ход

в этом вопросе нам бы помог alt2005 он крутой математик
 

Ну да, будет возвращаться. Применительно к рулетке - любое событие будет повторяться, если я правильно понял тему. Но вопрос - когда? Что толку, если номер повторится, скажем через 100 раз, если мы, пока дождемся этого, уйдем в минус? 
Бесполезно ждать первого (ближайшего по времени) возврата частицы или чего-то еще. На CGM я уже говорил. Проблема в том, что любое случайное событие стремиться выпасть как можно скорее. И это очень плохо. Мы не знаем, когда именно оно появится. Скорее нужно ждать появление события, как в картах. Когда туз пик не выпал 33 раза, то ясно что он в оставшихся 3-х картах. Вероятность угадать его уже не 1/36, как в начале, когда колода еще полная, а уже всего-то 1/3.

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

Никаких трендов на рулетке нет, и натяжений тоже. Система вовсе не стремится ничего компенсировать, просто такая "компенсация" происходит в рамках закона больших чисел. И то речь идет только об относительной компенсации, на соседней ветке я говорил об этом.
Никаких волн тоже нет. Есть дисперсия, но с волнами она не имеет ничего общего.