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

Чтобы узнать о романе, см. «Случайное блуждание» .

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

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

Элементарным примером случайного блуждания является случайное блуждание по прямой из целых чисел. $\mathbb {Z}$ который начинается с 0 и на каждом шаге перемещается на +1 или -1 с равной вероятностью . Другие примеры включают путь, пройденный молекулой при ее движении в жидкости или газе (см. Броуновское движение ), путь поиска животного -фуражника или колеблющуюся цену акций и финансовое положение игрока . Случайные блуждания применяются в технике и во многих научных областях, включая экологию , психологию , информатику , физику , химию , биологию , экономику и социологию . Термин «случайное блуждание» впервые был введен Карлом Пирсоном в 1905 году.

Реализации случайных блужданий могут быть получены с помощью моделирования Монте-Карло .

Случайное блуждание по решетке

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

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

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

Элементарным примером случайного блуждания является случайное блуждание по прямой из целых чисел: $\mathbb {Z}$, который начинается с 0 и на каждом шаге перемещается на +1 или -1 с равной вероятностью.

Эту прогулку можно проиллюстрировать следующим образом. Маркер ставится на нулевую позицию на числовой прямой и подбрасывается честная монета. Если выпадает решка, маркер перемещается на одну единицу вправо. Если выпадает решка, маркер перемещается на одну единицу влево. После пяти подбрасываний маркер теперь может находиться на -5, -3, -1, 1, 3, 5. При пяти подбросах, трех орлах и двух решках в любом порядке он приземлится на 1. Существует 10 способов приземление на 1 (подбрасывая три орла и две решки), 10 способов приземления на −1 (подбрасывая три решки и две решки), 5 способов приземления на 3 (подбрасывая четыре орла и одну решку), 5 способов приземления на -3 (подбрасывая четыре решки и одну решку), 1 способ приземления на 5 (подбрасывая пять решок) и 1 способ приземления на -5 (подбрасывая пять решок). На рисунке ниже показаны возможные результаты 5 бросков.

Все возможные результаты случайного блуждания после 5 подбрасываний честной монеты

Случайное блуждание в двух измерениях ( анимационная версия )

Случайная прогулка в двух измерениях с 25 тысячами шагов ( анимационная версия )

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

