Сущность метода Монте-Карло.

Одним из численных методов, получивших распространение при появлении быстродействующих электронных вычислительных машин (ЭВМ), является метод статистических испытаний, или метод Монте Карло. Он базируется на использовании так называемых случайных чисел — возможных значений некоторой случайной величины с заданным распределением вероятностей.

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

Сущность метода статистических испытаний поясним на примерах.

В качестве первого примера рассмотрим вычисление площади некоторой фигуры произвольной формы. Остановимся сначала на частном случае решения этой задачи. Пусть требуется вычислить площадь фигуры (см. рис. 1), ограниченной отрезками ОА и на осях прямоугольных координат ОХ и ОУ, кривой и ординатой (искомая площадь на рис. 1 заштрихована), причем будем считать выполненным условие для всех

Рис. 1.

Пользуясь обычными численными методами для приближенного вычисления искомой площади, поступают следующим образом. Разбивают отрезок (0,1) на оси ОХ на равных частей длиной Искомую площадь 5 представляют в виде суммы площадей элементарных фигур, как показано на рис. 2. Площадь каждой

элементарной фигуры приближенно можно заменить площадью соответствующего прямоугольника, равной где некоторая точка на оси внутри интервала. Точки выбирают таким образом, чтобы площадь - прямоугольника была возможно более близкой к площади элементарной фигуры. Очевидно, что при достаточно большом точность вычисления площади можно сделать вполне приемлемой.

Рис. 2.

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

Посмотрим теперь, как решается эта же задача методом статистических испытаний. Пусть мы имеем случайную величину равномерно распределенную на отрезке [0, 1] (см. [5]). Это значит, что вероятность попадания ее возможных значений в интервал пропорциональна длине интервала и не зависит от местоположения его на отрезке [0, 1].

Если возможные значения равномерно распределенной случайной величины заполняют отрезок [0, 1] на оси и возможные значения у случайной величины ) заполняют тот же отрезок на оси то пары чисел определяют случайную точку на плоскости имеющую равномерное распределение в квадрате (0,0), (0,1), (1,1), (1,0), который мы в дальнейшем будем называть единичным квадратом. Это значит, что вероятность попадания точки в некоторую область а пропорциональна площади этой области и не зависит от расположения ее внутри единичного квадрата.

Рис. 3.

Проведем мысленный эксперимент: внутрь единичного квадрата случайным образом с равномерным распределением бросается точка. Это эквивалентно выборке пары чисел являющихся возможными значениями соответственно. После N таких испытаний (где N достаточно велико) на плоскости появится N случайно расположенных точек, равномерно распределенных в единичном квадрате (см. рис. 3).

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

Если следовать геометрическим соображениям, ясно, что вероятность Р попадания точки в часть квадрата, находящуюся под кривой равна отношению площади этой части квадрата к площади всего квадрата. Частота попадания точки в часть квадрата под кривой при достаточно большом близка к вероятности Р (см. [5]). Отсюда следует, что в качестве приближенного значения искомой площади можно взять частоту т. е.

Для решения рассмотренного примера на ЭВМ нет необходимости в воспроизведении всех указанных выше действий. Сущность метода статистических испытаний для данного случая состоит в моделировании эксперимента при помощи случайных чисел.

Процедура решения выглядит следующим образом:

1. Выбирается случайное число из отрезка [0; 1] с равномерным законом распределения (из таблиц случайных чисел или вырабатывается самой машиной с помощью датчика случайных чисел); это случайное число принимается в качестве координаты случайной точки на оси

2. Вычисляется значение рассматриваемой функции в точке

3. Вырабатывается следующее случайное число принимаемое в качестве координаты точки на оси О У; таким образом и определяют случайную точку на плоскости внутри единичного квадрата.

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

5. Значение функции сравнивается со случайным числом Если неравенство (см. рис. 3)

выполнено, что соответствует попаданию случайной точки в часть квадрата под кривой то результату сравнения присваивается специальный признак если не выполнено

