Случайные блуждания на плоскости

Случайные блуждания на плоскости

Задача

Студент Василий отмечает сданную сессию. Он гуляет по центру города, схема которого приведена на рисунке. Находясь на перекрестке, Василий случайным образом решает, куда ему идти дальше (каждое из четырех возможных направлений он выбирает с вероятностью 1/4). Если он окажется рядом с баром (зеленые кружочки на рисунке), то непременно зайдет в него, а если окажется рядом со станцией метро (красные кружочки на рисунке), то решит, что это знак судьбы и ему пора заканчивать развлекаться и надо ехать домой. Как найти вероятность того, что Василий доберется до бара и продолжит свой праздник, если он стоит на перекрестке, помеченном синим кружочком?

Подсказка

Оказывается, считать вероятность добраться до бара с одного конкретного перекрестка неудобно (если вообще возможно). Лучше считать такие вероятности для всех перекрестков сразу. Для некоторых перекрестков вероятность известна из условия: если Василий оказался у бара, то с вероятностью 1 он в него зайдет, а если он оказался у метро, то поедет домой, и в бар, тем самым, зайдет с вероятностью 0. Осталось понять, как связаны друг с другом искомые вероятности для соседних перекрестков.

Решение

Как говорилось в подсказке, будем искать вероятность добраться до бара сразу для всех перекрестков. Обозначим эти вероятности так, как показано на рисунке справа (и сами перекрестки будем так же называть для краткости). Как связаны вероятности соседних перекрестков? Ответ дает формула полной вероятности: вероятность добраться до бара с данного перекрестка равна среднему арифметическому вероятностей соседних перекрестков (здесь мы учли, что Василий выбирает равновероятно). Скажем, a = (b + 1)/4, потому что у этого перекрестка соседние вероятности b, 1, 0 и 0, а d = (b + e + f)/4, потому что у него соседние вероятности b, e, f и 0.

Догадаться до такой связи можно и не зная формулу полной вероятности, а фактически выведя ее в процессе рассуждений. На примере перекрестка d это выглядит так: из него с вероятностью 1/4 Василий пойдет к перекрестку b, из которого с вероятностью b попадет в бар, то есть такой вариант развития событий приведет Василия в бар с вероятностью b·1/4. Аналогично находим вероятности в других трех вариантах, а их сумма как раз должна равняться d.

Таким образом, получается система линейных уравнений

решив которую, получим:

Итак, из своей стартовой позиции Василий попадет в бар с вероятностью 38/91. Неплохие шансы!

Послесловие

Решать эту задачу можно и эмпирически, написав программу, которая будет имитировать поведение нашего Василия. Запустив эту программу много раз, можно посчитать, в какой доле экспериментов виртуальный Василий добирается до виртуального бара, и получить приближение к правильному ответу. Такой подход называется методом Монте-Карло (на «Элементах» уже была задача, иллюстрирующая этот метод).

Можно применять «программистский» подход и по-другому: присвоить искомым вероятностям a, b, c, d, e, f какие-то начальные значения, а потом итеративно корректировать их, используя равенства из системы, которая получилась в решении. Прямо по очереди: сначала подкорректировать a, потом — b, подставляя новое значение а, потом — с, . После корректирования f, нужно повторить этот цикл снова, и так далее, пока не будет достигнута нужная точность. Это — метод релаксации.

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

Если посчитать (тем же способом) в нашей задаче вероятность попадания с перекрестка d не в бар, а в метро, то получится 53/91. Что в сумме с 38/91 дает 1. То есть вероятность того, что Василий будет бесконечно долго бродить по городу, равна 0. Это не означает, что он вообще не может просто так ходить (например, он может ходить туда-сюда между перекрестками а и b), но таких вариантов очень мало по сравнению со всеми возможными маршрутами Василия. Это верно для любого места старта и для любого ограниченного города с подобной «квадратной» планировкой: принимая равновероятные случайные решения на каждом перекрестке, рано или поздно Василий попадет либо в бар, либо в метро. Это вариация задачи о разорении игрока (см. gambler’s ruin) — достаточно следить за смещением по горизонтали.