Чтобы формально определить это блуждание, возьмем независимые случайные величины $Z_{1},Z_{2},\dots$, где каждая переменная равна 1 или −1 с вероятностью 50% для любого значения, и установите $S_{0}=0$ и ${\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$ Серия ​ $\{S_{n}\}$ называется простым случайным блужданием по $\mathbb {Z}$. Этот ряд (сумма последовательности -1 и единиц) дает чистое пройденное расстояние, если длина каждой части пути равна единице.Ожидание ​ $E(S_{n})$ из $S_{n}$ равен нулю. То есть среднее значение всех бросков монеты приближается к нулю по мере увеличения количества бросков. Это следует из свойства конечной аддитивности ожидания:

$$E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.$$

Аналогичный расчет, используя независимость случайных величин и тот факт, что $E(Z_{n}^{2})=1$, показывает, что:

$$E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.$$

Это намекает на то, что $E(|S_{n}|)\,\!$, ожидаемое расстояние перевода после n шагов должно быть порядка ${\sqrt {n}}$. Фактически,

$$\lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.$$

Чтобы ответить на вопрос, сколько раз случайное блуждание пересечет границу, если ему разрешено продолжать идти вечно, можно использовать простое случайное блуждание по $\mathbb {Z}$ пересечет каждую точку бесконечное число раз. У этого результата много названий: феномен пересечения уровней , повторение или разорение игрока . Причина такого названия следующая: игрок с конечной суммой денег в конечном итоге проиграет, играя в честную игру против банка с бесконечной суммой денег. Деньги игрока совершят случайное блуждание и в какой-то момент достигнут нуля, и игра будет окончена.

Если a и b — положительные целые числа, то ожидаемое количество шагов до тех пор, пока одномерное простое случайное блуждание, начинающееся с 0, впервые не достигнет b или − a , равно ab . Вероятность того, что эта прогулка достигнет b раньше − a, равна $a/(a+b)$, что можно вывести из того факта, что простое случайное блуждание является мартингейлом . И эти ожидания и вероятности попадания можно вычислить в $O(a+b)$ в общей одномерной случайной цепи Маркова.

Некоторые из упомянутых выше результатов можно вывести из свойств треугольника Паскаля . Количество различных обходов из n шагов, где каждый шаг равен +1 или -1, равно 2. ^н . Для простого случайного блуждания каждое из этих блужданий одинаково вероятно. Для того чтобы Sn _на был равен числу k, необходимо и достаточно, чтобы количество +1 в обходе превышало число −1 k . Отсюда следует, что +1 должно появиться ( n + k )/2 раз среди n шагов ходьбы, следовательно, количество прогулок, которые удовлетворяют условиям $S_{n}=k$ равно количеству способов выбора ( n + k )/2 элементов из набора n элементов, обозначенный ${\textstyle n \choose (n+k)/2}$. Чтобы это имело смысл, необходимо, чтобы n + k было четным числом, а это означает, что n и k либо оба четные, либо оба нечетные. Следовательно, вероятность того, что $S_{n}=k$ равно ${\textstyle 2^{-n}{n \choose (n+k)/2}}$. Представляя элементы треугольника Паскаля в виде факториалов и используя формулу Стирлинга , можно получить хорошие оценки этих вероятностей для больших значений $n$.

Если пространство ограничено $\mathbb {Z}$+ для краткости количество способов, которыми случайное блуждание выпадет на любое заданное число с пятью переворотами, можно выразить как {0,5,0,4,0,1}.

Эта связь с треугольником Паскаля продемонстрирована для малых значений n . При нулевых оборотах единственной возможностью будет оставаться на нуле. Однако за один ход есть один шанс приземлиться на -1 или один шанс приземлиться на 1. За два хода маркер с 1 может переместиться на 2 или вернуться к нулю. Маркер в -1 может переместиться в -2 или вернуться к нулю. Следовательно, есть один шанс попасть на −2, два шанса попасть на ноль и один шанс попасть на 2.

к	−5	−4	−3	−2	−1	0	1	2	3	4	5
$P[S_{0}=k]$						1
$2P[S_{1}=k]$					1		1
$2^{2}P[S_{2}=k]$				1		2		1
$2^{3}P[S_{3}=k]$			1		3		3		1
$2^{4}P[S_{4}=k]$		1		4		6		4		1
$2^{5}P[S_{5}=k]$	1		5		10		10		5		1

Центральная предельная теорема и закон повторного логарифма описывают важные аспекты поведения простых случайных блужданий на $\mathbb {Z}$. В частности, первое означает, что по мере увеличения n вероятности (пропорциональные числам в каждой строке) приближаются к нормальному распределению .

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

Как цепь Маркова

Одномерное случайное блуждание также можно рассматривать как цепь Маркова, пространство состояний которой задается целыми числами. $i=0,\pm 1,\pm 2,\dots .$ Для некоторого числа p, удовлетворяющего $\,0<p<1$, вероятности перехода (вероятность Pi _,j перехода из состояния i в состояние j ) определяются выражением

$$\,P_{i,i+1}=p=1-P_{i,i-1}.$$

Гетерогенное обобщение

Основная статья: Гетерогенное случайное блуждание в одном измерении

Гетерогенное случайное блуждание на каждом временном шаге рисует случайное число, определяющее локальные вероятности прыжка, а затем случайное число, определяющее фактическое направление прыжка. Главный вопрос – вероятность остаться на каждом из различных сайтов после $t$ скачков, и в пределе этой вероятности, когда $t$ очень велик.

Высшие измерения

Три случайных блуждания в трех измерениях

В более высоких измерениях набор случайно пройденных точек обладает интересными геометрическими свойствами. Фактически получается дискретный фрактал , то есть набор, который демонстрирует стохастическое самоподобие в больших масштабах. В небольших масштабах можно наблюдать «зубчатость», возникающую из-за сетки, по которой совершается прогулка. Траектория случайного блуждания — это совокупность посещенных точек, рассматриваемая как набор без учета того, когда блуждание достигло этой точки. В одном измерении траектория — это просто все точки между минимальной высотой и максимальной высотой, достигнутой при прохождении (оба в среднем порядка ${\sqrt {n}}$).

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

Чтобы ответить на вопрос о том, вернется ли человек когда-нибудь в исходную отправную точку прогулки, можно использовать двумерный эквивалент проблемы переезда, обсуждавшейся выше. В 1921 году Джордж Полиа доказал, что человек почти наверняка будет совершать двумерное случайное блуждание, но для трех измерений и выше вероятность возвращения к началу координат уменьшается по мере увеличения числа измерений. В трех измерениях вероятность снижается примерно до 34%. Известно, что математик Шизуо Какутани ссылался на этот результат следующей цитатой: «Пьяный человек найдет дорогу домой, но пьяная птица может заблудиться навсегда».

Другой вариант этого вопроса, который также задал Полья: «Если два человека покинут одну и ту же отправную точку, встретятся ли они когда-нибудь снова?» Можно показать, что разница между их местоположениями (два независимых случайных блуждания) также является простым случайным блужданием, поэтому они почти наверняка встретятся снова в 2-мерном блуждании, но для 3-х измерений и выше вероятность уменьшается с увеличением количества размеры. Пол Эрдеш и Сэмюэл Джеймс Тейлор также показали в 1960 году, что для размерностей, меньших или равных 4, два независимых случайных блуждания, начинающихся из любых двух заданных точек, почти наверняка имеют бесконечное количество пересечений, но для размерностей выше 5 они почти наверняка пересекаются только конечно часто. .

Асимптотическая функция двумерного случайного блуждания при увеличении числа шагов определяется распределением Рэлея . Распределение вероятностей является функцией радиуса от начала координат, а длина шага постоянна для каждого шага. Здесь длина шага предполагается равной 1, N — общее количество шагов, а r — радиус от начала координат.

$$P(r)={\frac {2r}{N}}e^{-r^{2}/N}$$

с

Моделирование шагов, аппроксимирующих винеровский процесс в двух измерениях

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

Винеровский процесс — это масштабный предел случайного блуждания в размерности 1. Это означает, что если существует случайное блуждание с очень маленькими шагами, существует приближение к винеровскому процессу (и, менее точно, к броуновскому движению). Точнее, если размер шага равен ε, нужно пройти прогулку длиной L /ε ² аппроксимировать длину Винера L . Когда размер шага стремится к 0 (и количество шагов пропорционально увеличивается), случайное блуждание сходится к винеровскому процессу в соответствующем смысле. Формально, если B — пространство всех путей длины L с максимальной топологией, и если M — пространство меры над B с нормальной топологией, то сходимость происходит в пространстве M . Точно так же винеровский процесс в нескольких измерениях является пределом масштабирования случайного блуждания в том же количестве измерений.

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

В двух измерениях среднее количество точек, которые одно и то же случайное блуждание имеет на границе своей траектории, равно r. ^4/3 . Это соответствует тому факту, что граница траектории винеровского процесса представляет собой фрактал размерности 4/3, факт, предсказанный Мандельбротом с помощью моделирования, но доказанный только в 2000 году.Лоулер ​ , Шрамм и Вернер .

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

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

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

$$\sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},$$