6. Полученные значения признака (о прибавляются к содержимому счетчика количества точек под кривой

7. Управление передается снова первой операции, что соответствует переходу к новой случайной точке После проведения N таких экспериментов определяется приближенное значение площади под кривой:

Рассмотренная процедура не требует запоминания всех случайных чисел, полученных в результате эксперимента. Запоминаются только значения и N. Это немаловажное обстоятельство вообще характерно для реализации метода статистических испытаний на ЭВМ.

Точность решения задачи методом статистических испытаний растет с увеличением количества испытаний N и при достаточно больших N становится приемлемой с практической точки зрения. (Этот вопрос будет более обстоятельно выяснен ниже, в § 5.)

Целесообразно обратить внимание на ряд возможных обобщений.

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

Тогда квадрат АВЕД будет единичным, а искомая площадь

где 5 — площадь фигуры, выраженная в единицах измерения, соответствующих новым масштабам.

Величина 5 может быть определена методом статистических испытаний.

Рис. 4.

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

причем выбирается уже не из отрезка [0,1], а из преобразованного (сдвинутого) единичного отрезка.

Если это неравенство выполнено, случайная точка находится внутри контура фигуры и тогда

Во-вторых, задача вычисления площади является частным случаем более общей задачи интегрального исчисления. В самом деле, площадь 5 (см. рис. 3) может быть выражена как

поэтому процедура определения площади одновременно является процедурой вычисления интеграла вида (1.4). Напомним, что здесь

Если же это условие не выполнено и пределы интегрирования произвольны, необходимо преобразовать масштабы по осям координат. Например, пусть требуется вычислить интеграл

где максимальное значение в отрезке [а, Ь] равно Используя замену переменных

и изменение масштаба по оси у, получим

где

Таким образом, рассматриваемая задача сводитсяс к предыдущей, решаемой с помощью интеграла вида (1.4).

77. Прикладные задачи определения характеристик случайного процесса. Методы решения.

Анализ единственности решения задачи оценивания параметров случайного процесса по данным наблюдений начнем с примера.

Пример 9.4. Рассмотрим скалярный случайный процесс

где — стационарный гауссовский случайный процесс с нулевым математическим ожиданием и ковариационной функцией а — известный параметр, а — неизвестные положительные параметры.

В данном случае вектор неизвестных параметров образован четырьмя компонентами При имеем

а случайный процесс , представляет собой скалярный гауссовский процесс.

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

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

Оценку параметра можно строить на двух очевидных равенствах:

В качестве реализации такой оценки используем функцию [XVII]

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

Эта система состоит из двух уравнений и содержит три неизвестных параметра, т.е. имеет бесчисленное множество решений.

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

Если а система (9.29) имеет решение, удовлетворяющее условиям положительности своих компонент, то это решение единственно.

Заметим, что рассматриваемый скалярный случайный процесс при становится стационарным случайным процессом с математическим ожиданием и дисперсией Пусть теперь — момент времени, начиная с которого исходный случайный процесс можно считать стационарным. Если принять за начало наблюдений, то параметры и оценить невозможно, как бы мы ни выбирали моменты измерений и сколько бы измерений ни проводилось в эти моменты времени, поскольку стационарные изменения состояния не зависят от значений параметров

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

содержит исчерпывающую информацию об исходном случайном процессе на множестве

Определение 9.1. Пусть — -мерный случайный процесс, зависящий от -мерного вектора неизвестных параметров Говорят, что -мерная функция плотности вероятностей определяет на исходный случайный процесс единственным образом, если равенство

верно тогда и только тогда, когда

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

где

блочный случайный вектор размерности Нас интересует экстремум этой функции.

В связи с этим напомним, что функцию называют выпуклой («низ) на множестве X, если для любых и для любого имеет место неравенство

Известно [V], что для выпуклой (дифференцируемой) функции справедливо неравенство

Пусть — случайный вектор . В этом случае

Определив математические ожидания правой и левой частей этого неравенства, приходим к неравенству Иенсена для выпуклой функции:

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

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

где функция определена равенством (9.30).

Поскольку — выпуклая функция, то по неравенству Иенсена имеем

или, что то же самое,

где так как для любого

то последнее неравенство принимает вид

Это неравенство превращается в равенство тогда и только тогда, когда

Поэтому из неравенства (9.31) и условия теоремы получаем, что для любых

или, что то же самое,

Таким образом, функция имеет на В единственный максимум в точке что и требовалось доказать.

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

Рассмотрим этот случай, поскольку он чаще других встречается в приложениях. Будем считать, что при содержат все интересующие нас параметры. Это означает, что вся интересующая нас информация об изучаемом случайном процессе представлена в совокупности его одномерных функций плотности вероятностей Отсюда следует, что для решения задачи оценивания его неизвестных параметров вполне подходит случайная выборка, соответствующая множеству функция плотности вероятностей которой определена равенством (9.18):

Для того чтобы выяснить достаточность зтих данных для однозначного оценивания неизвестных параметров, рассмотрим следующую функцию плотности вероятностей

и введем множества

При выполнении условий теоремы 9.1 при любых имеем

т.е. с учетом определения функции

или

Однако по условию задачи вид функции плотности вероятностей неизвестен. Тем не менее, задачу можно решить, если в качестве использовать плотность нормального закона распределения и наложить на функции дополнительные ограничения.

Определение 9.2. Будем говорить, что функции разделяют точки множества В на множестве , если для любых существует хотя бы одно значение такое, что

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

где

— плотность нормального распределения:

— неизвестная истинная одномерная функция плотности вероятностей случайного процесса.

Доказательство теоремы 9.2 опирается на следующее утверждение.

Лемма 9.1. Пусть — -мерный случайный вектор с функцией плотности вероятностей математическим ожиданием и ковариационной матрицей — плотность распределения вероятностей -мерного случайного вектора, распределенного по нормальному закону с математическим ожиданием то и ковариационной матрицей Е. Тогда для любых то и таких, что то , верно неравенство

Докажем, что

Действительно,

где

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

то очевидны равенства

При этом тогда и только тогда, когда Таким образом,

т.е. при любых то имеем

Теперь вернемся к доказательству теоремы 9.2.

Функция

при достигает максимума, так как при

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

Этот максимум является единственным, т.е. для любого a G В, такого, что имеем

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

а значит, для соответствующих ему слагаемых в суммах неравенства (9.33) будем иметь

Поэтому для любого , такого, что а имеем

а следовательно,

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

Из теоремы 9.2 вытекает весьма важное следствие, состоящее в том, что в тех случаях, когда конечномерные функции плотности вероятностей исходного случайного процесса неизвестны, для решения задачи оценивания можно использовать функции плотности вероятностей нормального закона распределения.

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

Прежде чем перейти к анализу методов оценивания неизвестных параметров изучаемых случайных процессов, отметим, что пример 9.4 наглядно иллюстрирует идею метода моментов [XVII]. Эта идея состоит в том, что для нахождения оценок неизвестных параметров исходного случайного процесса составляют систему уравнений путем приравнивания теоретических моментов, являющихся функциями неизвестных параметров, к соответствующим статистическим моментам, которые являются функциями данных наблюдений. Метод моментов далее мы рассматривать не будем.