Тема 3.1.3. Моделирование стохастических процессов

Основные понятия и термины по теме:

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

1. Создание материалов;

2. Понятие рендеринга;

3. Методы рендеринга.

Краткое изложение теоретических вопросов:

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

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

В тех случаях, когда построение аналитической модели явления по той или иной причине трудно осуществимо, применяется другой метод моделирования, известный под названием метода статистических испытаний или, иначе, метода Монте-Карло.

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

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

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

Пример 1. Решается задача: по некоторой цели производится 4 независимых выстрела, каждый из которых попадает в нее с р=0,5. Для поражения цели требуется не менее двух попаданий. Определить вероятность поражения цели.

Аналитический способ. Вероятность поражения цели вычисляется через вероятность противоположного события. Вероятность непоражения цели = сумме вероятностей ни одного попадания и ровно одного попадания; вероятность ни одного попадания 0,5⁴; вероятность одного попадания равна:

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

.

Розыгрыш. Будем моделировать процедуру стрельбы с помощью другой, тоже случайной процедуры. Будем бросать 4 монеты: условимся - герб попадание, решка – промах. Цель поражена - не менее двух гербов. Розыгрыш в нашем случае – бросание четырех монет, результат этого опыта - «поражение или не поражение цели». Повторим такой опыт (бросание 4 монет) очень много раз подряд. Тогда согласно теореме Бернулли, частота поражения цели почти наверняка будет мало отличаться от вероятности этого события W; значит, если мы бросим четыре монеты большое число раз N, мы почти наверняка получим число близкое к W, т.е. к 0,688. В данном случае определение вероятности W розыгрышем было несравненно трудней, чем аналитическим расчетом.

Пример 2. Анализ поведения дискретного объекта (дискретные входные и выходные переменные) - «задача о пьяном прохожем или задача о случайном блуждании». Прохожий решил прогуляться, стоя на углу улиц. Пусть вероятность того, что, достигнув очередного перекрестка, он пойдет на север, юг, восток и запад, одинакова. Какова вероятность того, что пройдя 10 кварталов, прохожий окажется не далее 2 кварталов от места, где он начал прогулку.

Обозначим его местонахождение на каждом перекрестке двумерным вектором (x₁, x₂) («выход»), где x₁ – направление с востока на запад и x₂ – направление с севера на юг. Каждое перемещение на один квартал к востоку (x₁ + 1), а каждое перемещение на один квартал к западу (x₁ – 1) (x₁ - дискретная переменная). К северу x₂ + 1, к югу x₂ – 1. Начальное положение (0,0).

Если в конце прогулки абсолютные значения х₁ и х₂ будут больше 2, то будем считать, что он ушел дальше двух кварталов в конце прогулки протяженностью в 10 кварталов. Т.к. вероятность движения нашего прохожего в любом из 4 направлений по условию одинакова и равна 0,25, то можно оценить его передвижение с помощью таблицы случайных чисел. Условимся, что если случайное число (СЧ) лежит в пределах от 0 до 24, пьяный пойдет на восток и мы увеличим х₁ на 1; если от 25 до 49, то он пойдет на запад и х₁-1; если от 50 до 74, он пойдет на север и x₂ + 1; если от 75 до 99, то на юг и x₂ – 1.

Блок-схема поведения прохожего.

Нужно провести достаточно большое число «машинных опытов», чтобы получить достоверный результат. Другими методами такую задачу решить практически невозможно.

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

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

Заметим, что методом статистических испытаний можно находить не только вероятности событий, но и средние значения (математические ожидания) случайных величин. При этом применяется закон больших чисел (теорема Чебышева). Согласно этой теореме, при большом числе опытов среднее арифметическое наблюденных значений случайной величины почти наверняка мало отличается от её математического ожидания. Аналогичным образом могут быть найдены не только математические ожидания, но и дисперсии интересующих нас случайных величин.

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

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