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

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

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

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

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

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

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

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

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

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

Одномерное случайное блуждание [ править ]

Элементарным примером случайного блуждания является случайное блуждание по целочисленной строке , которое начинается с 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 (перевернув пять решек). На рисунке ниже показаны возможные результаты пяти сальто.

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

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

Этот результат показывает, что диффузия неэффективна для смешивания из-за того, как квадратный корень ведет себя для больших . ^{[ необходима цитата ]}${\displaystyle N}$

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

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

Некоторые из упомянутых выше результатов могут быть получены из свойств треугольника Паскаля . Количество различных прогулок из n шагов, где каждый шаг равен +1 или -1, равно 2 ⁿ . Для простого случайного блуждания каждое из этих блужданий одинаково вероятно. Для того, чтобы S _n равнялось числу k, необходимо и достаточно, чтобы количество +1 в прогулке превышало число -1 на k . Из этого следует, что +1 должен появиться ( n  +  k ) / 2 раза среди n шагов прогулки, следовательно, количество прогулок, которым удовлетворяют, равно количеству способов выбора ( n  +  k${\displaystyle S_{n}=k}$) / 2 элементов из n- элементного множества, ^[7] обозначено . Чтобы это имело смысл, необходимо, чтобы n  +  k было четным числом, что означает, что n и k либо оба четные, либо оба нечетные. Следовательно, вероятность того равна . Представляя элементы треугольника Паскаля в терминах факториалов и используя формулу Стирлинга , можно получить хорошие оценки этих вероятностей для больших значений .${\displaystyle n \choose (n+k)/2}$${\displaystyle S_{n}=k}$${\displaystyle 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.

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

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

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

Как цепь Маркова [ править ]

Одномерное случайное блуждание также можно рассматривать как цепь Маркова , пространство состояний которой задается целыми числами. Для некоторого числа 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 {\sqrt {n}}}$

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

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

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

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

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

Отношение к винеровскому процессу [ править ]

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

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

Случайное блуждание - это дискретный фрактал (функция с целыми размерностями; 1, 2, ...), но траектория винеровского процесса является истинным фракталом, и между ними существует связь. Например, совершите случайную прогулку, пока она не попадет в круг радиуса r, умноженного на длину шага. Среднее количество выполняемых шагов r ² . ^{[ Править ]} Этот факт является дискретная версия о том , что процесс Wiener ходьбы является фрактал размерности Хаусдорфа  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. Разница, связанная с каждым компонентом , или составляет только одну треть от этого значения (все еще в 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 из обратного кумулятивного нормального распределения со средним равным нулю и σ исходного обратного кумулятивного нормального распределения:

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

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

${\displaystyle {\mathcal {N}}}$(μ _X + μ _Y , σ ² _X + σ ² _Y ) (см. здесь) .

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

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

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

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

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

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

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

Аномальная диффузия [ править ]

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

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

Количество различных сайтов, которые посещает один случайный прохожий , широко изучалось для квадратных и кубических решеток и фракталов. ^{[18] [19]} Эта величина полезна для анализа задач захвата и кинетических реакций. Это также связано с колебательной плотностью состояний, ^{[20] [21]} процессами диффузионных реакций ^[22] и распространением популяций в экологии. ^{[23] [24]} Обобщение этой проблемы на количество различных сайтов, посещаемых случайными блуждающими , недавно было изучено для d-мерных евклидовых решеток. ^[25]${\displaystyle S(t)}$${\displaystyle N}$${\displaystyle S_{N}(t)}$ Количество различных сайтов, которые посетили 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]
• В психологии случайные прогулки точно объясняют связь между временем, необходимым для принятия решения, и вероятностью того, что оно будет принято. ^[41]
• Случайные блуждания можно использовать для выборки из пространства состояний, которое неизвестно или очень велико, например, чтобы выбрать случайную страницу в Интернете или, для исследования условий работы, случайного работника в данной стране. ^{[ необходима цитата ]}

• Когда этот последний подход используется в информатике, он известен как цепь Маркова Монте-Карло или сокращенно MCMC. Часто выборка из некоторого сложного пространства состояний также позволяет получить вероятностную оценку размера пространства. Оценка перманента большой матрицы нулей и единиц была первой серьезной проблемой, решаемой с использованием этого подхода. ^{[ необходима цитата ]}

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

Варианты [ править ]

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

На графиках [ править ]

Случайное блуждание длины 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}$

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

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

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

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

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

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

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

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

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

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

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

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

• Самоизбегающих ходьбы . ^[49]

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

• Петли стираются случайная ходьба . ^{[51] [52]}
• Армированный блуждание . ^[53]
• Процесс разведки . ^{[ необходима цитата ]}
• Мультиагентная блуждание . ^[54]

Коррелированные прогулки на большие расстояния [ править ]

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

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

Предвзятые случайные блуждания на графиках [ править ]

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

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

Коррелированные случайные блуждания [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Библиография [ править ]

• Олдос, Дэвид ; Заливка, Джеймс Аллен (2002). Обратимые марковские цепи и случайные блуждания на графах . Архивировано 27 февраля 2019 года.
• Бен-Авраам Д .; Хэвлин С. , Диффузия и реакции во фракталах и неупорядоченных системах , Издательство Кембриджского университета, 2000.
• Дойл, Питер Дж .; Снелл, Дж. Лори (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), Цепи Маркова , Cambridge University Press. ISBN 0-521-63396-6 
• Pólya G. (1921), "Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" , Mathematische Annalen , 84 (1-2): 149–160, март 1921 г.
• Ревес, Пал (2013), Случайное блуждание в случайных и неслучайных средах (третье издание) , World Scientific Pub Co. ISBN 978-981-4447-50-8 
• Сунада, Тошиказу (2012). Топологическая кристаллография: с точки зрения дискретного геометрического анализа . Обзоры и учебные пособия по прикладным математическим наукам. 6 . Springer. ISBN 978-4-431-54177-6.
• Вайс Г. Аспекты и приложения случайного блуждания , Северная Голландия, 1994.
• Woess, Вольфганг (2000), Случайные блуждания на бесконечных графах и группах , Кембриджские трактаты по математике 138, Cambridge University Press. ISBN 0-521-55292-3 

Внешние ссылки [ править ]

• Константы случайного блуждания Поли
• Случайное блуждание в Java-апплете
• Квантовое случайное блуждание
• Оценка гауссовского случайного блуждания
• Модели электронной проводимости с использованием случайных блужданий с максимальной энтропией Демонстрационный проект Wolfram Demonstrations Project