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

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

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

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

Как видно из примеров, модель случайного блуждания применяется в инженерии и множестве научных областей, включая экологию, психологию, информатику, физику, химию, биологию, экономику и социологию. Случайное блуждание объясняет наблюдаемое поведение многих процессов в этих областях, и, таким образом, служит фундаментальной моделью для зарегистрированной стохастической активности. Так, в математике, значение π может быть приближено с использованием случайного блуждания и агентного моделирования.^[1][2] Понятие случайное блуждание было впервые введено Карлом Пирсоном в 1905 году.^[3]

Виды случайных блужданий могут представлять различного рода интерес. Сам термин чаще всего отсылает к особой категории цепей Маркова или марковского процесса, а многие зависящие от времени процессы упоминаются как случайные блуждания с модификатором, указывающим на их особые свойства. Случайные блуждания (по Маркову или нет) могут также встречаться в разнообразных областях: обычно изучаемые включают в себя графы, числовую прямую целых или действительных чисел, векторные пространства, кривые поверхности, многомерные римановы многообразия, а также конечные, конечнопорожденные группы, группы Ли. Параметр времени также может быть различным. В простейшем случае блуждание происходит в дискретном времени и является последовательностью случайных величин (X
t) = (X
1, X
2, ...), проиндексированных натуральными числами. Однако существуют и случайные блуждания, в которых шаги происходят в произвольный момент времени, и в этом случае позиция X
t должна быть определена для всех моментов времени t ∈ [0,+∞). Особыми случаями случайного блуждания являются полёт Леви и модели диффузии, такие как броуновское движение.

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

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

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

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

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

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

Графики ${\displaystyle X_{i}(i)}$ восьми одномерных случайных блужданий.

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

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

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

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

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

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

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

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

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

${\displaystyle 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.}$

Это даёт понять, что ${\displaystyle E(|S_{n}|)\,\!}$, ожидаемая дистанция после перемещения на n шагов, должна быть порядка ${\displaystyle {\sqrt {n}}}$. В действительности,^[6]

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

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

Пусть a и b — положительные целые числа, тогда ожидаемое количество шагов, когда простое одномерное случайное блуждание с началом в точке 0 впервые достигнет b или −a равна ab. Вероятность того, что данное блуждание достигент b прежде, чем достигнет −a, равна ${\displaystyle a/(a+b)}$, что следует из того факта, что простое случайное блуждание является мартингалом.

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

шагов, где каждый шаг это либо +1, либо −1 равно 2ⁿ. Для простого случайного блуждания каждый из этих шагов равновероятен. Для того, чтобы ${\displaystyle S_{n}\,\!}$ равнялось числу k, необходимо и достаточно, чтобы число шагов на +1 в блуждани превышало те, что на −1 на число k. Следовательно, шаг на +1 должен встретиться (n + k)/2 раз среди n шагов блуждания, следовательно, количество блужданий, удовлетворяющих условию ${\displaystyle S_{n}=k}$ , равняется количеству способов выбрать (n + k)/2 элементов из n-элементного множества.^[7] Это обозначается, как ${\displaystyle n \choose (n+k)/2}$. Чтобы данное выражение имело смысл, необходимо, чтобы сумма n + k была чётным числом, что значит числа n и k одновременно должны быть либо чёнтыми, либо нечётными. Следовательно, вероятность того, что ${\displaystyle S_{n}=k}$ будет равна ${\displaystyle 2^{-n}{n \choose (n+k)/2}}$.Представляя записи треугольника Паскаля с точки зрения факториалов и используя формулу Стирлинга, можно получить хорошие оценки этих вероятностей для больших значений ${\displaystyle n}$.

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

Продемонстрируем это соответствие треугольнику Паскаля для малых значений n. На нулевом шаге, единственная возможность — это остаться в нуле. Однако уже на первом ходу существует возможность оказаться либо в −1, либо в 1. На второй ход, из 1 можно сместиться на точку 2, либо же обратно в нуль. Из −1 можно сдвинуться в −2 или же обратно в нуль. Следовательно, существет один случай, когда мы окажемся в точке −2, два случая, когда в нуле, и один случай — в точке 2.

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

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

Прямым обобщением можно считать случайные блуждания по кристаллическим решёткам (бесконечнократные абелевы покрывающие графы конечныы графов). На самом деле, в таких условиях возможно даже утвердить центральную предельную теорему и теорему о больших уклонениях.^[8][9]

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

Одномерное дискретное случайное блуждание является цепью Маркова с целыми состояниями, чьё начальное распределение задаётся функцией вероятности случайной величины ${\displaystyle X_{0}}$, а матрица переходных вероятностей имеет вид

