Лекция послучайным блужданиям (М.Л. Сердобольская) (ПДФ-лекции)

2. СЛУЧАЙНЫЕ БЛУЖДАНИЯ ПО ПРЯМОЙРассмотрим простейшую математическую модель случайного блуждания. Пустьточечная частица может совершать только один тип движений: в дискретные моменты времени t0 , t1 , . . . частица совершает скачок вдоль прямой так, что в момент времени tn+1 она оказывается в точке, отстоящей от на единичное расстояниевлево или вправо от точки, где она находилась в момент времени tn . Без ограничения общности можно считать, что координата частицы в любой момент времени есть целое число. Введём на прямой некоторое начало отсчёта и будем писатьξj = m, если в момент времени tj частица находилась в точке m; здесь j = 0, 1, 2, .

. .и m = 0, ±1, ±2, . . .Предположим, что блуждание имеет случайный характер: прыжок вправо частица совершает с вероятностью p, а прыжок влево – с вероятностью q. При этомлюбые другие перемещения невозможны, так что p + q = 1. Примем также, чтовероятности скачков не зависят от положения частицы и предыстории её движения.Такая физическая модель с математической точки зрения в точности отвечает схеменезависимых испытаний Бернулли с двумя исходами – прыжком вправо, которыймы будем называть успехом, и прыжком вправо (неудачей). В рамках этой математической модели все вероятности рассчитываются на основании распределенияБернулли. Пусть частица сделала n прыжков. Вероятность того, что среди этихпрыжков будет ровно k прыжков вправо (или, что то же самое, n − k прыжковвлево) задаётся формулойP = Cnk pk q n−k ,k = 0, 1, .

. . , n.(2.1)При анализе случайных блужданий частицы очень удобно пользоваться понятием (случайной) траектории её движения за n шагов. Она представляет собой наборточек (j, ξj ), j = 0, 1, . . . , n, на двумерной координатной плоскости, в котором первая координата – это номер члена последовательности, т.

е. по сути момент времениt = j, а вторая – (случайная) величина, значение которой равно координате частицы в момент времени t = j. Для наглядности удобно соединить точки траекторииотрезками прямых, на графике получится непрерывная ломаная из n звеньев, координаты узлов которой суть (j, ξj ), j = 0, 1, . . . , n. При этом смещения за одинпрыжок ξj − ξj−1 , j = 1, 2, . . . , n, для нашей частицы суть независимые случайныевеличины, принимающие значения 1 с вероятностью p и −1 с вероятностью q.Всякая реализация движения частицы за n шагов может быть описана наборомm0 , m1 , .

. . , mn реализаций случайных координат частицы в последовательные моменты времени t = 0, 1, . . . , n, или событиемξ0 = m0 , ξ1 = m1 , . . . , ξn = mm ,или отвечающей такому движению траекторией, которую мы далее будем обозначать как Ln (m0 , mn ). Все эти описания абсолютно равноправны, и мы будем всемиими пользоваться. Будем говорить, что траектория Ln (m0 , mn ) имеет длину n (т. е.под длиной траектории будем понимать не геометрическую длину ломаной, а количество звеньев), начинается в точке (0, m0 ) и заканчивается в точке (n, mn ).При своём движении частица случайным образом «выбирает» одну из возможныхтраекторий.

Для события, вероятность которого задана формулой (2.1), возможными являются все те и только те траектории длины n, в которых ровно k смещений1mj − mj−1 = 1. Равенство (2.1) при этом можно интерпретировать так: вероятностьтого, что частица пройдет по одной из возможных траекторий, равна pk q n−k , и всегосуществуют Cnk таких траекторий, таким образом,P = pk q n−k + · · · + pk q n−k = Cnk pk q n−k .|{z}k слагаемыхCn2.1.

Вероятность смещения на d единиц вправо или влево. Выведем распределение случайной величины ξn . Будем считать, что P (ξ0 = m) = 1. Это отвечает тому, что в начальный момент времени частица достоверно находилась в точкеx = m (здесь m – фиксированное число) и далее начала случайное блуждание в соответствии с описанными выше правилами. Пусть d – смещение частицы за n шагов.Найдём P (ξn = m + d) для каждого d ∈ Z.Замечание 2.1. Справедливо очевидное равенствоP (ξn = m + d) = P (ξn = m + d | ξ0 = m),еслиP (ξ0 = m) = 1.(2.2)Представление через условную вероятность удобно, если нам необходимо явно указать, где находилась частица в начальный момент времени.Смещение частицы и число прыжков влево и вправо связаны простейшим уравнениемd = 1 · k + (−1) · (n − k) = 2k − n,(2.3)откуда k = (n + d)/2.

Понятно, что, поскольку частица сделала ровно n прыжков,число прыжков вправо должно быть целым числом в интервале [0, n], другими словами, P (ξn = m + d) = 0, если k = (n + d)/2 ∈/ {0, 1, . . . , n}. Если же указанноеограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли (2.1):P (ξn = m + d) = Cnk pk q n−k ,k=n+d,2(2.4)при обязательном условии k ∈ {0, 1, . . . , n}.Замечание 2.2. Ограничение 0 6 k 6 n по формуле (2.3) влечёт |d| 6 n.

Этоможно понять и без расчётов: если |d| > n, то частица «не успевает» дойти из начальной в конечную точку за n шагов, даже двигаясь строго в одном направлении(налево при d < 0 и направо при d > 0). Ограничение на значения k согласованои с (2.4): биномиальный коэффициент Cnk не определён при k ∈/ {0, 1, . . . , n}. Мыможем даже считать формулу (2.4) верной при любом k, если положим по определению Cnk = 0 для k ∈/ {0, 1, . . . , n}. Число шагов n и смещение d должны иметь какцелые числа одну чётность. Вероятность (2.4) не зависит от начального положения m и определяется только числом шагов n (номером члена последовательности)и смещением d.2.2.

