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

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

История

Истоки концепции случайного блуждания восходят к работам математиков XVIII—XIX веков. Одним из первых примеров является задача о разорении игрока, сформулированная Пьером де Монмором (1713) и Абрахамом де Муавром (1730). В ней рассматривалась игра, в которой капитал одного из участников изменяется случайным образом на единицу вверх или вниз, и ставился вопрос о вероятности полного разорения.

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

В 1905 году британский ботаник Роберт Броун (Броун) наблюдал хаотичное движение микроскопических частиц в жидкости, что впоследствии было названо броуновским движением. В 1905—1906 годах Альберт Эйнштейн и независимо Мариан Смолуховский дали математическое описание этого явления, используя модель случайного блуждания. Это стало одним из ключевых доказательств существования молекул.

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

Математическое определение

Одномерное случайное блуждание

Простейшая модель — одномерное случайное блуждание на целочисленной решётке. Пусть \( S_0 = 0 \) — начальное положение частицы. В каждый момент времени \( t = 1, 2, 3, \dots \) частица совершает шаг:

\[ S_t = S_{t-1} + X_t, \]

где \( X_t \) — независимые одинаково распределённые случайные величины, принимающие значения \( +1 \) с вероятностью \( p \) и \( -1 \) с вероятностью \( q = 1-p \). Если \( p = q = 0.5 \), блуждание называется симметричным.

Многомерное случайное блуждание

В \( d \)-мерном пространстве частица перемещается по решётке \( \mathbb{Z}^d \). На каждом шаге она с равной вероятностью выбирает одно из \( 2d \) направлений (вдоль координатных осей) и смещается на единицу. Например, на плоскости (\( d=2 \)) возможны четыре направления: вверх, вниз, влево, вправо.

Непрерывный предел: броуновское движение

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

Классификация и виды

По пространству состояний

• Дискретное случайное блуждание — шаги совершаются по точкам решётки (целочисленным координатам).
• Непрерывное случайное блуждание — шаги могут иметь произвольную длину и направление, распределённые по некоторому закону (например, равномерно по окружности).

По симметрии

• Симметричное — вероятности шагов в каждом направлении равны.
• Несимметричное (со сносом) — одно из направлений имеет большую вероятность. Например, в одномерном случае \( p > 0.5 \) приводит к дрейфу в положительном направлении.

По наличию памяти

• Марковское случайное блуждание — положение на следующем шаге зависит только от текущего положения (классический случай).
• Блуждание с памятью — шаг может зависеть от предыдущих положений (например, самонепересекающееся блуждание, используемое в моделировании полимеров).

Свойства

Среднее и дисперсия

Для одномерного симметричного случайного блуждания математическое ожидание положения в момент \( t \) равно нулю: \( \mathbb{E}[S_t] = 0 \). Дисперсия растёт линейно со временем: \( \text{Var}[S_t] = t \). Среднеквадратичное отклонение пропорционально \( \sqrt{t} \), что характерно для диффузионных процессов.

Возвратность и транзиентность

Свойство возвратности означает, что частица с вероятностью 1 когда-либо вернётся в исходную точку. Для симметричного случайного блуждания:

• Одномерное — возвратно (Пойа, 1921).
• Двумерное — возвратно (вероятность возвращения равна 1, хотя среднее время возвращения бесконечно).
• Трёхмерное и выше — транзиентно (вероятность возвращения меньше 1, частица уходит в бесконечность).

Закон арксинуса

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

Применение

Физика

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

Экономика и финансы

• Гипотеза эффективного рынка — изменения цен активов рассматриваются как случайное блуждание, что делает их непредсказуемыми в краткосрочной перспективе.
• Модель Блэка — Шоулза — оценка опционов основана на предположении, что цена базового актива следует геометрическому броуновскому движению (непрерывному случайному блужданию с логарифмической шкалой).

Информатика

• Алгоритмы случайного блуждания — используются в поисковых системах (PageRank) для ранжирования веб-страниц, в симуляциях сетей и в методах Монте-Карло.
• Моделирование трафика — случайные блуждания применяются для анализа поведения пользователей в интернете.

Биология

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

Примеры

Задача о пьяном моряке

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

Блуждание на графе

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

Интересные факты

• Термин «случайное блуждание» (random walk) ввёл в обиход британский математик Джон Эдвардс в 1940-х годах, хотя сам концепт известен с XVIII века.
• В 2014 году математик Такаси Хара доказал, что для случайного блуждания на некоторых фрактальных структурах (например, на треугольнике Серпинского) свойство возвратности может отличаться от классического.
• В квантовой механике существует аналог — квантовое случайное блуждание, где частица может находиться в суперпозиции состояний, что приводит к существенно иной динамике.

Критика и ограничения

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

Источники

• Пойа Г. О случайном блуждании // Математический сборник. — 1921.
• Феллер В. Введение в теорию вероятностей и её приложения. — Т. 1, 2. — М.: Мир, 1984.
• Ширяев А. Н. Вероятность. — М.: Наука, 1989.
• Башелье Л. Теория спекуляции (1900). — В кн.: Канторович Л. В. и др. Математические методы в экономике. — М., 1964.
• Эйнштейн А. О движении взвешенных в покоящейся жидкости частиц, требуемом молекулярно-кинетической теорией теплоты // Annalen der Physik. — 1905.