${\displaystyle P\equiv (p_{ij})_{i,j\in \mathbb {Z} }=\left({\begin{matrix}\ddots &\ddots &\ddots &\\&q_{-1}&0&p_{-1}&\\&&q_{0}&0&p_{0}\\&&&q_{1}&0&p_{1}\\&&&&\ddots &\ddots &\ddots \end{matrix}}\right)}$,

то есть

${\displaystyle p_{i,i+1}\equiv \mathbb {P} (X_{n+1}=i+1\mid X_{n}=i)=p_{i},}$

${\displaystyle p_{i,i-1}\equiv \mathbb {P} (X_{n+1}=i-1\mid X_{n}=i)=q_{i},\quad i\in \mathbb {Z} ,}$

${\displaystyle p_{ij}\equiv \mathbb {P} (X_{n+1}=j\mid X_{n}=i)=0,\quad |i-j|\not =1.}$

Повышенные размерности

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

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

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

Вернётся ли когда-нибудь этот человек в начальную точку блуждания? Данный случай это двухмерный эквивалент проблемы пересечения уровня, оговоренной выше. В 1921 Дьёрдь Пойя доказал, что человек почти наверняка вернётся в случае двухмерного случайного блуждания, но для трёх измерений или больше, вероятность возвращения уменьшается с увеличением количества измерений. В трёхмерном случае, вероятность уменьшается примерно до 34 %.^[10] Математик Сидзуо Какутани известен своей цитатой касательно такого результата: «Пьяница рано или поздно найдет свой путь домой, а вот пьяная птица может потеряться навсегда».^[11]

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

Асимптотическая функция для двухмерного случайного блуждания при увеличении числа шагов определяется распределением Рэлея. Распределение вероятностей является функцией радиуса от начала координат, и для каждого шага длина шага постоянна.

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

Отношение к Винеровскому процессу

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

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

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

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

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

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

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

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

где t — это время, прошедшее с начала случайного блуждания, ${\displaystyle \varepsilon }$ — это размер шага в блуждании, а ${\displaystyle \delta t}$ — это время, прошедшее между двумя последующими шагами.

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

В трёхмерном случае, дисперсия, соответствующая функции Грина уравнения диффузии:

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

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

${\displaystyle D={\frac {\varepsilon ^{2}}{6\delta t}}}$ (имеет смысл только в случае трёх измерений).

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

Для 2D:^[15]

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

Для 1D:^[16]

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

Теорема Донскера

Рассмотрим случайное блуждание ${\displaystyle Y_{n}=\sum \limits _{i=1}^{n}{X_{i}}}$, где ${\displaystyle EX_{i}=0,DX_{i}=\sigma ^{2}<\infty }$.

Центральная предельная теорема утверждает, что ${\displaystyle {\frac {Y_{n}}{\sigma {\sqrt {n}}}}\rightarrow N(0,1)}$ по распределению при ${\displaystyle n\rightarrow \infty }$.

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

Построим по ${\displaystyle Y_{n}}$ случайный процесс ${\displaystyle S_{n}(t),t\in [0,1]}$, определив его следующим образом: ${\displaystyle S_{n}\left({\frac {k}{n}}\right)={\frac {Y_{k}}{\sigma {\sqrt {n}}}}}$, а при остальных ${\displaystyle t}$ мы доопределим процесс линейным продолжением:

${\displaystyle S_{n}(t)=(k+1-nt)S_{n}\left({\frac {k}{n}}\right)+(nt-k)S_{n}\left({\frac {k+1}{n}}\right),t\in \left({\frac {k}{n}};{\frac {k+1}{n}}\right)}$

Из центральной предельной теоремы ${\displaystyle \forall t}$ ${\displaystyle S_{n}(t)\rightarrow N(0,t)}$ по распределению при ${\displaystyle n\rightarrow \infty }$

Это означает сходимость одномерных распределений процесса ${\displaystyle S_{n}(t)}$ к одномерным распределениям винеровского процесса. Теорема Донскера, называемая также принципом инвариантности, утверждает, что имеет место слабая сходимость процессов, ${\displaystyle S_{n}(t)\rightarrow W(t),n\rightarrow \infty }$

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

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

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

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

Если μ ненулевое, случайное блуждание будет зависеть от линейного тренда (англ. linear trend). Если v_s это начальное значение случайного блуждания, то ожидаемое значение после n шагов, будет равняться v_s + nμ.

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

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

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

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

${\displaystyle {\mathcal {N}}}$(μ_X + μ_Y, σ²_X + σ²_Y)

В нашем случае, μ_X = μ_Y = 0 and σ²_X = σ²_Y = σ² дают:

${\displaystyle {\mathcal {N}}}$(0, 2σ²)

По индукции, для n шагов имеем:

