Метод статистических испытаний

Численный метод решения математических задач при помощи моделирования случайных величин называется методом статистических испытаний, или методом Монте-Карло. В основе метода лежит следующий факт: если имеется механизм генерирования (розыгрыша) значений равновероятно распределенной на отрезке [0; 1] случайной величины, то легко получить случайные значения другой случайной величины, распределенной по любому заданному закону.

Генерирование значений равновероятно распределенной случайной величины осуществляется с помощью так называемых датчиков псевдослучайных чисел. Сегодня практически в каждом алгоритмическом языке или пакете прикладных программ имеется стандартная процедура генерирования случайных чисел. Так, например, в программах, написанных на языке Pascal, достаточно написать п := rand, и п будет присвоено одно из значений псевдослучайного числа. Рассмотрим механизм метода статистических испытаний.

Розыгрыш значений непрерывной случайной величины. Поставим задачу получить значения Е, случайной величины X, распределенной на отрезке [а; Ь], с плотностью вероятности Дх).

При заданном законе распределения вероятность попадания случайной величины X в интервал [а; ?) находится по известной формуле.

Это выражение можно рассматривать в качестве уравнения относительно неизвестной Е,. Покажем, что величина Е, являющаяся корнем уравнения (19.1), имеет плотность вероятности Дх) [14].

Функция распределения случайной величины X монотонно возрастает от 0 до 1.

Следовательно, прямая у = г| (рис. 19.1) пересекает графику = = у (х) в одной единственной точке, абсциссу которой принимаем за 4- Тем самым доказано, что уравнение (19.1) имеет единственное решение.

Рис. 19.1. Розыгрыш непрерывной случайной величины.

Выберем произвольный интервал (с; d), содержащийся в отрезке [а; Ь]. В связи с монотонностью функции у (х) любой точке с <�х < d соответствует ордината кривой у = у (х), удовлетворяющая неравенству у© <�у.

Предположим, что случайная величина ц на интервале (0; 1) распределена равномерно. В этом случае.

Сравнивая это выражение с равенством (19.2), получим.

Соотношение (19.4) показывает, что величина Ъ, имеет плотность вероятности fix'). Этот факт является основанием для построения следующей схемы получения случайного значения непрерывной случайной величины X, имеющей заданный закон распределения/(х).

1. Генерируется г — значение случайной величины, равномерно распределенной на отрезке [0; 1].

2. Записывается уравнение и решается относительно искомой величины Пример 19.1.

Розыгрыш равномерного распределения на произвольном отрезке [а; Ь]. Пусть задано распределение.

Составляем уравнение.

Отсюда легко получить искомый результат:

Пример 19.2.

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

окончательная формула имеет следующий вид:

Таким образом, чтобы разыграть случайную величину, распределенную по экспоненциальному закону, необходимо разыграть значение г| случайной величины, равновероятно распределенной на отрезке [0; 1], а затем подставить его в формулу (19.6).

Для более сложных распределений аналитически решить уравнение типа (19.5) не удается. Поэтому используют таблицы функций распределений. Так же разыгрывают равномерно распределенную величину г|, а затем по таблице ищут величину удовлетворяющую условию = argF (r|).

Розыгрыш значений дискретной случайной величины. Пусть заданы значения вероятностей для некоторой дискретной случайной величиныX: p (Xj), р (х₂),…, р (х_п). Ставится задача случайным образом выбрать одно из возможных значений X, учитывая ее распределение.

Идея решения данной задачи основана на попадании случайной точки в один из интервалов, каждый из которых имеет длину, пропорциональную величине соответствующей вероятности р (х,), i = 1, …, п.

Вначале, как всегда в методе Монте-Карло, генерируется ц — значение случайной величины равновероятно распределенной на отрезке [0; 1]. Затем находится искомая величина по правилу.

Логику этого правила иллюстрирует рис. 19.2. Случайная точка всегда попадает в один из возможных интервалов. В какой? Приведенное правило позволяет последовательно просматривать отношения нарастающей суммы вероятностей к их общей сумме. Считается выбранным то значение х_к, для которого впервые выполнится условие в формуле (19.7).

Рис. 19.2. Розыгрыш дискретной случайной величины.

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

Пример 19.3.

Имеются четыре альтернативы х_1; х₂, х₃, х₄ с весами q (xj) = 13, q(х₂) = 7, q (x₃) = 11 и q (x₄) = 3. Какая альтернатива будет выбрана, если выпало ц = 0,73?

Решение. В соответствии с формулой (19.7) имеем:

Таким образом, выбрана третья альтернатива. Если бы выпало ц = 0,59, то был бы выбран тот же вариант, а вот если ц = 0,27, то первый и т. д.

Пример применения метода статистических испытаний.

Пусть в данный прямоугольник вписана некоторая сложная фигура (рис. 19.3). Требуется определить площадь вписанной фигуры.

Рис. 19.3. Определение площади методом статистических испытаний.

Решение этой задачи при помощи метода статистических испытаний может происходить по следующей схеме. Реализуется механизм попадания в прямоугольник: разыгрываются случайные значения равновероятно распределенных случайных чисел из интервалов (а; Ь) и (с; d), которые выступают координатами случайной точки. Всего разыгрываются N точек. Из них Nj попадает во вписанную фигуру, a N₂ — вне ее QV = JVj + ЛГ₂). За площадь фигуры S принимается отношение числа точек, попавших в фигуру, к общему числу разыгранных точек: S = N^/N.

Сколько розыгрышей (точек М) необходимо произвести, чтобы обеспечить заданную точность е? Обычно поступают следующим образом. Производится серия из достаточно представительного числа розыгрышей точек (к шт.), в результате чего получается результат S_k. Затем серия повторяется, и если.

то S_2k принимается за конечный результат. В противном случае серии повторяются до тех пор, пока два последних результата не дадут отличие менее, чем е.

Формальную оценку числа розыгрышей можно получить и на основании следующих рассуждений. Пусть требуется вычислить неизвестную величину р. Предположим, что имеется такая случайная величина х, что М (Х) = р и D (X) = а². Сгенерируем N значений случайной величины X. Согласно центральной предельной теореме распределение суммы.

приближается к нормальному с параметрами p_N и ah . Применяя правило трех сигм, получаем приближенное равенство.

или в более компактной форме.

Данное соотношение говорит о том, что среднее значение сгенерированной случайной величины с очень высокой вероятностью равно р. При этом ошибка не превосходит величины 3a/ViV, стремящейся к нулю при возрастании N. Важно подчеркнуть, что выражение (19.8) позволяет оценить число розыгрышей N, которое обеспечивает получение такой точности.

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