Случайная прогулка

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

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

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

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

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

Решетчатое случайное блуждание

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

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

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

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

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

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

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

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

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

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

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

$${\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)}$ ${\displaystyle O(a+b)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$${\displaystyle 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 году Лоулером , Шраммом и Вернером . ^[14]

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

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

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

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

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

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

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

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

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

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

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

Для 2D: ^[15]

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

Для 1D: ^[16]

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

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

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

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

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

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

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

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

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

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

(глянь сюда)

В нашем случае µ _X = µ _Y = 0 и σ ² _X = σ ² _Y = σ ² дают

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

nрасстояниеnтождество Бьенеме ${\displaystyle Z\sim {\mathcal {N}}(0,n\sigma ^{2}).}$

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

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

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

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

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

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

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

Приложения

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

Как уже упоминалось, диапазон природных явлений, которые были предметом попыток описания с помощью той или иной разновидности случайных блужданий, значителен, особенно в физике ^{[25] [26]} и химии, ^[27] материаловедении , ^{[28] [29]} и биологии. . ^{[30] [31] [32]} Ниже приведены некоторые конкретные применения случайных блужданий:

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

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

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

Варианты

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

На графиках

Случайное блуждание длины k по возможно бесконечному графу G с корнем 0 представляет собой случайный процесс со случайными величинами, такими что и является вершиной, выбранной равномерно случайным образом из соседей . Тогда число — это вероятность того, что случайное блуждание длины k, начинающееся в v , заканчивается в w . В частности, если G — граф с корнем 0 , это вероятность того, что случайное блуждание с шагом -шага вернется к 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)}$ ${\displaystyle p_{0,0,2k}}$ ${\displaystyle 2k}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Случайное блуждание со стиранием цикла . ^{[49] [50]}
• Усиленное случайное блуждание. ^[51]
• Процесс разведки. ^{[ нужна цитата ]}
• Мультиагентное случайное блуждание. ^[52]

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Пирсон, Карл (1905). «Проблема случайного блуждания». Природа . 72 (1865): 294. Бибкод : 1905Natur..72..294P. дои : 10.1038/072294b0. S2CID  4010776.
2. Теория и применение моделирования Монте-Карло. (2013). Хорватский: IntechOpen. Страница 229, https://books.google.de/books?id=3HWfDwAAQBAJ&pg=PA229.
3. Пал, Ревес (1990) Случайное блуждание в случайной и неслучайной среде , World Scientific
4. Кольс, Мориц; Эрнандес, Таня (2016). «Ожидаемое покрытие алгоритма мобильности случайного блуждания». arXiv : 1611.02861 [стат.AP].
5. «Случайное одномерное блуждание - из Wolfram MathWorld» . Mathworld.wolfram.com. 26 апреля 2000 года . Проверено 2 ноября 2016 г. .
6. Эдвард А. Кодлинг и др., Модели случайного блуждания в биологии, Журнал интерфейса Королевского общества, 2008 г.
7. Котани, М.; Сунада, Т. (2003). Спектральная геометрия кристаллических решеток . Современная математика. Том. 338. стр. 271–305. дои : 10.1090/conm/338/06077 . ISBN 978-0-8218-3383-4.
8. Котани, М.; Сунада, Т. (2006). «Большое отклонение и касательный конус на бесконечности кристаллической решетки». Математика. З. _ 254 (4): 837–870. дои : 10.1007/s00209-006-0951-9. S2CID  122531716.
9. "Константы случайного блуждания Полии" . Mathworld.wolfram.com . Проверено 2 ноября 2016 г. .
10. Дарретт, Рик (2010). Вероятность: теория и примеры . Издательство Кембриджского университета. стр. 191. ISBN. 978-1-139-49113-6.
11. Полиа, Джордж (1984). Вероятность; комбинаторика; Преподавание и обучение математике . Рота, Джан-Карло, 1932–1999 гг., Рейнольдс, MC, Шортт, Рэй Майкл. Кембридж, Массачусетс: MIT Press. стр. 582–585. ISBN 0-262-16097-8. ОСЛК  10208449.
12. Эрдеш, П.; Тейлор, SJ (1960). «Некоторые свойства пересечения путей случайного блуждания». Acta Mathematica Academiae Scientiarum Hungaricae . 11 (3–4): 231–248. CiteSeerX 10.1.1.210.6357 . дои : 10.1007/BF02020942. ISSN  0001-5954. S2CID  14143214. 
13. https://ocw.mit.edu/courses/18-366-random-walks-and-diffusion-fall-2006/aef0a2690183294e59ea8cb29f8dd448_lec01.pdf
14. Маккензи, Д. (2000). «МАТЕМАТИКА: Измерение самого дикого танца на Земле». Наука . 290 (5498): 1883–4. дои : 10.1126/science.290.5498.1883. PMID  17742050. S2CID  12829171. (Ошибка:  doi :10.1126/science.291.5504.597)
15. Глава 2 ДИФФУЗИЯ. Дартмут.edu.
16. Уравнение диффузии для случайного блуждания. Архивировано 21 апреля 2015 года в Wayback Machine . Physics.uakron.edu.
17. Вайс, Джордж Х.; Рубин, Роберт Дж. (1982). «Случайные блуждания: теория и избранные приложения». Достижения химической физики . Том. 52. С. 363–505. дои : 10.1002/9780470142769.ch5. ISBN 978-0-470-14276-9.
18. Блюмен, А.; Клафтер, Дж.; Зумофен, Г. (1986). «Модели динамики реакций в очках». Оптическая спектроскопия стекол . Физика и химия материалов с низкоразмерной структурой. Том. 1. стр. 199–265. Бибкод : 1986PCMLD...1..199B. дои : 10.1007/978-94-009-4650-7_5. ISBN 978-94-010-8566-3.
19. Александр, С.; Орбах, Р. (1982). «Плотность состояний на фракталах: «фратоны»» (PDF) . Журнал Physique Lettres . 43 (17): 625–631. doi : 10.1051/jphyslet: 019820043017062500. S2CID  67757791.
20. Раммал, Р.; Тулуза, Г. (1983). «Случайные блуждания по фрактальным структурам и перколяционным кластерам». Журнал Physique Lettres . 44 (1): 13–22. doi : 10.1051/jphyslet: 0198300440101300.
21. Смолуховский, М.В. (1917). «Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen». З. Физ. хим. (29): 129–168., Райс, ЮАР (1 марта 1985 г.). Диффузионно-ограниченные реакции. Комплексная химическая кинетика. Том. 25. Эльзевир. ISBN 978-0-444-42354-2. Проверено 13 августа 2013 г.
22. Скеллам, JG (1951). «Случайное рассредоточение теоретических популяций». Биометрика . 38 (1/2): 196–218. дои : 10.2307/2332328. JSTOR  2332328. PMID  14848123.
23. Скеллам, JG (1952). «Исследования по статистической экологии: I. Пространственная структура». Биометрика . 39 (3/4): 346–362. дои : 10.2307/2334030. JSTOR  2334030.
24. Бергер, Т. (1970). «Информационные скорости винеровских процессов». Транзакции IEEE по теории информации . 16 (2): 134–139. дои : 10.1109/TIT.1970.1054423.
25. Рискен Х. (1984) Уравнение Фоккера-Планка . Шпрингер, Берлин.
26. Де Женн П.Г. (1979) Концепции масштабирования в физике полимеров . Издательство Корнельского университета, Итака и Лондон.
27. Ван Кампен Н.Г. (1992) Стохастические процессы в физике и химии , исправленное и дополненное издание. Северная Голландия, Амстердам.
28. Вайс, Джордж Х. (1994). Аспекты и приложения случайного блуждания . Случайные материалы и процессы. Издательство Северной Голландии, Амстердам. ISBN 978-0-444-81606-1. МР  1280031.
29. Дой М. и Эдвардс С.Ф. (1986) Теория динамики полимеров . Кларендон Пресс, Оксфорд
30. Гоэл Н.В. и Рихтер-Дин Н. (1974) Стохастические модели в биологии . Академик Пресс, Нью-Йорк.
31. Реднер С. (2001) Руководство по процессу первого прохождения . Издательство Кембриджского университета, Кембридж, Великобритания.
32. Кокс Д.Р. (1962) Теория обновления . Метуэн, Лондон.
33. Дэвид А. Кодде и Хайн Шредер (1984), Прогнозирование корпоративных доходов и прибыли: модели временных рядов в сравнении с менеджментом и аналитиками, Journal of Business Finance and Accounting, vol. 11, № 3, осень 1984 г.
34. Джонс, RAL (2004). Мягкий конденсированный носитель (Перепечатка. Под ред.). Оксфорд [ua]: Oxford Univ. Пр. стр. 77–78. ISBN 978-0-19-850589-1.
35. Бар-Йосеф, Зив; Гуревич, Максим (2008). «Случайная выборка из индекса поисковой системы». Журнал АКМ . Ассоциация вычислительной техники (ACM). 55 (5): 1–74. дои : 10.1145/1411509.1411514. ISSN  0004-5411.
36. Грейди, Л. (2006). «Случайные блуждания для сегментации изображений» (PDF) . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 28 (11): 1768–83. CiteSeerX 10.1.1.375.3389 . дои : 10.1109/TPAMI.2006.233. PMID  17063682. S2CID  489789. Архивировано из оригинала (PDF) 5 июля 2017 года . Проверено 2 ноября 2016 г. . 
37. Руччи, М; Виктор, доктор юридических наук (2015). «Неустойчивый глаз: этап обработки информации, а не ошибка». Тенденции в нейронауках . 38 (4): 195–206. doi :10.1016/j.tins.2015.01.005. ПМЦ 4385455 . ПМИД  25698649. 
38. Энгберт, Р.; Мергенталер, К.; Синн, П.; Пиковский, А. (2011). «Интегрированная модель фиксационных движений глаз и микросаккад». Труды Национальной академии наук . 108 (39): Е765-70. Бибкод : 2011PNAS..108E.765E. дои : 10.1073/pnas.1102730108 . ПМК 3182695 . ПМИД  21873243. 
39. Нософски, РМ; Палмери, Ти Джей (1997). «Модель ускоренной классификации случайного блуждания на основе образцов» (PDF) . Психологический обзор . 104 (2): 266–300. дои : 10.1037/0033-295x.104.2.266. PMID  9127583. Архивировано из оригинала (PDF) 10 декабря 2004 г.
40. Кодлинг, EA; Планк, MJ; Бенаму, С. (6 августа 2008 г.). «Модели случайного блуждания в биологии». Журнал интерфейса Королевского общества . 5 (25): 813–834. дои : 10.1098/rsif.2008.0014. ПМК 2504494 . ПМИД  18426776. 
41. Гупта, Панкадж и др. WTF: Система «за кем следить» в Твиттере, Материалы 22-й международной конференции по Всемирной паутине
42. Интересно отметить, что в общем графе встреча двух независимых случайных блуждающих не всегда сводится к проблеме возвращения одного случайного блуждания в исходную точку.
43. Кришнапур, Манджунатх; Перес, Юваль (2004). «Рекуррентные графы, в которых два независимых случайных блуждания сталкиваются конечно часто». Электронные коммуникации в теории вероятности . 9 : 72–81. arXiv : math/0406487 . Бибкод : 2004math......6487K. дои : 10.1214/ECP.v9-1111. ISSN  1083-589Х. S2CID  16584737.
44. Тишби, Идо; Бихам, Офер; Кацав, Эйтан (2017). «Распределение времени первого попадания случайных блужданий в сетях Эрдеша – Реньи». Физический журнал A: Математический и теоретический . 50 (11): 115001. arXiv : 1606.01560 . Бибкод : 2017JPhA...50k5001T. дои : 10.1088/1751-8121/aa5af3. S2CID  118850609.
45. Тишби, Идо; Бихам, Офер; Кацав, Эйтан (2016). «Распределение длин путей самоизбегающих блужданий в сетях Эрдеша – Реньи». Физический журнал A: Математический и теоретический . 49 (28): 285002. arXiv : 1603.06613 . Бибкод : 2016JPhA...49B5002T. дои : 10.1088/1751-8113/49/28/285002. S2CID  119182848.
46. Бурда, З.; Дуда, Дж.; Удача, Дж. М.; Вацлав, Б. (2009). «Локализация случайного блуждания с максимальной энтропией». Письма о физических отзывах . 102 (16): 160602. arXiv : 0810.4113 . Бибкод : 2009PhRvL.102p0602B. doi : 10.1103/PhysRevLett.102.160602. PMID  19518691. S2CID  32134048.
47. Мадрас, Нил и Слэйд, Гордон (1996) Прогулка самоизбегания , Birkhäuser Boston. ISBN 0-8176-3891-1 . 
48. Хеммер, С.; Хеммер, ПК (1984). «Среднее самоизбегающее случайное блуждание по квадратной решетке длится 71 шаг». Дж. Хим. Физ . 81 (1): 584–585. Бибкод : 1984JChPh..81..584H. дои : 10.1063/1.447349 .
49. Лоулер, Грегори (1996). Пересечение случайных блужданий , Биркхойзер Бостон. ISBN 0-8176-3892-X . 
50. Лоулер, Грегори Конформно-инвариантные процессы на плоскости , book.ps.
51. Пемантл, Робин (2007). «Обзор случайных процессов с подкреплением» (PDF) . Вероятностные исследования . 4 : 1–79. arXiv : math/0610076 . дои : 10.1214/07-PS094. S2CID  11964062.
52. Аламгир, М. и фон Люксбург, У (2010). «Многоагентные случайные блуждания для локальной кластеризации на графах». Архивировано 15 апреля 2012 года в Wayback Machine , 10-я Международная конференция IEEE по интеллектуальному анализу данных (ICDM) , стр. 18–27.
53. Бове, Пьер; Бенаму, Саймон (1988). «Пространственный анализ движений животных с использованием коррелированной модели случайного блуждания». Журнал теоретической биологии . 131 (4): 419–433. Бибкод : 1988JThBi.131..419B. дои : 10.1016/S0022-5193(88)80038-9.
54. Карейва, премьер-министр; Шигесада, Н. (1983). «Анализ движения насекомых как коррелированного случайного блуждания». Экология . 56 (2–3): 234–238. Бибкод : 1983Oecol..56..234K. дои : 10.1007/BF00379695. PMID  28310199. S2CID  20329045.

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

• Олдос, Дэвид ; Заполните, Джеймс Аллен (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), «Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz». Архивировано 4 марта 2016 г. в Wayback Machine , Mathematische Annalen , 84 (1–2): 149–160, март 1921 г.
• Ревес, Пал (2013), Случайное блуждание в случайной и неслучайной среде (третье издание) , ISBN World Scientific Pub Co. 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