Z ~ ${\displaystyle {\mathcal {N}}}$(0, nσ²).

Для шагов, распределенных в соответствии с любым распределением с нулевым средним и конечной дисперсией (не обязательно только нормальное распределение), среднее квадратическое пройденного после n шагов расстояния определяется, как:

${\displaystyle {\sqrt {E|S_{n}^{2}|}}=\sigma {\sqrt {n}}.}$

Но для гауссового случайного блуждания это только стандартное отклонение распределения пройденного после n шагов расстояния. Следовательно, если μ равняется нулю, и если среднее квадратическое преодолённой дистанции равняется одному стандартному отклонению, существует 68,27 % вероятность, что среднее квадратическое преодолённой дистанции после n шагов будет находиться между ± σ${\displaystyle {\sqrt {n}}}$. Также, существует 50 % вероятность что пройденная дистанция после n шагов будет находиться между ± 0.6745σ${\displaystyle {\sqrt {n}}}$.

Аномальная диффузия

В неупорядоченных системах, таких как пористые среды и фракталы, ${\displaystyle \sigma ^{2}}$ может быть пропорциональным не ${\displaystyle t}$, а ${\displaystyle t^{2/d_{w}}}$. Экспонента ${\displaystyle d_{w}}$ называется экспонентой аномальной диффузии и может быть больше или меньше 2.^[17] Аномальная диффузия также может быть выражена как σ_r² ~ Dt^α где α — параметр аномалии. Некоторые диффузии в случайной среде даже пропорциональны степени логарифма времени, например блуждание Синая или диффузия Брокса.

Количество различных мест

Количество различных друг от друга мест, посещённых единственным случайным ходоком ${\displaystyle S(t)}$, было широко изучено для квадратных и кубических решёток и фракталов.^[18][19] Эта величина полезна для анализа проблем тупиков (англ. trapping) и кинетических реакций. Она также связана с колебательной плотностью состояний,^[20][21] диффузионными реакциями процессов^[22] и распределением популяций в экологии.^[23][24] Обобщение этой задачи на количество отдельных мест, посещенных ${\displaystyle N}$ случайными ходоками, обозначаемое как ${\displaystyle S_{N}(t)}$, недавно было изучено для d-мерных евклидовых решёток.^[25] Число различных мест, посещенных N ходоками не просто связано с числом различных мест, посещённых каждым ходоком.

Оценка количества информации

Оценка количества информации случайного блуждания по Гауссу относительно квадрата расстояния ошибки, то есть его квадратичная функция искажения, заданная параметрически:^[26]

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

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

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

Применения

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

Как уже упоминалось, диапазон природных явлений, которые попытались описать некоторыми разновидностями случайных блужданий, является значительным. В частности, в физике,^[27][28] химии,^[29] материаловедении,^[30][31] биологии^[32] и других различных науках.^[33][34] Вот некоторые применения случайного блуждания:

• В финансовой экономике, «гипотеза случайного блуждания» используется для моделирования цен акций и других факторов. Но эмпирические изучения обнаружили расхождения с теоретической моделью, особенно в краткосрочной и долгосрочной взаимосвязях.
• В популяционной генетике, случайное блуждание описывает статистические свойства дрейфа генов.
• В физике, случайные блуждания используются как упрощенные модели броуновского движения и диффузии, такие как случайное движение молекул в жидкостях и газах. Например, диффузно-ограниченная агрегация. Также в физике случайные блуждания и некоторые из самовзаимодействующих блужданий играют важную роль в квантовой теории поля.
• В математической экологии, случайные блуждания используются для описания отдлельных передвижений животных, для того, чтобы эмпирически поддержать процессы биодиффузии, и порой для моделирования популяционной динамики.
• В физике полимеров случайное блуждание описывает идеальную цепочку — простейшую модель для изучения полимеров.^[35]
• В других областях математики случайное блуждание используется, для поиска решения уравнения Лапласа, для оценки гармонической меры, а также для различных конструкций в анализе и комбинаторике.
• В компьютерных науках случайные блуждания используются для оценки размера сети Интернет.^[36]
• В сегментации изображений, случайные блуждания используются, чтобы определить ярлыки (например, «объект» или «фон») для ассоциации с каждым пикселем.^[37] Этот алгоритм обычно упоминается, как алгоритм сегментации «случайный ходок».

Во всех этих случаях случайное блуждание часто заменяется броуновским движением:

• В исследованиях головного мозга, случайные блуждания используются для моделирования каскадов возбуждения нейронов.
• В науке о зрении, окулярный дрейф имеет тенденцию вести себя как случайное блуждание.^[38] По мнению некоторых авторов, фиксирующие движения глаз в общем случае также описываются случайным блужданием.^[39]
• В психологии случайные блуждания точно объясняют связь между временем, необходимым для принятия решения, и вероятностью того, что определённое решение будет принято..^[40]
• Случайные блуждания можно использовать для выборки из пространства состояний, которое очень велико или неизвестно, например, чтобы выбрать случайную страницу в Интернете или для исследования условий работы случайного работника в какой-нибудь данной стране.

• При использовании в компьютерных науках, последний подход известен как марковская цепь Монте-Карло (Markov chain Monte Carlo, MCMC). Часто выборка из некоторого сложного пространства состояний также позволяет получить вероятностную оценку размера пространства. Оценка перманента большой матрицы нулей и единиц была первой большой проблемой, связанной и использованием данного подхода.

• Случайные блуждания часто используются для семплирования массивных онлайн графов, таких как социальные сети.
• В беспроводных вычислительных сетях случайное блуждание используется для моделирования движения узла.
• Подвижные бактерии совершают предвзятые случайные блуждания.^[41]
• Случайные блуждания используются для моделирования азартных игр.
• В физике случайные блуждания лежат в основе метода оценки Ферми.
• Twitter использует случайные блуждания для предложения тех, кого возможно стоит отслеживать^[42]
• Дэйв Байер и Перси Диаконис доказали, что 7 перетасовок достаточно, чтобы перемешать колоду карт (подробнее см. В разделе «Тасование»). Этот результат переводится в утверждение о случайном блуждании по симметрической группе, что они и доказывают, с решающим использованием структуры группы с помощью анализа Фурье.
• С использованием случайных блужданий возможна организация траектории движения в пространстве параметров оптимизируемой целевой функции, что применяется при решении задач оптимизации^[43]. При использовании специального закона распределения случайных величин может быть получена модификация метода случайных блужданий, именуемая полетами Леви^[англ.].
• С помощью случайных блужданий можно решить краевую задачу для уравнений Максвелла в интегральной форме. Интеграл считается с помощью метода Монте-Карло, при этом подынтегральная функция семплируется с помощью случайного блуждания. Таким образом можно найти взаимные ёмкости проводников в интегральных схемах, обходя требования методов конечных и граничных элементов к дискретизации пространства, что играет определяющую роль в выборе метода с учётом увеличения количества вентилей в современных интегральных схемах. В отличие от методов конечных и граничных элементов, метод случайных блужданий находит сразу интеграл от поля, а не поле в каждой точке, которое потом интегрируют, находя ёмкость.^[44] Методы случайного блуждания стали де-факто стандартом в начале XXI века в нахождении паразитных ёмкостей интегральных схем.
• Используется при решении уравнения переноса оптического излучения в среде с применением метода Монте-Карло.h*

Варианты

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

На графах

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

По аналогии с ранее описанной секции (повышенные размерности), предположим, что сейчас наш город больше не представляет собой идеальную квадратную сетку. Когда наш человек достигает определённого перекрестка, он с равной вероятностью выбирает между разными доступными дорогами. Таким образом, если на перекрестке семь выходов, человек пойдет к каждому с вероятностью одна седьмая. Таким образом, мы получим случайное блуждание на графе. Доберется ли наш человек до своего дома? Оказывается, при довольно хороших условиях ответ остается положительным,^[45] но, в зависимости от графа, на следующий вопрос ('Встретятся ли два человека?') ответ «бесконечно часто» уже может не быть почти достоверным событием.^[46]

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

Оказывается, что следующее предположение является истинным (элементарное доказательство можно найти в книге Дойла и Снелла):

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

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

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

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

Говоря о случайных графах, в частности о модели Эрдёша-Реньи, были получены аналитические результаты некоторых свойств случайных ходоков. Они включают в себя распределение первых^[47] и последних^[48] попаданий (англ. hitting time) ходока, где первое попадание это первый случай, когда ходок впервые наступает на ранее посещенное место, а последнее совпадает со случаем, когда ходоку некуда больше идти, кроме как на посещенное ранее место.

Хорошей справкой по случайному блужданию на графе является данная онлайн книга. Для изучения групп подойдут книги Вёсса. Если ядро переходов ${\displaystyle p(x,y)}$ само по себе является случайным (на основе среды ${\displaystyle \omega }$), то случайное блуждание называется «случайным блужданием в случайной среде». Когда закон случайного блуждания включает в себя случайность ${\displaystyle \omega }$, закон называется отожженным (англ. annealed); с другой стороны, если ${\displaystyle \omega }$ рассматривается как фиксированное, закон зовётся закаленным (англ. quenched).