где t — время, прошедшее с момента начала случайного блуждания, $\varepsilon$ – размер шага случайного блуждания, а $\delta t$ это время, прошедшее между двумя последовательными шагами.

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

В 3D дисперсия, соответствующая функции Грина уравнения диффузии, равна:

$$\sigma ^{2}=6\,D\,t.$$

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

$$D={\frac {\varepsilon ^{2}}{6\delta t}}$$

(действительно только в 3D).

Два приведенных выше выражения дисперсии соответствуют распределению, связанному с вектором ${\vec {R}}$ который связывает два конца случайного блуждания в 3D. Отклонение, связанное с каждым компонентом $R_{x}$, $R_{y}$ или $R_{z}$ составляет лишь одну треть от этого значения (все еще в 3D).

Для 2D:

$$D={\frac {\varepsilon ^{2}}{4\delta t}}.$$

Для 1D:

$$D={\frac {\varepsilon ^{2}}{2\delta t}}.$$

Гауссово случайное блуждание

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

Здесь размер шага представляет собой обратное кумулятивное нормальное распределение. $\Phi ^{-1}(z,\mu ,\sigma )$ где 0 ≤ z ≤ 1 — равномерно распределенное случайное число, а μ и σ — среднее и стандартное отклонения нормального распределения соответственно.

Если µ не равно нулю, случайное блуждание будет изменяться по линейному тренду. Если v _s — начальное значение случайного блуждания, ожидаемое значение после n шагов будет v _s + n µ.

В частном случае, когда µ равно нулю, после n шагов распределение вероятностей расстояния перевода определяется как N (0, n σ ² ), где N () — обозначение нормального распределения, n — количество шагов, а σ — из обратного кумулятивного нормального распределения, как указано выше.

