Случайные блуждания

Оказывается, считать вероятность добраться до бара с одного конкретного перекрестка неудобно (если вообще возможно). Лучше считать такие вероятности для всех перекрестков сразу. Для некоторых перекрестков вероятность известна из условия: если Василий оказался у бара, то с вероятностью 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. Что и требовалось.

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