Мы можем выбрать каждое возможное ребро графа с такой же вероятностью, как и локальный максимум неопределенности (энтропии). Мы также можем сделать это глобально — в случайном блуждании с максимальной энтропией (англ. maximal entropy random walk, MERW) необходимо, чтобы все пути были равновероятны или, иными словами, для любых двух вершин, каждый путь заданной длины равновероятен.^[49] Такое блуждание имеет гораздо более сильные локализирующие свойства.

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

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

• Самоизбегающее блуждание.^[50]

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

• Случайное блуждание со стиранием цикла.^[52][53]
• Усиленное случайное блуждание.^[54]
• Процесс исследования.
• Мультиагентное случайное блуждание.^[55]

Долгосрочные коррелирующие блуждания

Долгосрочные коррелирующие временные ряды встречаются во многих биологических, климатологических и экономических системах:

• Запись сердцебиения^[56]
• Последовательности некодирующей ДНК^[57]
• Временные ряды волатильности акций^[58]
• Записи температуры по всему миру^[59]

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

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

См. также

• Броуновское движение
• Закон повторного логарифма
• Винеровский процесс
• Единичный корень
• Задача о разорении игрока

Примечания

1. Wirth, E.; Szabó, G.; Czinkóczky, A. Measure Landscape Diversity with Logical Scout Agents (англ.) // ISPRS – International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences : journal. — 2016. — 8 June (vol. XLI-B2). — P. 491—495. — doi:10.5194/isprs-archives-xli-b2-491-2016. — Bibcode: 2016ISPAr49B2..491W.
2. Wirth E. (2015). Pi from agent border crossings by NetLogo package Архивная копия от 24 февраля 2021 на Wayback Machine. Wolfram Library Archive
3. Pearson, K. The Problem of the Random Walk (англ.) // Nature. — 1905. — Vol. 72, no. 1865. — P. 294. — doi:10.1038/072294b0. — Bibcode: 1905Natur..72..294P.
4. Pal, Révész (1990) Random walk in random and nonrandom environments, World Scientific
5. Kohls, Moritz; Hernandez, Tanja. Expected Coverage of Random Walk Mobility Algorithm (англ.) : journal. — 2016. — Bibcode: 2016arXiv161102861K. — arXiv:1611.02861.
6. Random Walk-1-Dimensional – from Wolfram MathWorld  (неопр.). Mathworld.wolfram.com (26 апреля 2000). Дата обращения: 2 ноября 2016. Архивировано 18 ноября 2016 года.
7. Edward A. Colding et al, Random walk models in biology, Journal of the Royal Society Interface, 2008
8. Kotani, M. and Sunada, T. Spectral geometry of crystal lattices. — Contemporary. Math. — 2003. — Т. 338. — С. 271—305. — (Contemporary Mathematics). — ISBN 9780821833834. — doi:10.1090/conm/338/06077.
9. Kotani, M. and Sunada, T. Large deviation and the tangent cone at infinity of a crystal lattice (англ.) // Math. Z.^[англ.] : journal. — 2006. — Vol. 254, no. 4. — P. 837—870. — doi:10.1007/s00209-006-0951-9.
10. Pólya's Random Walk Constants  (неопр.). Mathworld.wolfram.com. Дата обращения: 2 ноября 2016. Архивировано 21 сентября 2016 года.
11. Durrett, Rick. Probability: Theory and Examples. — Cambridge University Press, 2010. — С. 191. — ISBN 9781139491136.
12. Pólya, George. Probability ; Combinatorics ; Teaching and learning in mathematics (англ.). — Cambridge, Mass.: MIT Press, 1984. — P. 582–585. — ISBN 0-262-16097-8.
13. Erdős, P.; Taylor, S. J. Some intersection properties of random walk paths (англ.) // Acta Mathematica Academiae Scientiarum Hungaricae : journal. — 1960. — Vol. 11, no. 3—4. — P. 231—248. — ISSN 0001-5954. — doi:10.1007/BF02020942.
14. MacKenzie, D. MATHEMATICS: Taking the Measure of the Wildest Dance on Earth (англ.) // Science : journal. — 2000. — Vol. 290, no. 5498. — P. 1883—1884. — doi:10.1126/science.290.5498.1883. — PMID 17742050.
15. Chapter 2 DIFFUSION Архивная копия от 9 февраля 2015 на Wayback Machine. dartmouth.edu.
16. Diffusion equation for the random walk Архивная копия от 21 апреля 2015 на Wayback Machine. physics.uakron.edu.
17. D. Ben-Avraham and S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems Архивная копия от 4 октября 2011 на Wayback Machine, Cambridge University Press, 2000.
18. Weiss, George H.; Rubin, Robert J. Random Walks: Theory and Selected Applications // Advances in Chemical Physics. — 1982. — Т. 52. — С. 363—505. — ISBN 9780470142769. — doi:10.1002/9780470142769.ch5.
19. Blumen, A.; Klafter, J.; Zumofen, G. Models for Reaction Dynamics in Glasses // Optical Spectroscopy of Glasses. — 1986. — Т. 1. — С. 199—265. — (Physic and Chemistry of Materials with Low-Dimensional Structures). — ISBN 978-94-010-8566-3. — doi:10.1007/978-94-009-4650-7_5.
20. Alexander, S.; Orbach, R. Density of states on fractals : " fractons " // Journal de Physique Lettres. — 1982. — Т. 43, № 17. — С. 625—631. — doi:10.1051/jphyslet:019820043017062500.
21. Rammal, R.; Toulouse, G. Random walks on fractal structures and percolation clusters (англ.) // Journal de Physique Lettres : journal. — 1983. — Vol. 44, no. 1. — P. 13—22. — doi:10.1051/jphyslet:0198300440101300. Архивировано 3 марта 2021 года.
22. Smoluchowski, M.V. Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen (нем.) // Z. Phys. Chem.^[англ.] : magazin. — 1917. — S. 129—168.,Rice, S.A. Diffusion-Limited Reactions. — Elsevier, 1985. — Т. 25. — (Comprehensive Chemical Kinetics). — ISBN 978-0-444-42354-2.
23. Skellam, J. G. Random Dispersal in Theoretical Populations (англ.) // Biometrika : journal. — 1951. — Vol. 38, no. 1/2. — P. 196—218. — doi:10.2307/2332328. — PMID 14848123. — JSTOR 2332328.
24. Skellam, J. G. Studies in Statistical Ecology: I. Spatial Pattern (англ.) // Biometrika : journal. — 1952. — Vol. 39, no. 3/4. — P. 346—362. — doi:10.2307/2334030. — JSTOR 2334030.
25. Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. Territory covered by N diffusing particles (англ.) // Nature. — 1992. — Vol. 355, no. 6359. — P. 423—426. — doi:10.1038/355423a0. — Bibcode: 1992Natur.355..423L.,Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George. Number of distinct sites visited by N random walkers (англ.) // Physical Review A : journal. — 1992. — Vol. 45, no. 10. — P. 7128—7138. — doi:10.1103/PhysRevA.45.7128. — Bibcode: 1992PhRvA..45.7128L. — PMID 9906785.; for insights regarding the problem of N random walkers, see Shlesinger, Michael F. New paths for random walkers (англ.) // Nature. — 1992. — Vol. 355, no. 6359. — P. 396—397. — doi:10.1038/355396a0. — Bibcode: 1992Natur.355..396S. Архивировано 5 декабря 2020 года. and the color artwork illustrating the article.
26. Berger, T. Information rates of Wiener processes (англ.) // IEEE Transactions on Information Theory^[англ.] : journal. — 1970. — Vol. 16, no. 2. — P. 134—139. — doi:10.1109/TIT.1970.1054423.
27. Risken H. (1984) The Fokker–Planck Equation. Springer, Berlin.
28. De Gennes P. G. (1979) Scaling Concepts in Polymer Physics. Cornell University Press, Ithaca and London.
29. Van Kampen N. G. (1992) Stochastic Processes in Physics and Chemistry, revised and enlarged edition. North-Holland, Amsterdam.
30. Weiss, George H.^[англ.]. Aspects and Applications of the Random Walk (англ.). — North-Holland Publishing Co., Amsterdam, 1994. — (Random Materials and Processes). — ISBN 978-0-444-81606-1.
31. Doi M. and Edwards S. F. (1986) The Theory of Polymer Dynamics. Clarendon Press, Oxford
32. Goel N. W. and Richter-Dyn N. (1974) Stochastic Models in Biology. Academic Press, New York.
33. Redner S. (2001) A Guide to First-Passage Process. Cambridge University Press, Cambridge, UK.
34. Cox D. R. (1962) Renewal Theory. Methuen, London.
35. Jones, R.A.L. Soft condensed matter (англ.). — Reprint.. — Oxford [u.a.]: Oxford University Press, 2004. — P. 77–78. — ISBN 978-0-19-850589-1.
36. Bar-Yossef, Ziv; Gurevich, Maxim. Random sampling from a search engine's index (англ.) // Journal of the ACM : journal. — Association for Computing Machinery (ACM), 2008. — Vol. 55, no. 5. — P. 1—74. — ISSN 0004-5411. — doi:10.1145/1411509.1411514.
37. Grady, L. Random walks for image segmentation (англ.) // IEEE Transactions on Pattern Analysis and Machine Intelligence^[англ.] : journal. — 2006. — Vol. 28, no. 11. — P. 1768—1783. — doi:10.1109/TPAMI.2006.233. — PMID 17063682. Архивировано 5 июля 2017 года.
38. Rucci, M; Victor, J. D. The unsteady eye: An information-processing stage, not a bug (англ.) // Trends in Neurosciences^[англ.] : journal. — Cell Press, 2015. — Vol. 38, no. 4. — P. 195—206. — doi:10.1016/j.tins.2015.01.005. — PMID 25698649. — PMC 4385455.
39. Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. An integrated model of fixational eye movements and microsaccades (англ.) // Proceedings of the National Academy of Sciences of the United States of America : journal. — 2011. — Vol. 108, no. 39. — P. E765-70. — doi:10.1073/pnas.1102730108. — Bibcode: 2011PNAS..108E.765E. — PMID 21873243. — PMC 3182695.
40. Nosofsky, R. M.; Palmeri, T. J. An exemplar-based random walk model of speeded classification (англ.) // Psychological Review : journal. — 1997. — Vol. 104, no. 2. — P. 266—300. — doi:10.1037/0033-295x.104.2.266. — PMID 9127583. Архивировано 10 декабря 2004 года.
41. Codling, E. A; Plank, M. J; Benhamou, S. Random walk models in biology (англ.) // Journal of the Royal Society Interface^[англ.] : journal. — 2008. — 6 August (vol. 5, no. 25). — P. 813—834. — doi:10.1098/rsif.2008.0014. — PMID 18426776. — PMC 2504494.
42. Gupta, Pankaj et al. WTF: The who-to-follow system at Twitter Архивная копия от 12 июля 2019 на Wayback Machine, Proceedings of the 22nd international conference on World Wide Web
43. Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: изд-во МГТУ им. Н. Э. Баумана, 2014. 446 с.
44. A stochastic algorithm for high speed capacitance extraction in integrated circuits // Microelectronics Reliability. — 1993-07. — Т. 33, вып. 9. — С. 1420—1421. — ISSN 0026-2714. — doi:10.1016/0026-2714(93)90150-w.
45. It is interesting to remark that in a general graph the meeting of two independent random walkers does not always reduces to the problem of a single random walk returning to its starting point.
46. Krishnapur, Manjunath; Peres, Yuval. Recurrent Graphs where Two Independent Random Walks Collide Finitely Often (англ.) // Electronic Communications in Probability^[англ.] : journal. — 2004. — Vol. 9. — P. 72—81. — ISSN 1083-589X. — doi:10.1214/ECP.v9-1111. — Bibcode: 2004math......6487K. — arXiv:math/0406487. Архивировано 19 июня 2020 года.
47. Tishby, Ido; Biham, Ofer; Katzav, Eytan. The distribution of first hitting times of randomwalks on Erdős–Rényi networks (англ.) // Journal of Physics A: Mathematical and Theoretical^[англ.] : journal. — 2017. — Vol. 50, no. 11. — P. 115001. — doi:10.1088/1751-8121/aa5af3. — Bibcode: 2017JPhA...50k5001T. — arXiv:1606.01560.
48. Tishby, Ido; Biham, Ofer; Katzav, Eytan. The distribution of path lengths of self avoiding walks on Erdős–Rényi networks (англ.) // Journal of Physics A: Mathematical and Theoretical^[англ.] : journal. — 2016. — Vol. 49, no. 28. — P. 285002. — doi:10.1088/1751-8113/49/28/285002. — Bibcode: 2016JPhA...49B5002T. — arXiv:1603.06613.
49. Burda, Z.; Duda, J.; Luck, J. M.; Waclaw, B. Localization of the Maximal Entropy Random Walk (англ.) // Physical Review Letters : journal. — 2009. — Vol. 102, no. 16. — P. 160602. — doi:10.1103/PhysRevLett.102.160602. — Bibcode: 2009PhRvL.102p0602B. — arXiv:0810.4113. — PMID 19518691.
50. Madras, Neal and Slade, Gordon (1996) The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1.
51. Hemmer, S.; Hemmer, P. C. An average self-avoiding random walk on the square lattice lasts 71 steps (англ.) // Journal of Chemical Physics : journal. — 1984. — Vol. 81, no. 1. — P. 584—585. — doi:10.1063/1.447349. — Bibcode: 1984JChPh..81..584H.
52. Lawler, Gregory (1996). Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X.
53. Lawler, Gregory Conformally Invariant Processes in the Plane, book.ps Архивная копия от 16 декабря 2003 на Wayback Machine.
54. Pemantle, Robin. A survey of random processes with reinforcement (англ.) // Probability Surveys^[англ.] : journal. — 2007. — Vol. 4. — P. 1—79. — doi:10.1214/07-PS094. — arXiv:math/0610076. Архивировано 5 июня 2011 года.
55. Alamgir, M and von Luxburg, U (2010). «Multi-agent random walks for local clustering on graphs» Архивная копия от 15 апреля 2012 на Wayback Machine, IEEE 10th International Conference on Data Mining (ICDM), pp. 18-27.
56. Peng, C.-K.; Mietus, J; Hausdorff, J. M.; Havlin, S; Stanley, H. E.; Goldberger, A. L. Long-range anticorrelations and non-gaussian behavior of the heartbeat (англ.) // Phys. Rev. Lett. : journal. — 1993. — Vol. 70, no. 9. — P. 1343—1346. — doi:10.1103/PhysRevLett.70.1343. — Bibcode: 1993PhRvL..70.1343P. — PMID 10054352. Архивировано 13 июля 2015 года.
57. Peng, C. K.; Buldyrev, S. V.; Goldberger, A. L.; Havlin, S; Sciortino, F; Simons, M; Stanley, H. E. Long-range correlations in nucleotide sequences (англ.) // Nature. — 1992. — Vol. 356, no. 6365. — P. 168—170. — doi:10.1038/356168a0. — Bibcode: 1992Natur.356..168P. — PMID 1301010. Архивировано 6 ноября 2018 года.
58. Liu, Yanhui; Cizeau, Pierre; Meyer, Martin; Peng, C.-K.; Eugene Stanley, H. Correlations in economic time series (англ.) // Physica A^[англ.] : journal. — 1997. — Vol. 245, no. 3—4. — P. 437. — doi:10.1016/S0378-4371(97)00368-3. — Bibcode: 1997PhyA..245..437L. — arXiv:cond-mat/9706021.
59. Koscielny-Bunde, Eva; Bunde, Armin; Havlin, Shlomo; Roman, H. Eduardo; Goldreich, Yair; Schellnhuber, Hans-Joachim. Indication of a universal persistence law governing atmospheric variability (англ.) // Phys. Rev. Lett. : journal. — 1998. — Vol. 81, no. 3. — P. 729. — doi:10.1103/PhysRevLett.81.729. — Bibcode: 1998PhRvL..81..729K. Архивировано 13 июля 2015 года.
60. Bovet, Pierre; Benhamou, Simon. Spatial analysis of animals' movements using a correlated random walk model (англ.) // Journal of Theoretical Biology^[англ.] : journal. — 1988. — Vol. 131, no. 4. — P. 419—433. — doi:10.1016/S0022-5193(88)80038-9.
61. Kareiva, P.M.; Shigesada, N. Analyzing insect movement as a correlated random walk (англ.) // Oecologia : journal. — 1983. — Vol. 56, no. 2—3. — P. 234—238. — doi:10.1007/BF00379695. — Bibcode: 1983Oecol..56..234K. — PMID 28310199.