Любопытно посмотреть, что происходит при случайном блуждании, если нет никаких ограничений по размеру области. Например, в одномерном случае блуждание происходит вдоль прямой, на которой через равные промежутки отмечены точки, которые пронумерованы по порядку целыми числами. Бродяга начинает в нуле, а перед каждым ходом подбрасывает монетку, чтобы решить, в какую сторону ему идти, после чего перемещается в соседнюю точку в выбранном направлении. Оказывается, что с вероятностью 1 он вернется туда, откуда начинал свой путь. Это — теорема Пойа для одномерного случая, ее несложно доказать (доказательство приведено мелким шрифтом).

Сначала рассмотрим конечный вариант: блуждание происходит на отрезке c концами 0 и n. Обозначим за p(x) вероятность того, что блуждание придет в 0 раньше, чем в n. Тогда эта функция (определенная на множестве целых чисел от 0 до n) удовлетворяет свойствам: (1) p(0) = 1, p(n) = 0; (2) p(x) = (p(x − 1) + p(x + 1))/2. Второе свойство — это признак арифметической прогрессии, поэтому значения функции p(x) должны образовывать арифметическую прогрессию. Отсюда и из условия (1) следует, что p(x) = 1 − x/n.

Пусть теперь P(n) — вероятность того, что бродяга, блуждая по уже бесконечной прямой, вернется в начало раньше, чем удалится от него на расстояние n. Например, P(1) = 0 (потому что первым же ходом он отойдет от начала на 1), а P(2) = 1/2, потому что из точки 1 с равной вероятностью можно вернуться в начало и шагнуть в 2, и то же самое верно для точки −1. Покажем, что P(n) = 1 − 1/n. Пусть бродяга первым ходом сместился в 1. Тогда разобранный выше случай дает нам, что с вероятностью 1 − 1/n он придет в 0 раньше, чем дойдет до точки n. Аналогично, если он первым ходом сместился в точку −1. Поэтому P(n) = (1 − 1/n)/2 + (1 − 1/n)/2 = 1 − 1/n. Что и требовалось.

Читайте также:  Исчезновение фильм 2009 отзывы

В двухмерном случае теорема Пойа тоже верна: случайное блуждание по линиям бесконечной клетчатой сетки с вероятностью 1 вернется в исходную точку. Доказывается это, правда, сложнее, чем одномерный случай. Удивительно, что в трехмерном пространстве (и в больших размерностях) эта теорема уже не верна. Красивые доказательства этих фактов основываются на неожиданной аналогии между случайными блужданиями и электрическими цепями. Подробно об этом можно прочитать в статье М. Скопенкова, В. Смыкалова и А. Устинова «Случайные блуждания и электрические цепи» (опубликована в сборнике «Математическое Просвещение», выпуск 16), на основе которой подготовлена эта задача.

Существует еще одна интересная задача, при решении которой не обойтись без понятия вероятности. Это проблема «случайных блужданий». В простейшем варианте эта задача выглядит следующим образом. Вообразите себе игру, в которой игрок, начиная от точки х = 0, за каждый ход может продвинуться либо вперед (до точки х), либо назад (до точки —х), причем решение о том, куда ему идти, принимается совершенно случайно, ну, например, с помощью подбрасывания монеты. Как описать результат такого движения? В более общей форме эта задача описывает движение атомов (или других частиц) в газе — так называемое броуновское движение — или образование ошибки при измерениях. Вы увидите, насколько проблема «случайных блужданий» тесно связана с описанным выше опытом с подбрасыванием монеты.

Прежде всего давайте рассмотрим несколько примеров случайных блужданий. Их можно описать «чистым» продвижением DN, за N шагов. На фиг. 6.5 показаны три примера путей при случайном блуждании.

