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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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̄ .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций