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

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

Симметричное случайное блуждание на квадратной решётке: 240 единичных шагов.

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

Область

Теория вероятностей; статистическая физика

Разновидность

Математическая модель

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

Современное название вошло в математический язык в начале XX века благодаря Карлу Пирсону, однако сам тип задачи имеет более ранних предшественников. В 1905 году Пирсон сформулировал в журнале Nature «проблему случайного блуждания», а лорд Рэлей указал, что математически близкая схема уже появлялась в его исследованиях случайных фаз. В 1921 году Джордж Пойа доказал знаменитую теорему о возврате блуждания на решётке, а в середине XX века принцип инвариантности Донскера строго связал масштабированные случайные блуждания с винеровским процессом.

Простейшая модель

Пусть точка начинает движение в нуле.

На каждом шаге она бросает условную монету:

• орёл - шаг вправо;
• решка - шаг влево.

После $n$ шагов положение равно сумме отдельных приращений:

$$S_n=X_1+X_2+\cdots +X_n,$$

где каждое $X_k$ равно +1 или −1. Каждый отдельный шаг непредсказуем, но траектория целиком обладает строгими вероятностными закономерностями. Эта простая конструкция стала моделью для огромного числа процессов - от диффузии и движения частиц до цен, популяций и алгоритмов.

Почему это уже случайный процесс

Одно положение $S_n$ - обычная случайная величина. Но последовательность $S_0,S_1,S_2,\dots$ описывает целую случайную историю. Поэтому случайное блуждание - один из самых наглядных примеров случайного процесса. Кроме того, простейшее блуждание является цепью Маркова: чтобы определить распределение следующего положения, достаточно знать текущее положение. Прошлый путь не нужен непосредственно.

Старые задачи об азартных играх

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

какова вероятность достичь нуля раньше некоторой верхней границы?

Такие задачи были частью ранней теории вероятностей XVII-XVIII веков.

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

Луи Башелье: блуждание цены

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

1905 год: Карл Пирсон вводит «random walk»

В июле 1905 года британский статистик Карл Пирсон обратился к читателям Nature с коротким письмом «The Problem of the Random Walk». Он предложил следующую схему. Человек начинает из точки, проходит фиксированное расстояние по прямой, затем выбирает совершенно случайное направление и снова проходит то же расстояние. После n таких шагов требуется определить вероятность того, что человек окажется на расстоянии между r и r + dr от начальной точки. Так термин «random walk» вошёл в научный оборот.

Почему Пирсону понадобилась эта задача

Пирсон был одним из создателей биометрии и математической статистики. Его интересовали задачи распространения живых организмов и пространственного рассеяния. В том же 1905 году в Nature активно обсуждалась практическая проблема уменьшения численности малярийных комаров. Случайное перемещение организма естественно приводило к вопросу: где он окажется после серии независимых изменений направления? Так один из самых абстрактных сегодня объектов вероятности появился в биометрическом и санитарном контексте.

Рэлей отвечает Пирсону

Письмо Пирсона быстро получило ответ. Лорд Рэлей заметил, что математически та же задача уже возникала у него при сложении большого числа гармонических колебаний одинаковой амплитуды со случайными фазами. Рэлей ссылался на собственные работы 1880 и 1899 годов. Это замечательный эпизод истории науки. Одна и та же математическая структура независимо возникла:

• в физике волн и случайных фаз;
• в биометрии и движении организмов.

Сам Пирсон признал, что решение Рэлея для большого числа шагов фактически отвечает на его практический вопрос.

Почему при большом числе шагов возникает нормальное распределение

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

От Пирсона к решётке

Пирсон формулировал двумерную задачу с произвольным направлением шага. Но для математического исследования особенно удобной стала решётка. На одномерной решётке точка движется вправо или влево. На квадратной двумерной решётке - в одно из четырёх соседних направлений. В трёх измерениях - к одному из шести соседей. Так возникает простой вопрос:

вернётся ли случайно блуждающая точка когда-нибудь в исходное место?

Ответ оказался неожиданно зависим от размерности пространства.

Джордж Пойа

В 1921 году венгерско-швейцарский математик Джордж Пойа опубликовал знаменитый результат о случайных блужданиях на целочисленной решётке. Он рассматривал симметричное блуждание в d-мерном пространстве. Точка на каждом шаге выбирает одного из ближайших соседей с одинаковой вероятностью. Пойа спросил: какова вероятность когда-либо снова попасть в исходную точку?

Теорема Пойа

Ответ выглядит почти парадоксально:

• в одном измерении возврат происходит с вероятностью 1;
• в двух измерениях возврат также происходит с вероятностью 1;
• в трёх и более измерениях существует положительная вероятность никогда не вернуться.

Этот результат называется теоремой Пойа о возвратности случайного блуждания.

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

Почему одномерное блуждание возвращается

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