Что можно сказать о таком движении? Ну, во-первых, можно спросить: как далеко мы в среднем продвинемся? Нужно ожидать, что среднего продвижения вообще не будет, поскольку мы с равной вероятностью можем идти как вперед, так и назад. Однако чувствуется, что с увеличением N мы все с большей вероятностью можем блуждать где-то все дальше и дальше от начальной точки. Поэтому возникает вопрос: каково среднее абсолютное расстояние, г. е. каково среднее значение |D|? Впрочем, удобнее иметь дело не с |D|, а с D 2 ; эта величина положительна как для положительного, так и для отрицательного движения и поэтому тоже может служить разумной мерой таких случайных блужданий.

Можно показать, что ожидаемая величина D 2 N равна просто N— числу сделанных шагов. Кстати, под «ожидаемой величиной» мы понимаем наиболее вероятное значение (угаданное наилучшим образом), о котором можно думать как об ожидаемом среднем значении большого числа повторяющихся процессов блуждания. Эта величина обозначается как 2 N> и называется, кроме того, «средним квадратом расстояния». После одного шага D 2 всегда равно +1, поэтому, несомненно, 2 1> = 1. (За единицу расстояния всюду будет выбираться один шаг, и поэтому я в дальнейшем не буду писать единиц длины.)

Ожидаемая величина D 2 N для N > 1 может быть получена из DN-1. Если после (N — 1) шагов мы оказались на расстоянии DN-1 то еще один шаг даст либо DN= DN-1 + 1, либо DN=DN-1 — 1. Или для квадратов

Если процесс повторяется большое число раз, то мы ожидаем, что каждая из этих возможностей осуществляется с вероятностью 1/2, так что средняя ожидаемая величина будет просто средним арифметическим этих значений, т. е. ожидаемая величина D 2 N будет просто D 2 n-1 + 1. Но какова величина D 2 n-1, вернее, какого значения ее мы ожидаем? Просто, по определению, ясно, что это должно быть «среднее ожидаемое значение» 2 n-1>, так что

Если теперь вспомнить, что 2 1> = 1, то получается очень простой результат:

Отклонение от начального положения можно характеризовать величиной типа расстояния (а не квадрата расстояния); для этого нужно просто извлечь квадратный корень из D 2 N> и получить так называемое «среднее квадратичное расстояние» Dск:

Мы уже говорили, что случайные блуждания очень похожи на опыт с подбрасыванием монет, с которого мы начали эту главу. Если представить себе, что каждое продвижение вперед или назад обусловливается выпадением «орла» или «решки», то DN. будет просто равно N — NP, т. е. разности числа выпадений «орла» и «решки». Или поскольку N+ NP = N (где N — полное число подбрасываний), то DN= 2N— N. Вспомните, что раньше мы уже получали выражение для ожидаемого распределения величины No [она обозначалась тогда через k; см. уравнение (6.5)]. Ну а поскольку N — просто постоянная, то теперь такое же распределение получилось и для D. (Выпадение каждого «орла» означает невыпадение «решки», поэтому в связи между N и D появляется множитель 2.) Таким образом, на фиг. 6.2 график представляет одновременно и распределение расстояний, на которые мы можем уйти за 30 случайных шагов (k = 15 соответствует D = 0, а k= 16 соответствует D= 2 и т. д.).

Отклонение N от ожидаемой величины N/2 будет равно

откуда для среднего квадратичного отклонения получаем

Вспомним теперь наш результат для Dск. Мы ожидаем, что среднее расстояние, пройденное за 30 шагов, должно быть равно √30 = 5,5, откуда среднее отклонение k от 15 должно быть 5,5 : 2 ≈ 2,8. Заметьте, что средняя полуширина нашей кривой на фиг. 6.2 (т. е. полуширина «колокола» где-то посредине) как раз приблизительно равна 3, что согласуется с этим результатом.

