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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Одномерное дискретное случайное блуждание — это случайный процесс с дискретным временем, имеющий вид

,

где

  •  — начальное состояние;
  • ;
  • случайные величины совместно независимы.

Случайное блуждание как цепь Маркова[править | править вики-текст]

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

,

то есть

Общее определение[править | править вики-текст]

Пусть последовательность независимых случайных величин со значениями в и одинаковыми распределениями. Тогда случайный процесс заданный последовательностью

называется случайным блужданием в или d-мерным случайным блужданием.[1] Случайное блуждание это дискретный случайный процесс с независимыми стационарными приращениями.

Теорема Донскера[править | править вики-текст]

Рассмотрим случайное блуждание , где .

Центральная предельная теорема утверждает, что по распределению при .

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

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

Из центральной предельной теоремы по распределению при

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

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

Применение в оптимизации[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Bert Fristedt, Lawrence Gray: A modern approach to probability theory. Birkhäuser, Boston/Basel/Berlin 1997, ISBN 978-0-8176-3807-8, S. 165.
  2. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.

См. также[править | править вики-текст]