Доказательство: Гауссово случайное блуждание можно рассматривать как сумму последовательности независимых и одинаково распределенных случайных величин, X _i из обратного кумулятивного нормального распределения со средним значением, равным нулю, и σ исходного обратного кумулятивного нормального распределения:

$Z=\sum _{i=0}^{n}{X_{i}},$

но у нас есть распределение суммы двух независимых нормально распределенных случайных величин Z = X + Y , которое определяется выражением

$${\mathcal {N}}(\mu _{X}+\mu _{Y},\sigma _{X}^{2}+\sigma _{Y}^{2})$$

(см. здесь) .

В нашем случае µ _X = µ _Y = 0 и σ ² _Х = р ² _Y = п ² урожай

$${\mathcal {N}}(0,2\sigma ^{2})$$

По индукции для n шагов имеем $Z\sim {\mathcal {N}}(0,n\sigma ^{2}).$Для шагов, распределенных в соответствии с любым распределением с нулевым средним значением и конечной дисперсией (не обязательно только нормальным распределением), среднеквадратичное расстояние перевода после n шагов равно (см. тождество Бьенеме )

${\sqrt {Var(S_{n})}}={\sqrt {E[S_{n}^{2}]}}=\sigma {\sqrt {n}}.$

Но для гауссовского случайного блуждания это всего лишь стандартное отклонение распределения расстояния перевода после n шагов. Следовательно, если µ равно нулю, и поскольку среднеквадратичное расстояние перевода (RMS) составляет одно стандартное отклонение, существует вероятность 68,27%, что среднеквадратичное расстояние перевода после n шагов упадет между $\pm \sigma {\sqrt {n}}$. Аналогично, существует 50% вероятность того, что расстояние перевода после n шагов упадет между $\pm 0.6745\sigma {\sqrt {n}}$.

Количество отдельных сайтов

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

Скорость информации

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

$$R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\varphi )/\theta \right)\}\,d\varphi ,$$

$$D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,$$

где $S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2}$. Поэтому невозможно закодировать ${\{Z_{n}\}_{n=1}^{N}}$ используя двоичный код размером менее $NR(D_{\theta })$ бит и восстановить его с ожидаемой среднеквадратической ошибкой менее $D_{\theta }$. С другой стороны, для любого $\varepsilon >0$, существует $N\in \mathbb {N}$ достаточно большой и двоичный код не более $2^{NR(D_{\theta })}$ отдельные элементы, такие что ожидаемая среднеквадратическая ошибка при восстановлении ${\{Z_{n}\}_{n=1}^{N}}$ из этого кода не более $D_{\theta }-\varepsilon$.

Приложения

Энтони Гормли в Скульптура «Квантовое облако» Лондоне была спроектирована компьютером с использованием алгоритма случайного блуждания.

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

• В финансовой экономике гипотеза случайного блуждания используется для моделирования цен на акции и других факторов. Эмпирические исследования выявили некоторые отклонения от этой теоретической модели, особенно в краткосрочных и долгосрочных корреляциях. Посмотрите цены на акции .
• В популяционной генетике случайное блуждание описывает статистические свойства генетического дрейфа.
• В физике случайные блуждания используются как упрощенные модели физического броуновского движения и диффузии, такие как в жидкостях и случайное движение молекул газах. См., например, агрегацию, ограниченную диффузией. Также в физике случайные блуждания и некоторые самодействующие блуждания играют роль в квантовой теории поля .
• В производстве полупроводников случайные блуждания используются для анализа эффектов термической обработки на более мелких узлах. Он применяется для понимания диффузии легирующих примесей , дефектов , примесей и т. д. на критических этапах производства. Методы случайного блуждания также используются для изучения диффузии реагентов, продуктов и плазмы во время химического осаждения из паровой фазы процессов . Континуальная диффузия использовалась для изучения потока газов в макроскопических масштабах в CVD-реакторах. Однако меньшие размеры и возросшая сложность заставили нас рассматривать их методом случайного блуждания. Это позволяет проводить точный анализ случайных процессов на молекулярном уровне и на более мелких уровнях в производстве полупроводников.
• В математической экологии случайные блуждания используются для описания движений отдельных животных, для эмпирического подтверждения процессов биодиффузии и иногда для моделирования динамики популяций .
• В физике полимеров случайное блуждание описывает идеальную цепь . Это самая простая модель для изучения полимеров .
• В других областях математики случайное блуждание используется для вычисления решений уравнения Лапласа , для оценки гармонической меры , а также для различных конструкций в анализе и комбинаторике .
• В информатике случайные блуждания используются для оценки размера Интернета .
• При сегментации изображения случайные блуждания используются для определения меток (т. е. «объект» или «фон»), которые можно связать с каждым пикселем. Этот алгоритм обычно называют алгоритмом сегментации случайных блуждающих .