Читайте также:  Проблемы с монитором benq

Теперь мы способны рассмотреть вопрос, которого избегали до сих пор. Как узнать, «честна» ли наша монета? Сейчас мы можем, по крайней мере частично, ответить на него. Если монета «честная», то мы ожидаем, что в половине случаев выпадет «орел», т. е.

Одновременно ожидается, что действительное число выпадений «орла» должно отличаться от N/2 на величину порядка √N/2, или, если говорить о доле отклонения, она равна

т. е. чем больше N, тем ближе к половине отношение N0/N.

На фиг. 6.6 отложены числа N/N для тех подбрасываний монеты, о которых мы говорили раньше. Как видите, при увеличении числа N кривая все ближе и ближе подходит к 0,5. Но, к сожалению, нет никаких гарантий, что для каждой данной серии или комбинации серий наблюдаемое отклонение будет близко к ожидаемому отклонению. Всегда есть конечная вероятность, что произойдет большая флуктуация — появление большого числа выпадений «орла» или «решки»,— которая даст произвольно большое отклонение. Единственное, что можно сказать,— это если отклонения близки к ожидаемому 1/2√N (скажем, со множителем 2 или 3), то нет оснований считать монету «поддельной» (или что партнер плутует).

Мы не рассматривали еще случаи, когда для монеты или какого-то другого объекта испытания, подобного монете (в том смысле, что возможны два или несколько достоверно не предсказуемых исхода наблюдения, например камень, который может упасть только на какую-то из двух сторон), имеется достаточно оснований полагать, что вероятности разных исходов не равны. Мы определили вероятность Р(О) как отношение /N. Но что принять за величину ? Каким образом можно узнать, что ожидается! Во многих случаях самое лучшее, что можно сделать, это подсчитать число выпадений «орла» в большой серии испытаний и взять = N (наблюденное). (Как можно ожидать чего-то еще?) При этом, однако, нужно понимать, что различные наблюдатели и различные серии испытаний могут дать другое значение Р(О), отличное от нашего. Следует ожидать, однако, что все эти различные ответы не будут расходиться больше чем на 1/2√N [если Р(О) близко к половине]. Физики-экспериментаторы обычно говорят, что «экспериментально найденная» вероятность имеет «ошибку», и записывают это в виде

При такой записи подразумевается, что существует некая «истинная» вероятность, которую в принципе можно подсчитать, но что различные флуктуации приводят к ошибке при экспериментальном ее определении. Однако нет возможности сделать эти рассуждения логически согласованными. Лучше все-таки, чтобы вы поняли, что вероятность в каком-то смысле — вещь субъективная, что она всегда основывается на какой-то неопределенности наших познаний и величина ее колеблется при их изменении.

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

‘) В симметрическом случае с —0 (т. е. р = q) формула (6.8) согла­суется с предельным распределением для времени первого достижения, которое элементарными методами получено в гл. III (8.6).

*) См. примечание на стр. 331.

ленными координатами. Каждое положение имеет четыре соседних. Подобным же образом в случае трех измерений каждое положение имеет шесть соседних. Чтобы определить случайное блуждание, нужно задать соответствующие четыре или шесть вероятностей. Для простоты мы рассмотрим только симметричный случай, в котором все на­правления равновероятны. Многомерные задачи много сложнее, чем одномерные, так как тут области, которыми ограничено движение частицы, могут иметь произвольную форму, и роль экранов вместо точек играют сложные границы.

Начнем с интересной теоремы, принадлежащей Пойа’).

Теорема. При одномерном и двумерном случайном блу­ждании частица с вероятностью единица рано или поздно (и поэтому бесконечно много раз) возвратится в свое началь­ное положение. Однако в случае трех измерений эта вероят­ность равна всего лишь примерно 0,35 [математическое ожидание числа возвращений равно тогда 0,65 2 k (0,35)ft = 0,35/0,65 « 0,53].