Почему два измерения всё ещё возвратны

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

Почему три измерения меняют картину

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

История Пойа и прогулки

Позднейшая биографическая традиция связывает интерес Пойа к проблеме с его собственными прогулками. Он рассказывал, что во время прогулки несколько раз случайно встретил одну и ту же пару и задумался, насколько вероятны повторные встречи случайно движущихся людей. Сам биографический эпизод нельзя считать математическим доказательством происхождения теоремы, но он хорошо отражает геометрическую интуицию задачи. Главный научный факт остаётся точным: результат Пойа был опубликован в 1921 году.

Случайное блуждание и цепь Маркова

Простое блуждание является одним из наиболее естественных примеров цепи Маркова. Состояние - нынешняя координата. Переход зависит только от неё. На прямой:

$x\to x+1$ с вероятностью $\frac{1}{2}$;

$x\to x-1$ с вероятностью $\frac{1}{2}$.

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

Блуждание как сумма приращений

Существует и другой взгляд. Положение после $n$ шагов - сумма случайных приращений. Так случайное блуждание связывает две большие области вероятности:

• теорию сумм случайных величин;
• теорию случайных процессов.

Центральная предельная теорема описывает распределение положения в один большой момент времени. Теория процессов описывает всю траекторию. Именно из этого различия позже вырастет функциональная центральная предельная теорема.

От дискретного блуждания к броуновскому движению

Роберт Броун. Непрерывное броуновское движение стало естественным пределом масштабированных случайных блужданий.

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

Эта связь была интуитивно видна уже Башелье и физикам начала XX века.

Норберт Винер. В 1923 году он построил строгую математическую модель непрерывного броуновского движения.

Винер в 1923 году создал строгий непрерывный случайный процесс.

Но полное общее доказательство сходимости масштабированных блужданий к винеровскому процессу появилось позже.

Принцип инвариантности Донскера

В 1951 году Монро Донскер опубликовал принцип инвариантности для вероятностных предельных теорем. Пусть случайное блуждание имеет независимые одинаково распределённые приращения с нулевым средним и конечной дисперсией. Если правильно масштабировать:

• время - в $n$ раз;
• пространство - примерно в $\sqrt{n}$ раз,

то целая случайная траектория сходится по распределению к винеровскому процессу.

Это значительно сильнее обычной центральной предельной теоремы.

Центральная предельная теорема против Донскера

Центральная предельная теорема говорит:

где окажется блуждание в один большой момент времени?

Принцип Донскера говорит:

на что похожа вся траектория после масштабирования?

Поэтому теорему Донскера называют функциональной центральной предельной теоремой.

Она строго связывает дискретную и непрерывную вероятностные модели.

Универсальность броуновского предела

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

микроскопические детали могут исчезать на большом масштабе.

Исторически именно поэтому простое случайное блуждание оказалось моделью огромного числа физических и математических явлений.

Первое достижение точки

Другой важный вопрос:

когда блуждание впервые достигнет заданного уровня?

Это задача о времени первого достижения.

Она естественно возникает в:

• задаче разорения игрока;
• диффузии к поглощающей границе;
• надёжности;
• финансах;
• биологических моделях.

Из случайного блуждания выросла большая теория времён остановки.

Принцип отражения

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

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

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

Модель используется для:

• переноса частиц;
• теплопроводности;
• полимерных цепей;
• дефектов кристаллической решётки;
• случайного транспорта.

При большом числе шагов дискретная модель приводит к диффузионному уравнению и броуновскому движению.

Так простая решётка становится микроскопической моделью непрерывной физической среды.

Полимеры

Длинную полимерную молекулу можно приближённо представить как последовательность звеньев случайной ориентации. Положение конца цепи относительно начала тогда напоминает случайное блуждание. Более реалистичные модели запрещают самопересечения или учитывают взаимодействия звеньев. Отсюда возникли самонепересекающиеся случайные блуждания - важная область статистической физики.

Экология и движение организмов

Пирсон пришёл к random walk именно через биометрические задачи. В современной экологии случайные блуждания используются для приближённого описания движения животных, распространения организмов и поиска пищи. Однако реальное движение часто имеет память и направленность. Поэтому простая независимая модель служит исходной точкой, а не универсальным законом.

Генетика

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

Финансы

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

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

Алгоритмы и компьютерные науки

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

• связность сетей;
• поиск;
• выборка;
• смешивание марковских цепей;
• ранжирование вершин.

Знаменитый PageRank использует модель случайного перемещения пользователя по графу веб-страниц.

Так случайное блуждание вошло в инфраструктуру интернета.

Случайное блуждание по графу

Решётка - только частный граф. На произвольной сети случайный ход выбирает одного из соседей текущей вершины. Структура графа определяет:

• вероятность возврата;
• время достижения;
• стационарное распределение;
• скорость смешивания.

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

