10.9.   МЕТОДЫ СЛУЧАЙНОГО БЛУЖДАНИЯ

Один общий метод получения произвольного неравномерного распределения вероятности был предложен Метрополисом, Розенблатом и Теллером в 1953 г. Метод Метрополией представляет собой частный случай процедуры выборки по значимости, в которой некоторые возможные выборки

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

Для простоты познакомимся с одномерным вариантом метода Метропо-лиса. Предположим, мы хотим сгенерировать случайные переменные с произвольной плотностью вероятности р(х). В методе Метрополиса моделируется «случайное блуждание» точек {х^, распределение которых после большого числа шагов асимптотически стремится к распределению вероятности р(х). Случайное блуждание определяется заданием вероятности перехода w(x.—*x.) от одного значения х. к другому—х., для того чтобы распределение точек xQ, Ху *2, ... сходилось к р(х). Можно показать, что достаточно (но ие необходимо) удовлетворить условию «детального баланса»

Соотношение (10.51) не определяет w(x[—*x) единственным образом. Рассмотрим простейший вариант w(x. — х.), который удовлетворяет условию (10.51):

Данный переход w(x.—*x.) можно описать следующими шагами. Предположим, что «пешеход» находится в точке с координатой хп. Для формирования *п+1:

Выбираем   пробную   координату   х( = хп + б^,   где   б^—случайное число иа отрезке [-6, б].

Вычисляем w - р(х )/р(х ).

Если w * 1, принимаем этот переход и полагаем *n+1 = xf

Если w < 1, генерируем случайное число г.

Если г £ ш, принимаем этот переход и полагаем *п+1 = х{.

Если пробный переход не принят, то полагаем *п+1 = хп.

Прежде чем сформируется асимптотическое распределение вероятности с плотностью р(х), необходимо произвести выборку ряда точек случайного блуждания. Каким выбрать максимальный «размер шага» б? Если б слишком велико, то будет приниматься малая часть пробных шагов и выборка р{х) будет неэффективна.  С другой стороны,  если б слишком

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