Прежде чем доказывать эту теорему, приведем две другие ее формулировки, принадлежащие Пойа. Во-первых, почти очевидно, что в случае одного или двух измерений частица с вероятно­стью единица бесконечное число раз побывает в каждом со­стоянии; в случае трех измерений это, однако, неверно. Таким об­разом, утверждение «все дороги ведут в Рим» в некотором смысле справедливо для двух измерений.

С другой стороны, рассмотрим две частицы, совершающие неза­висимые случайные блуждания, причем их перемещения происходят одновременно. Встретятся ли они когда-нибудь? Для простоты изло­жения определим расстояние между двумя возможными положениями как наименьшее число шагов, ведущих из одного положения в дру­гое. (Тогда расстояние равно сумме абсолютных величин разностей координат.) Если обе частицы движутся единичными шагами, то при каждом их перемещении расстояние между ними либо не меняется, либо меняется на две единицы. Поэтому расстояние между двумя частицами либо всегда четно, либо всегда нечетно. Во втором слу­чае две частицы никогда не могут занять одно и то же положение. В первом случае, как легко видеть, вероятность встречи частиц на п-и шаге равна вероятности того, что первая частица за 2п шагов достигнет начального положения второй частицы. Поэтому наша тео­рема утверждает, что в случае двух (но не трех) измерений две частицы наверняка будут бесконечное число раз занимать одно и то же положение. Аналогичное рассуждение показывает, что если

‘) Q. Poly a, Ober eine Aufgabe der Wahrscheinlichkeitsrechnung betref- fend die Irrfahrt im Strassennetz, Mathematische Annalen, 84 (1921), 149—160. Числовое значение 0,35 было вычислено W. Н. МсС г е a and F. J. W. W h i p- p 1 e, Random paths in two and three dimensions, Proceedings of the Royal Society of Edinburgh, 60 (1940), 281—298.

Читайте также:  Параметры запуска для изменения разрешения экрана

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

Доказательство. Для случая одного измерения теорема была доказана в примере 3, б гл. XIII, с той разницей, что там мы гово­рили об игре с бросанием монеты, а не о симметричном случайном блуждании. Для случаев двух и трех измерений теорема может быть доказана совершенно аналогично. Пусть ип — вероятность того, что п-й шаг приведет частицу в начальное положение. Согласно тео­реме 2 § 3 гл. XII, мы должны доказать, что в случае двух изме­рений ряд 2 ип расходится, а в случае трех измерений 2 ип

0,53. В случае двух измерений возвращение в начальное положение воз­можно только тогда, когда число шагов в положительных направле­ниях осей х и у равно соответственно числу шагов в отрицательных направлениях. Поэтому при нечетном п имеем ип = 0, а при четном п (согласно полиномиальному распределению гл. VI)