Почему размерность была таким важным открытием

Теорема Пойа показала, что качественное поведение случайного процесса зависит от геометрии пространства.

Один и тот же локальный закон шага:

выбрать случайного соседа,

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

Возвратность как свойство марковской цепи

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

Блуждание с дрейфом

Если вероятность шага вправо не равна вероятности шага влево, возникает дрейф.

Например:

вправо с вероятностью $p$;

влево с вероятностью $1-p$.

Если $p>\frac{1}{2}$, положение в среднем движется вправо.

Такая модель показывает разницу между:

• случайностью отдельных шагов;
• систематическим направлением процесса.

В реальных системах часто присутствуют одновременно дрейф и случайное рассеяние.

Персистентное блуждание

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

Самонепересекающееся блуждание

Другая модификация запрещает посещать одну вершину повторно. Она возникла в задачах полимерной физики. Теперь история траектории критически важна: чтобы выбрать допустимый следующий шаг, нужно знать, где процесс уже был. Такой процесс уже не является простой цепью Маркова на исходном пространстве координат. Если же расширить состояние, включив всю посещённую область, марковское описание можно восстановить. Это хороший пример роли выбора состояния.

Случайное блуждание и PageRank

В конце XX века идея случайного блуждания получила одно из самых известных цифровых применений. Веб представили как граф страниц и гиперссылок. Воображаемый пользователь случайно переходит по ссылкам. Долгосрочная доля времени, проведённая на странице, связана с её рангом. PageRank добавляет механизм случайного перехода на произвольную страницу, чтобы сделать процесс устойчивее. Так модель Пирсона и Пойа стала частью поисковой технологии.

От «пьяницы» к строгой математике

Популярное название «прогулка пьяницы» делает случайное блуждание почти бытовой головоломкой. История показывает обратное. За простой картинкой стоит соединение:

• биометрии Пирсона;
• волновой физики Рэлея;
• предельных теорем;
• решёточной геометрии Пойа;
• броуновского движения;
• функциональных предельных теорем Донскера;
• теории марковских цепей;
• современной науки о сетях.

Именно простота модели позволила ей стать универсальной лабораторией вероятности.

Историческая хронология

Год	Событие
XVII-XVIII века	Задачи об азартных играх и разорении игрока создают ранние модели одномерного случайного движения капитала.
1880	Рэлей исследует сложение случайно ориентированных колебаний - математическую задачу, близкую будущему random walk.
1900	Башелье связывает случайное движение с биржевыми ценами.
1905	Карл Пирсон формулирует в Nature «проблему случайного блуждания».
1905	Рэлей указывает на более раннюю физическую форму той же задачи.
1905-1906	Эйнштейн и Смолуховский развивают статистическую теорию броуновского движения.
1906-1907	Марков создаёт теорию цепных зависимых испытаний.
1921	Джордж Пойа доказывает теорему о возвратности блуждания в зависимости от размерности.
1923	Винер строит строгую математическую модель броуновского движения.
1951	Донскер публикует принцип инвариантности, связывающий масштабированное случайное блуждание с винеровским процессом.
Вторая половина XX века	Случайные блуждания становятся стандартным инструментом физики, биологии, теории графов и алгоритмов.
Конец XX века	Случайные блуждания по графам входят в поисковые и сетевые алгоритмы, включая PageRank.

Историческое значение

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

Наследие

Сегодня случайные блуждания используются как базовые модели и как технические инструменты. Они позволяют проверять гипотезы, строить алгоритмы, исследовать графы и приближать непрерывные процессы. Но историческое ядро остаётся тем же вопросом, который Пирсон поставил в 1905 году:

где окажется объект после большого числа случайных шагов?

Ответ на этот простой вопрос оказался связан с некоторыми из наиболее глубоких идей современной вероятности.

См. также

• Случайный процесс
• Цепи Маркова
• Марковское свойство
• Броуновское движение: от Роберта Броуна до математики Винера
• Норберт Винер и винеровский процесс
• Стационарное распределение
• PageRank: случайное блуждание по Всемирной паутине

Источники и литература

• Pearson K. The Problem of the Random Walk // Nature. 1905. Vol. 72. P. 294, 342.
• Rayleigh. The Problem of the Random Walk // Nature. 1905. Vol. 72. P. 318.
• Pólya G. Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz // Mathematische Annalen. 1921. Bd. 84. S. 149-160.
• Bachelier L. Théorie de la spéculation. Paris, 1900.
• Donsker M. D. An Invariance Principle for Certain Probability Limit Theorems // Memoirs of the American Mathematical Society. 1951. № 6. P. 1-10.
• Spitzer F. Principles of Random Walk. Princeton: Van Nostrand, 1964.
• Feller W. An Introduction to Probability Theory and Its Applications. Vol. I. New York: Wiley.