Литература

• Aldous, David^[англ.]; Fill, James Allen. Reversible Markov Chains and Random Walks on Graphs (англ.). — 2002.
• Ben-Avraham D.; Havlin S., Diffusion and Reactions in Fractals and Disordered Systems Архивная копия от 4 октября 2011 на Wayback Machine, Cambridge University Press, 2000.
• Doyle, Peter G.; Snell, J. Laurie. Random Walks and Electric Networks. — Mathematical Association of America, 1984. — Т. 22. — (Carus Mathematical Monographs). — ISBN 978-0-88385-024-4.
• Feller, William (1968), An Introduction to Probability Theory and its Applications (Volume 1).ISBN 0-471-25708-7
• Hughes, Barry D. (1996), Random Walks and Random Environments, Oxford University Press.ISBN 0-19-853789-1
• Norris, James (1998), Markov Chains, Cambridge University Press.ISBN 0-521-63396-6
• Pólya G.(1921), «Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz» Архивная копия от 4 марта 2016 на Wayback Machine, Mathematische Annalen, 84(1-2):149-160, March 1921.
• Révész, Pal (2013), Random Walk in Random and Non-random Environments (Third Edition), World Scientific Pub Co.ISBN 978-981-4447-50-8
• Sunada, Toshikazu^[англ.]. Topological Crystallography: With a View Towards Discrete Geometric Analysis (англ.). — Springer, 2012. — Vol. 6. — (Surveys and Tutorials in the Applied Mathematical Sciences). — ISBN 978-4-431-54177-6.
• Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.
• Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups, Cambridge tracts in mathematics 138, Cambridge University Press.ISBN 0-521-55292-3

Ссылки

• Pólya’s Random Walk Constants
• Random walk in Java Applet Архивная копия от 31 августа 2007 на Wayback Machine
• Quantum random walk
• Gaussian random walk estimator
• Electron Conductance Models Using Maximal Entropy Random Walks Wolfram Demonstrations Project