Вероятность непопадания в ноль. Найдём вероятность того, что частица, стартовав из точки m > 0, за n шагов пришла в точку m + d > 0 и при этом ниразу не попала в точку с координатой ноль:Pn+ (m, m + d) = P (ξn = m + d, ξn−1 6= 0, . . . , ξ1 6= 0 | ξ0 = m).2(2.5)Другими словами, мы ищем вероятность того, что траектория Ln (m, m+d) целикомлежит выше горизонтальной оси. Как мы уже отмечали, вероятность прохода полюбой траектории Ln (m, m + d) равна pk q n−k , где k = (n + d)/2, поэтому вероятность (2.5) равнаPn+ (m, m + d) = Nn+ (m, m + d) · pk q n−k ,где Nn+ (m, m + d) – число траекторий из m в m + d длины n, не пересекающихгоризонтальную ось и не касающихся этой оси.

Очевидно, чтоNn+ (m, m + d) = Cnk − Nn− (m, m + d),где Cnk – полное число траекторий из (0, m) в (n, m + d), а Nn− (m, m + d) – числотраекторий из (0, m) в (n, m + d), хотя бы один раз пересекающих горизонтальнуюось.Найдём Nn− (m, m + d). Каждую интересующую нас траекторию, хотя бы одинраз пересекающую ось, будем как обозначать как L̄n (m, m + d). Для любой такойтраектории найдется хотя бы один шаг, на котором частица окажется в точке с нулевой координатой. Вычислим Nn− (m, m + d) с помощью так называемого принципаотражения.Утверждение 2.1.Nn− (m, m + d) = Cnk̄ ,еслиk̄ =n + 2m + d= k + m ∈ {0, 1, . . . , n}.2(2.6)Если k̄ ∈/ {0, 1, .

. . , n}, то Nn− (m, m + d) = 0, другими словами, проход из точки mв точку m + d с заходом в ноль невозможен.Доказательство. Возьмём любую траекторию L̄n (m, m+d). обозначим через jминимальный номер шага, для которого ξj = 0, т. е. j – момент первого пересечения или касания траекторией L̄n (m, m + d) оси. Таким образом, наша траекторияпроходит через точку с координатами (j, 0).Для каждой траектории L̄n (m, m + d) существует траектория Ln (−m, m + d) тойже длины n, идущую из точки (0, −m) в точку (n, m + d), сформированная по следующему правилу отражения.

Часть траектории Ln (−m, m+d), лежащая левее точки(j, 0), получена симметричным отражением такой же части траектории L̄n (m, m+d)относительно горизонтальной оси, а в последующих точках обе траектории совпадают. Заметим, что в моменты времени, предшествующие t = j, часть траекторииL̄n (m, m+d) лежит строго выше оси, следовательно, часть траектории Ln (−m, m+d)лежит строго ниже оси.Теперь попробуем установить обратное соответствие. Любое блуждание, начинающееся в точке −m < 0 и заканчивающееся в точке m + d > 0, с необходимостьюпройдет через точку 0 (начавшись ниже оси и закончившись выше оси, непрерывнаятраектория обязательно ось пересечёт).Рассмотрим траекторию Ln (−m, m + d), отвечающую этому блужданию.

Каки выше, обозначим через j минимальный номер шага, для которого ξj = 0 (момент первого пересечения или касания оси), и отразим симметрично относительногоризонтальной оси часть этой траектории, лежащую левее точки (j, 0), а при t > j3tРис. 1. Принцип отражения.продолжим двигаться по траектории Ln (−m, m + d). В результате получим траекторию L̄n (m, m + d), которая также проходит через точку (j, 0), т. е. пересекает ось tили касается ее (см. рис. 1).Таким образом, блуждание из m в m + d, проходящее через ноль, и любое блуждание из точки −m в точку m + d находятся во взаимно однозначном соответствии.Найдём количество траекторий вида Ln (−m, m + d).

При таком блуждании смещение частицы за n шагов равно d¯ = m + d − (−m) = 2m + d. Для того чтобысместиться на такое расстояние, нужно сделать ровно k̄ = (n + 2m + d)/2 шаговвправо. Таким образом, количество траекторий вида Ln (−m, m+d) равно Cnk̄ . В силу взаимно однозначного соответствия количество траекторий вида Ln (−m, m + d)совпадает с количеством траекторий вида L̄n (m, m + d), т. е.Nn− (m, m + d) = Cnk̄ ,k̄ =n + 2m + d.2Формула (2.6) доказана.Итак, для m > 0 и m + d > 0Pn+ (m, m + d) = (Cnk − Cnk̄ )pk q n−k ,k=n+d,2k̄ =n + 2m + d= k + m.

(2.7)2Как и в формуле (2.4), хотя бы одно из чисел k = (n + d)/2 и k̄ = (n + 2m + d)/2должно принадлежать множеству {0, 1, . . . , n}, иначе Pn+ (m, m + d) = 0. Если мыпримем, как уже говорилось выше, соглашение, что Cnk = 0, если k ∈/ {0, 1, . . . , n},то равенство нулю вероятности получится само собой.Нетрудно понять, что если в рамках наших соглашений Cnk̄ 6= 0, то и Cnk 6= 0,причём Cnk > Cnk̄ . Это можно показать и напрямую, но куда проще обратитьсяк «физическим» соображениям. В самом деле, если Cnk̄ 6= 0, то у частицы существуетвозможность пройти из точки m в точку m + d без захода в ноль. Однако Cnk – это4число всех возможных путей без всяких ограничений, разумеется, таких путей неменьше, чем путей, не проходящих через ноль, Cnk > Cnk̄ .