Метод Монте-Карло

В основе метода Монте-Карло лежат способы генерации псевдослучайных чисел (чисел из детерминированной последовательности с гигантским периодом повторения) [32]. Главным положением метода является следующее: значение любой случайной величины можно получить путем преобразования одной какой-либо «стандартной» (с известным законом распределения) случайной величины. Благодаря максимальной средней простоте преобразований, в качестве стандартной используют случайные величины с равномерным законом распределения на интервале (0,1). Этим и объясняется наличие практически во всех языках программирования высокого уровня процедур генерации равномерных случайных чисел.

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

Интервальный подход заключается в следующем. Пусть имеется датчик случайной величины , равномерно распределенной на интервале (0,1). Необходимо получить случайную величину с распределением

 

,

где - возможные значения случайной величины, {p_i}_1,n - соответствующие им вероятности.

Для этого интервал значений (0,1) разбивают на n интервалов, длины которых соответственно равны . В каждом опыте разыгрывают значение . Если оно попадает в интервал с номером i, то счи­тают и т.д.

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

 

Рис.5.9. Иллюстрация к принципу генерации случайных величин по методу обратных функций

 

Он состоит в разыгрывании случайной величины n по формуле

(5.45)

 

или эквивалентной формуле , где x=g(y) - функция, обратная y=F(x), для которой при всех и при всех 0<y<1 справедливо

 

.

 

Доказательство того, что случайная величина v имеет функцию распределения F(x) следующее. Так как

 

 

и т.к. - равномерно распределена в интервале (0,1), то функция равна длине интервала (0,F(x))=F(x). Отсюда следует , что и требовалось доказать.