• В исследованиях мозга случайные блуждания и усиленные случайные блуждания используются для моделирования каскадов возбуждения нейронов в мозге.
• В науке о зрении дрейф глаз имеет тенденцию вести себя как случайное блуждание. По мнению некоторых авторов, фиксационные движения глаз в целом также хорошо описываются случайным блужданием.
• В психологии случайные блуждания точно объясняют связь между временем, необходимым для принятия решения, и вероятностью того, что определенное решение будет принято.
• Случайные блуждания можно использовать для выборки из пространства состояний, которое неизвестно или очень велико, например, чтобы выбрать случайную страницу в Интернете. В информатике этот метод известен как цепь Маркова Монте-Карло (MCMC).

• В беспроводных сетях для моделирования движения узла используется случайное блуждание.
• Подвижные бактерии совершают смещенные случайные блуждания .
• В физике случайные блуждания лежат в основе метода оценки Ферми .
• В Интернете сайт Twitter использует случайные блуждания, чтобы предлагать, на кого подписаться.
• Дэйв Байер и Перси Диаконис доказали, что 7 перетасовок достаточно, чтобы перемешать колоду карт (более подробную информацию см. в разделе «Перетасовка »). Этот результат переводится в утверждение о случайном блуждании в симметричной группе , что они и доказывают, с решающим использованием структуры группы с помощью анализа Фурье.

Варианты

Был рассмотрен ряд типов случайных процессов , похожих на чистые случайные блуждания, но в которых допускается более обобщение простой структуры. Чистая независимыми структура может быть охарактеризована шагами, определяемыми и одинаково распределенными случайными величинами . Случайные блуждания могут происходить в различных пространствах, таких как графы , целые числа, вещественная линия, плоскость или векторные пространства более высокой размерности, на искривленных поверхностях более высокой размерности или римановых многообразиях и на группах . Также возможно определить случайные блуждания, которые совершают свои шаги в случайное время, и в этом случае позиция X
_t должен быть определен для всех моментов времени t ∈ [0, +∞) . Конкретные случаи или пределы случайных блужданий включают модели полета Леви и модели диффузии , такие как броуновское движение .

На графиках

Случайное блуждание длины k по возможно бесконечному графу G с корнем 0 — это случайный процесс со случайными величинами. $X_{1},X_{2},\dots ,X_{k}$ такой, что $X_{1}=0$ и ${X_{i+1}}$ — вершина, выбранная равномерно случайным образом среди соседей $X_{i}$.Тогда число $p_{v,w,k}(G)$ — это вероятность того, что случайное блуждание длины k , начинающееся в v, заканчивается в w .В частности, если G — граф с корнем 0 , $p_{0,0,2k}$ это вероятность того, что $2k$-шаг случайного блуждания возвращается к 0 .

Опираясь на аналогию из предыдущего раздела о высших измерениях, предположим теперь, что наш город больше не представляет собой идеальную квадратную сетку. Когда наш человек достигает определенного перекрестка, он с равной вероятностью выбирает между различными доступными дорогами. Таким образом, если на перекрестке семь выходов, человек пройдет к каждому с вероятностью одна седьмая. Это случайное блуждание по графу. Доберется ли наш человек до своего дома? Оказывается, в довольно мягких условиях ответ по-прежнему положительный. но в зависимости от графика ответ на вариант вопроса «Встретятся ли два человека снова?» не может быть, чтобы они встречались бесконечно часто и почти наверняка.

Примером случая, когда человек почти наверняка доберется до своего дома, является случай, когда длины всех блоков находятся между a и b (где a и b — любые два конечных положительных числа). Обратите внимание: мы не предполагаем, что граф плоский , т. е. в городе могут быть туннели и мосты. Одним из способов доказательства этого результата является использование подключения к электрическим сетям . Возьмите карту города и разместите номиналом 1 Ом в каждом квартале резистор . Теперь измерьте «сопротивление между точкой и бесконечностью». Другими словами, выберите некоторое число R , возьмите все точки электрической сети, находящиеся на расстоянии больше R от нашей точки, и соедините их вместе. Теперь это конечная электрическая сеть, и мы можем измерить сопротивление от нашей точки до проводных точек. Возьмем R до бесконечности. Пределом называется сопротивление между точкой и бесконечностью . Оказывается, верно следующее (элементарное доказательство можно найти в книге Дойла и Снелла):

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

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

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

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

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

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

