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

Введение

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

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

Сетчатая случайная ходьба

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

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

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

Более высокие размеры

В более высоких измерениях набор случайно пройденных точек обладает интересными геометрическими свойствами. Фактически, получается дискретный фрактал, то есть множество, демонстрирующее стохастическое самоподобие в больших масштабах. В малых масштабах можно наблюдать "изрезанность", возникающую из-за сетки, на которой выполняется случайное блуждание. Траектория случайного блуждания – это совокупность посещенных точек, рассматриваемая как множество без учета времени прибытия в точку. В одном измерении траектория – это просто все точки между минимальной и максимальной высотой, достигнутой блужданием (обе, в среднем, порядка √N). Чтобы визуализировать двумерный случай, можно представить человека, случайно гуляющего по городу. Город практически бесконечен и расположен в виде квадратной сетки тротуаров. На каждом перекрестке человек случайно выбирает один из четырех возможных маршрутов (включая тот, с которого он пришел). Формально это случайное блуждание по множеству всех точек на плоскости с целочисленными координатами. Чтобы ответить на вопрос, вернется ли человек к исходной точке блуждания, это двумерный эквивалент проблемы пересечения уровня, обсуждавшейся выше. В 1921 году Джордж Поля доказал, что человек почти наверняка вернется в двухмерном случайном блуждании, но для трех и более измерений вероятность возвращения к началу уменьшается с увеличением числа измерений. В трех измерениях вероятность снижается примерно до 34%. Математик Шидзуо Какутани был известен тем, что ссылался на этот результат следующей цитатой: "Пьяный человек найдет дорогу домой, но пьяная птица может заблудиться навсегда". Другой вариант этого вопроса, который также задавал Поля: "Если два человека выйдут из одной и той же начальной точки, встретятся ли они когда-нибудь снова?". Можно показать, что разница между их местоположениями (две независимые случайные прогулки) также является простым случайным блужданием, поэтому они почти наверняка встретятся снова в двумерном блуждании, но для трех и более измерений вероятность уменьшается с увеличением числа измерений. Пол Эрдош и Сэмюэл Джеймс Тейлор также показали в 1960 году, что для измерений, меньших или равных 4, две независимые случайные прогулки, начинающиеся из любых двух заданных точек, почти наверняка имеют бесконечно много пересечений, но для измерений, больших 5, они почти наверняка пересекаются лишь конечное число раз. Асимптотическая функция для двухмерного случайного блуждания при увеличении числа шагов задается распределением Рэлея. Распределение вероятности является функцией радиуса от начала координат, а длина шага постоянна для каждого шага. Здесь длина шага считается равной 1, N – общее число шагов, а r – радиус от начала координат.

In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete fractal, that is, a set which exhibits stochastic self similarity on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed. The trajectory of a random walk is the collection of points visited, considered as a set with disregard to when the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height and the maximum height the walk achieved (both are, on average, on the order of ). To visualize the two dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the plane with integer coordinates. To answer the question of the person ever getting back to the original starting point of the walk, this is the 2 dimensional equivalent of the level crossing problem discussed above. In 1921 George Pólya proved that the person almost surely would in a 2 dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%. The mathematician Shizuo Kakutani was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever". Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?" It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2 dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. Paul Erdős and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often. The asymptotic function for a two dimensional random walk as the number of steps increases is given by a Rayleigh distribution. The probability distribution is a function of the radius from the origin and the step length is constant for each step. Here, the step length is assumed to be 1, N is the total number of steps and r is the radius from the origin.

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

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

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

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

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

Варианты

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

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

Существует ряд интересных моделей случайных путей, в которых каждый шаг сложным образом зависит от предыдущих. Все они сложнее для аналитического решения, чем обычное случайное блуждание, однако поведение любой модели случайного блуждателя можно исследовать с помощью компьютеров. Примеры включают:
Самоизбегающее блуждание. Самоизбегающее блуждание длиной n на – это случайный путь из n шагов, начинающийся в начале координат, совершающий переходы только между соседними узлами в , никогда не посещающий один и тот же узел повторно и выбираемый равномерно среди всех таких путей. В двух измерениях, из-за эффекта самозапирания, типичное самоизбегающее блуждание очень короткое, в то время как в более высоких измерениях оно растет неограниченно. Эта модель часто используется в физике полимеров (с 1960-х годов). Блуждание с удалением петель. Усиленное случайное блуждание. Процесс исследования. Многоагентное случайное блуждание.

Максимальная энтропия случайного ходьбы

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

Коррелированные случайные прогулки

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