ПРИЛОЖЕНИЕ 10В. МЕТОД ОТБОРА-ОТКАЗА

Хотя метод обратного преобразования, рассмотренный в разд. 10.7, в принципе можно использовать для генерирования любого требуемого распределения вероятностей, на практике это метод ограничивается функциями, для которых обратное преобразование Р \г) можно найти аналитически или с помощью несложного численного приближения. Другим методом генерирования неравномерных распределений вероятностей является метод отбора-отказа, предложенный фон Нейманом. В основе этого метода лежит простое геометрическое соображение, применяемое при вычислении определенных интегралов методом проб и ошибок, который обсуждался в разд. 10.4.

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

Одна из процедур генерирования случайных точек (х,у), равномерно распределенных под заданной функцией сравнения w(x), заключается в следующем:

Выбираем w(x). В качестве одного из вариантов выбора можно подобрать такую w(x), чтобы значения х, распределенные в соответствии с w(x), можно было бы генерировать методом обратного преобразования. Пусть полная площадь под кривой w(x) равна А.

Генерируем равномерно распределенное случайное число на отрезке [О, А] и используем его для получения соответствующего значения х, распределенного согласно w(x).

Для значения х, сгенерированного на шаге 2, получаем равномерно распределенное на отрезке [0, ьу(х)] случайное число у. Точка (х,у) равномерно распределена по площади, расположенной под функцией сравнения w(x). Если у £ р(х), то х принимается в качестве случайного числа, распределенного в соответствии с р(х).

Конечно, шаги 2 и 3 нужно много раз повторить.

Заметим, что метод отбора-отказа эффективен, только если функция сравнения w(x) близка к р(х) на всем рассматриваемом интервале.