_ у (2«)! —JL/2nW(n2 /у и

и’2п- 42„ 2j kk(n-k)(n-k) "42" U hU ‘

Последнее выражение равно 4

Применение формулы Стирлинга показывает, что и2п имеет порядок 1 /я, так что ряд 2 ат расходится.

В случае трех измерений аналогично получаем

где сумма берется по всем j и k, удовлетворяющим условию Легко проверить, что

В скобках стоят вероятности триномиального распределения, сумма которых равна единице. Поэтому сумма квадратов этих вероятностей меньше максимальной из них, соответствующей значениям j и k, близ­ким к я/3. Применяя формулу Стирлинга, мы убеждаемся, что макси­мальная вероятность имеет величину порядка я-1, так что и2п — величина порядка и ряд ЗС й2а сходится.

Теорема Пойа аналогична фактам, изложенным в примере 3, в гл. XII в связи с бросанием нескольких монет.

В заключение этого параграфа приведем еще одну задачу, обоб­щающую понятие поглощающего экрана. Для определенности рас­смотрим случай двух измерений, когда вместо интервала 0 х а имеется плоская область D, т. е. некоторое множество точек с цело­численными координатами. Каждая точка имеет четыре соседних, но для некоторых точек области D одна или несколько соседних точек лежат вне D. Такие точки образуют границу области D; все осталь­ные точки называются внутренними. В одномерном случае границу образуют два экрана, и задача состоит в нахождении вероятности того, что, выходя из z, частица достигнет граничной точки х = 0 ранее, чем точки х = а. Будем аналогично искать вероятность того, что частица достигнет определенного участка границы, не побывав до этого ни в одной граничной точке, не принадлежащей этому участку. Это значит, что все граничные точки делятся на две группы В’ и В", и мы ищем вероятность и (х, у) того, что, выходя из внутренней точки (х, у), частица достигнет какой-нибудь точки из В’ ранее, чем точки из В". В частности, если В’ состоит из одной-единственной точки, то и (х, у) есть вероятность того, что частица рано или поздно будет поглощена в этой точке.

Пусть (х, у)—внутренняя точка. Первый шаг переводит частицу в одну из четырех соседних точек (х ± 1,у), (х,у ± 1). Если все эти четыре точки являются внутренними, то

Это — уравнение в конечных разностях, играющее ту же роль, что и (2.1) (с р = q = 1/2). Если (x-f-l,y)— граничная точка, то соответ­ствующее ей слагаемое должно быть заменено на 1 или 0, в зависи­мости от того, принадлежит ли (х + 1, у) к В’ или к В". Поэтому уравнение (7.4) будет справедливо для всех внутренних точек, если условиться, что для граничной точки (Е, т]) вероятность и (I, т>) — 1, если (Е, 7j)—точка из В’, и и (Е, tj) = 0, если (Е, 7j)— точка из В". Это соглашение играет роль граничных усло­вий (2.2).

Мы имеем теперь систему линейных уравнений (7.4) с неизве­стными и (х, у); каждой внутренней точке соответствует одно неизве­стное и одно уравнение. Эта система неоднородна, так как в ней встречается по крайней мере одна граничная точка (Е, у) из В’, при­бавляющая к правой части (7.4) слагаемое ljA. Если область D конечна, то число уравнений равно числу неизвестных. В этом случае система имеет единственное решение тогда и только тогда, когда соответствующая однородная система [и (Е, tj)—0 для всех граничных

точек] не имеет решения, отличного от нуля. Далее, и (х, у)—сред­нее арифметическое четырех соседних значений и(х ± 1 ,у), и (х,у ± 1) и поэтому не больше максимального из них. Иными словами, и(х,у) не может иметь во внутренних точках ни максимума, ни минимума, и поэтому наибольшее и наименьшее значения достигаются в гра­ничных точках. Следовательно, если все граничные значения—нули, то таковы же значения и (х, у) во всех внутренних точках. Это доказы­вает существование и единственность решения уравнения (7.4). По­скольку граничные значения равны 0 и 1, все значения и(х,у) лежат между нулем и единицей, как это и должно быть для вероятностей. Как мы увидим из общей теоремы о бесконечных цепях Маркова’), аналогичные утверждения справедливы также и для бесконечных областей.

Ссылка на основную публикацию
Слова содержащие приставку корень суффикс и окончание
Примеры разборов слов, у которых есть все основные морфемы: приставка, корень, суффикс, окончание. у бор к а у дивл ени...
Системная плата ecs mcp61m m3
Средняя цена по России, руб: 3 877 Общие характеристики Производитель Фирма, которая произвела данную материнскую плату. ECS Форм-фактор Форм-фактор –...
Системное администрирование windows 10
Наверняка вы уже слышали, что сегодня официально выходит Windows 10 Creators Update. В этой статье мы решили быть на шаг...
Словарь для it специалистов
ykaneva 2018-04-09T16:54:33+00:00 September 13th, 2017 | Практика английского | 7 Comments 7 142,973 Сегодня день программиста. По этому поводу в...
Adblock detector