Хорошим справочником по случайному блужданию по графам является онлайн-книга Олдоса и Филла . Информацию о группах см. в книге Вёсса.Если переходное ядро $p(x,y)$ сам по себе является случайным (в зависимости от среды $\omega$) тогда случайное блуждание называется «случайным блужданием в случайной среде». Когда закон случайного блуждания включает в себя случайность $\omega$, закон называется отожженным законом; с другой стороны, если $\omega$ рассматривается как фиксированный, закон называется угасшим законом. См. книгу Хьюза, книгу Ревеса или конспекты лекций Зейтуни.

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

Самодействующие случайные блуждания

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

• себя Походка с избеганием самого .

Самоизбегающее блуждание длины n по $\mathbb {Z} ^{d}$ — это случайный путь из n шагов, который начинается в начале координат и совершает переходы только между соседними узлами в $\mathbb {Z} ^{d}$, никогда не посещает сайт повторно и выбирается единообразно среди всех таких путей. В двух измерениях из-за самоловушки типичный путь самоизбегания очень короткий. в то время как в более высоком измерении оно выходит за все пределы.Эта модель часто использовалась в физике полимеров (с 1960-х годов).

• цикла Случайное блуждание со стиранием .
• Усиленное случайное блуждание .
• Процесс разведки .
• Мультиагентное случайное блуждание .

Смещенные случайные блуждания по графикам

Основная статья: Смещенное случайное блуждание по графу

блуждание с

Основная статья: Случайное блуждание с максимальной энтропией

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

Коррелированные случайные блуждания

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

См. также

• Ветвящееся случайное блуждание
• Броуновское движение
• Закон повторного логарифма
• полет Леви
• Гипотеза полета Леви о поиске пищи
• Случайное блуждание со стиранием цикла
• Случайное блуждание с максимальной энтропией
• Самоизбегающая прогулка
• Корень единицы

Библиография

• Олдос, Дэвид ; Заполните, Джеймс Аллен (2002). Обратимые цепи Маркова и случайные блуждания по графам . Архивировано из оригинала 27 февраля 2019 года.
• Дойл, Питер Г.; Снелл, Дж. Лори (1984). Случайные блуждания и электрические сети . Карус Математические монографии. Том. 22. Математическая ассоциация Америки . arXiv : math.PR/0001057 . ISBN  978-0-88385-024-4 . МР   0920811 .
• Феллер, Уильям (1968), Введение в теорию вероятностей и ее приложения (Том 1). ISBN   0-471-25708-7
• Хьюз, Барри Д. (1996), Случайные блуждания и случайная среда , Oxford University Press. ISBN   0-19-853789-1
• Норрис, Джеймс (1998), Марковские цепи , издательство Кембриджского университета. ISBN   0-521-63396-6
• Полиа Г. (1921), «К проблеме расчета вероятности случайного блуждания в дорожной сети». Архивировано 4 марта 2016 года в Wayback Machine , Mathematical Annals , 84 (1–2): 149–160, март 1921 года.
• Ревес, Пал (2013), Случайное блуждание в случайной и неслучайной среде (третье издание) , World Scientific Pub Co. ISBN   978-981-4447-50-8
• Сунада, Тошиказу (2012). Топологическая кристаллография: взгляд на дискретный геометрический анализ . Обзоры и учебные пособия по прикладным математическим наукам. Том. 6. Спрингер. ISBN  978-4-431-54177-6 .
• Вайс Г. Аспекты и применение случайного блуждания , Северная Голландия, 1994.
• Весс, Вольфганг (2000), Случайные блуждания по бесконечным графам и группам , Кембриджские трактаты по математике 138, Издательство Кембриджского университета. ISBN   0-521-55292-3

Внешние ссылки

• Константы случайного блуждания Пойи
• Случайное блуждание в Java-апплете. Архивировано 31 августа 2007 г. в Wayback Machine.
• Квантовое случайное блуждание
• Гауссова оценка случайного блуждания
• Модели электронной проводимости с использованием случайных блужданий с максимальной энтропией. Демонстрационный проект Wolfram