Случайное блуждание — математический объект, известный как стохастический или случайный процесс, который описывает путь, состоящий из последовательности случайных шагов в каком-нибудь математическом пространстве (например, на множестве целых чисел).
Простейшим примером случайного блуждания является случайное блуждание по числовой прямой целых чисел , , которое начинается в точке 0 и на каждом шаге сдвигается на +1 или на −1 с равной вероятностью. Другими примерами могут послужить траектория движения молекулы в жидкости или газе (броуновское движение), поиск пути у животных во время фуражировки, колебания цен акций на фондовом рынке, финансовое состояние игрока: все описанные случаи могут быть аппроксимированы моделями случайного блуждания, даже несмотря на то, что они могут не быть полностью случайными в реальной жизни.
Как видно из примеров, модель случайного блуждания применяется в инженерии и множестве научных областей, включая экологию, психологию, информатику, физику, химию, биологию, экономику и социологию. Случайное блуждание объясняет наблюдаемое поведение многих процессов в этих областях, и, таким образом, служит фундаментальной моделью для зарегистрированной стохастической активности. Так, в математике, значение π может быть приближено с использованием случайного блуждания и агентного моделированияWirth E. (2015). Pi from agent border crossings by NetLogo package . Wolfram Library Archive. Понятие случайное блуждание было впервые введено Карлом Пирсоном в 1905 году.
Виды случайных блужданий могут представлять различного рода интерес. Сам термин чаще всего отсылает к особой категории цепей Маркова или марковского процесса, а многие зависящие от времени процессы упоминаются как случайные блуждания с модификатором, указывающим на их особые свойства. Случайные блуждания (по Маркову или нет) могут также встречаться в разнообразных областях: обычно изучаемые включают в себя графы, числовую прямую целых или действительных чисел, векторные пространства, кривые поверхности, многомерные римановы многообразия, а также конечные, конечнопорожденные группы, группы Ли. Параметр времени также может быть различным. В простейшем случае блуждание происходит в дискретном времени и является последовательностью случайных величин , проиндексированных натуральными числами. Однако существуют и случайные блуждания, в которых шаги происходят в произвольный момент времени, и в этом случае позиция должна быть определена для всех моментов времени . Особыми случаями случайного блуждания являются полёт Леви и модели диффузии, такие как броуновское движение.
Случайное блуждание — это фундаментальная тема в обсуждениях марковского процесса, и его математическое изучение очень обширно.
Случайное блуждание по решётке Известной моделью случайного блуждания является блуждание по правильной решётке, где на каждом шаге расположение переходит в другую точку в соответствии с неким распределением вероятностей.
В простом случайном блуждании, расположение может переходить только в соседние точки решётки, формируя путь решётки. В простом симметричном случайном блуждании по локально ограниченной решётке вероятности перехода точки в каждого из её непосредственных соседей равны. Наиболее изученным примером является случайное блуждание по d-мерной решётке целых чисел (иногда называемой гиперкубической решёткой) .Pal, Révész (1990) Random walk in random and nonrandom environments, World Scientific
Если пространство состояний ограничено конечным числом измерений, то такая модель случайного блуждания называется простым ограниченным симметричным случайным блужданием, и вероятности переходов зависят от местоположения точки, потому что на пограничных и угловых точках движение ограничено.
Одномерное случайное блуждание
Простейшим примером случайного блуждания является случайное блуждание по числовой прямой целых чисел, , которое начинается в точке 0 и на каждом шаге сдвигается на +1 или на −1 с равной вероятностью.
Это блуждание можно проиллюстрировать следующим образом. Метка ставится на ноль числовой прямой, и подбрасывается «честная» монета. Если выпадает «орёл», метка смещается на одну единицу вправо, а если «решка» — на одну единицу влево. После пяти подкидываний, метка может находиться на −5, −3, −1, 1, 3, 5. За пять подкидываний, среди которых три «орла» и две «решки», идущих в любой последовательности, метка будет на 1. Существуют 10 способов оказаться в точке 1 (путём выпадения трёх «орлов» и двух «решек»), 10 способов оказаться в точке −1 (три «решки» и два «орла»), 5 способов оказаться в точке 3 (четыре «орла» и одна «решка»), 5 способов оказаться в точке −3 (четыре «решки» и один «орёл»), 1 способ оказаться в точке 5 (пять «орлов») и 1 способ оказаться в точке −5 (пять «решек»). Возможные исходы пяти бросков проиллюстрированы ниже.
Чтобы определить это блуждание формально, возьмём независимые случайные переменные , где каждая переменная равна либо 1 либо −1, с вероятностью, равной 50 % для каждого значения, множество и Ряд называют простым случайным блужданием по . Этот ряд (сумма последовательности −1 и 1) означает пройденное расстояние, если каждая часть блуждания имеет длину, равную единице. Математическое ожидание ряда равно нулю. То есть, среднее значение всех бросков монетки с ростом количества бросков, стремится к нулю. Это следует из свойства конечной аддитивности ожидания:
Аналогично рассуждая, используем независимость случайных величин и факт того, что , видим:
Это даёт понять, что , ожидаемая дистанция после перемещения на n шагов, должна быть порядка . В действительности,
Сколько раз случайное блуждание пересечет границу, если есть возможность блуждать бесконечно? Простейшее случайное блуждание по пересечёт каждую точку бесконечное количество раз. Полученный эффект имеет множество названий: феномен пересечения уровня, рекуррентность или задача о разорении игрока. Причина именно такого названия последнего случая заключается в следующем: игрок с конечным количеством денег в рано или поздно проиграет, если будет играть в честную игру против банка с неограниченным количеством денег. Деньги игрока представляют собой случайное блуждание, и в какой-то момент времени оно достигнет нуля и игра будет окончена.
Пусть a и b — положительные целые числа, тогда ожидаемое количество шагов, когда простое одномерное случайное блуждание с началом в точке 0 впервые достигнет b или −a равна ab. Вероятность того, что данное блуждание достигент b прежде, чем достигнет −a, равна , что следует из того факта, что простое случайное блуждание является мартингалом.
Некоторые из упомянутых выше результатов могут быть получены из свойств треугольника Паскаля. Количество всех различных блужданий по n
шагов, где каждый шаг это либо +1, либо −1 равно 2n. Для простого случайного блуждания каждый из этих шагов равновероятен. Для того, чтобы равнялось числу k, необходимо и достаточно, чтобы число шагов на +1 в блуждани превышало те, что на −1 на число k. Следовательно, шаг на +1 должен встретиться (n + k)/2 раз среди n шагов блуждания, следовательно, количество блужданий, удовлетворяющих условию , равняется количеству способов выбрать (n + k)/2 элементов из n-элементного множества.Edward A. Colding et al, Random walk models in biology, Journal of the Royal Society Interface, 2008 Это обозначается, как . Чтобы данное выражение имело смысл, необходимо, чтобы сумма n + k была чётным числом, что значит числа n и k одновременно должны быть либо чёнтыми, либо нечётными. Следовательно, вероятность того, что будет равна .Представляя записи треугольника Паскаля с точки зрения факториалов и используя формулу Стирлинга, можно получить хорошие оценки этих вероятностей для больших значений .
Если для краткости ограничить пространство до +, то количество способов, в которых случайное блуждание остановится на каком-то номере после пяти шагов может быть показано как {0,5,0,4,0,1}.
Продемонстрируем это соответствие треугольнику Паскаля для малых значений n. На нулевом шаге, единственная возможность — это остаться в нуле. Однако уже на первом ходу существует возможность оказаться либо в −1, либо в 1. На второй ход, из 1 можно сместиться на точку 2, либо же обратно в нуль. Из −1 можно сдвинуться в −2 или же обратно в нуль. Следовательно, существует один случай, когда мы окажемся в точке −2, два случая, когда в нуле, и один случай — в точке 2. k−5−4−3−2−101234511112113311464115101051 Центральная предельная теорема и закон повторного логарифма описывают важные аспекты поведения простого случайного блуждания по . В частности, с увеличением n вероятности (в пропорции с числами в каждой строке) стремятся к нормальному распределению.
Прямым обобщением можно считать случайные блуждания по кристаллическим решёткам (бесконечнократные абелевы покрывающие графы конечныы графов). На самом деле, в таких условиях возможно даже утвердить центральную предельную теорему и теорему о больших уклонениях.
Как цепь Маркова Одномерное дискретное случайное блуждание является цепью Маркова с целыми состояниями, чьё начальное распределение задаётся функцией вероятности случайной величины , а матрица переходных вероятностей имеет вид
,
то есть
Повышенные размерности
В повышенных размерностях множество точек случайного блуждания имеет довольно интересные геометрические свойства. Фактически, мы получаем дискретный фрактал, то есть множество, которое показывает стохастическое самоподобие при увеличении масштаба. При малом масштабе можно наблюдать «зазубренность» на сетке, по которой осуществляется блуждание. Две книги Лоулера, представленные в ссылках, являются хорошим источником материала по данной теме. Траектория случайного блуждания — это совокупность посещенных точек, рассматриваемых как множество с точностью до момента времени, когда блуждание достигло точки. В одном измерении траектория представляет собой просто все точки между минимальной высотой и максимальной высотой, которое достигло блуждание (обе, в среднем, порядка ).
Для визуализации двухмерного случая, можно представить человека, случайно гуляющего по городу. Этот город фактически бесконечен и расположен в квадратной сетке тротуаров. На каждом перекрестке человек случайным образом выбирает один из четырёх возможных маршрутов (в том числе тот, по которому он пришёл). Формально, это случайное блуждание по множеству всех точек на плоскости с целочисленными координатами.
Вернётся ли когда-нибудь этот человек в начальную точку блуждания? Данный случай это двухмерный эквивалент проблемы пересечения уровня, оговоренной выше. В 1921 Дьёрдь Пойя доказал, что человек почти наверняка вернётся в случае двухмерного случайного блуждания, но для трёх измерений или больше, вероятность возвращения уменьшается с увеличением количества измерений. В трёхмерном случае, вероятность уменьшается примерно до 34 %. Математик Сидзуо Какутани известен своей цитатой касательно такого результата: «Пьяница рано или поздно найдет свой путь домой, а вот пьяная птица может потеряться навсегда».
Ещё один вариант этого вопроса, который также задал Пойя звучит так: если два человека покинут одну стартовую точку, то встретятся ли они когда-нибудь? Можно рассуждать, что разница между их местоположениями (два независимых случайных блуждания) также является простым случайным блужданием, так что они почти наверняка встретятся в двухмерном блуждании, но для трёх измерений или больше, вероятность возвращения так же, как и в предыдущем случае, уменьшается с увеличением количества измерений. Пал Эрдёш и Сэмюэл Джеймс Тейлор также показали в 1960 что для измерений, меньших или равных 4, два независимых случайных блуждания, начиная с любых двух заданных точек, почти наверняка имеют бесконечно много пересечений, но для измерений, превышающих 5, они почти наверняка пересекаются лишь конечное число раз.