Моделирование стохастических систем

МОДЕЛИРОВАНИЕ СТОХАСТИЧЕСКИХ СИСТЕМ Под стохастическими будем понимать системы, процесс эволюции которых имеет случайный характер, т.е. такие, в которых результат развития системы не детерминирован полностью влияющими на нее факторами. Для описания явлений с неопределенным исходом используется идея случайности. Согласно ей, результат таких явлений как бы определяется неким случайным выбором, случайным испытанием («природа бросает кости»). Когда изменения происходят при полной неизменности условий, в которых протекает явление (случайная изменчивость), мы объясняем это случайностью. Однако, поскольку идеальной неизменности достичь невозможно, сохраняется логическая возможность отрицать случайность и объяснять неопределенность результата воздействием неизвестных и неучтенных факторов. Статистический подход к изучению явлений заключается в мысленном разделении наблюдаемой изменчивости на две части – обусловленные закономерными и случайными причинами, и выявлении закономерной изменчивости на фоне случайной. С другой стороны, случайные события могут не только мешать изучать закономерности – они могут сами порождать их. Поведение молекул газа носит случайный характер, однако давление газа строго постоянно. Изучением закономерностей, порождаемых случайными событиями, занимается теория вероятностей. Вероятность события – это числовая мера его правдоподобия, объективной возможности его появления. Приближенно, это отношение числа появлений данного события к числу испытаний, если число испытаний достаточно велико (теорема Бернулли). Случайными величинами называют величины, принимающие в ходе случайных испытаний заранее неизвестные значения. Дискретной случайной величиной (ДСВ) называется такая случайная величина, множество возможных значений которой конечно, либо счетно. Непрерывной случайной величиной (НСВ) называется такая случайная величина, множество значений которой может принять любое значение из некоторого интервала. Появление тех или иных значений случайной величины можно рассматривать как события, которым в общем случае соответствуют различные вероятности. Полное представление о случайной величине дает закон ее распределения. Законом распределения ДСВ называется соотношение, устанавливающее связь между возможными значениями случайной величины и соответствующими вероятностями. Для НСВ X закон распределения задается либо интегральной функцией распределения F(x), задающей вероятность того, что случайная величина X принимает значение, меньшее x, либо, чаще, плотностью вероятности f(x) = F’(x). <Примеры законов распределения: равномерное, нормальное распределения> Наиболее важные свойства распределения задаются числовыми характеристиками: математическим ожиданием, дисперсией и др. Говорят, что в системе происходит случайный процесс, если она с течением времени может переходить из состояния в состояние под действием случайных факторов. МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ В ряде случаев, когда аналитическое решение стохастической задачи получить не удается, используют метод статистических испытаний (метод Монте-Карло). Основная идея этого метода состоит в следующем: вместо аналитического решения задачи либо проводят испытания, непосредственно рассматриваемые в задаче, либо эти испытания заменяют другими, имеющими с исходными одинаковую вероятностную структуру. Иначе говоря, рассматриваемые в задаче случайные явления имитируют, моделируют другими случайными явлениями. Определённые по результатам достаточно большого числа испытаний характеристики случайных явлений (относительные частоты, средние арифметические) используют в качестве приближенного решения задачи (в качестве оценок вероятностей, математических ожиданий). Допустимость этого приближения основывается на законе больших чисел. Так как достаточно высокая точность решения при использовании метода статистических испытаний гарантируется, как правило, только при проведении большого числа испытаний, этот метод практически можно реализовать только на ЭВМ. Метод статистических испытаний применяют для решения не только тех задач, в которых в явном виде имеются случайные явления, но также и для решения других математических задач. В этом случае искусственно подбирают такое случайное явление, характеристики которого связаны с результатом решения исходной задачи. Для определения числовых значений этих характеристик используется метод статистических испытаний. МОДЕЛИРОВАНИЕ СЛУЧАЙНОЙ ВЕЛИЧИНЫ С РАВНОМЕРНЫМ РАСПРЕДЕЛЕНИЕМ НА ОТРЕЗКЕ [0,1] Как для реализации метода статистических испытаний, так и в других ситуациях, связанных с изучением стохастических систем, требуется иметь возможность получения последовательности случайных чисел. Оказывается, что для имитации на ЭВМ случайных явлений самой различной природы достаточно иметь возможность получения на компьютере последовательности значений случайной величины, равномерно распределенной на отрезке [0,1]. Напомним, непрерывная случайная величина X имеет равномерное распределение на отрезке [a,b], если её плотность вероятности Случайную величину с равномерным распределением на отрезке [0,1] будем обозначать через R. Имеем Физические генераторы. Физическим генератором (датчиком случайного двоичного разряда) называется специальное приспособление к ЭВМ, в котором результаты случайного физического процесса преобразуются в последовательность случайной величины Х с распределением {0/0,5; 1/0,5}. Это, например, генераторы, использующие случайный процесс радиоактивного распада. Пусть в ЭВМ имеется какой-либо источник излучения радиоактивных частиц. Счетчик подсчитывает количество радиоактивных частиц за некоторое время t. Если число частиц четное, то в разряд посылается единица, если нечетное, то нуль. При параллельной работе k генераторов будет получено значение k-разрядной двоичной дроби, приближенно равной случайной величине R. Время t выбирается таким, чтобы вероятность получения в разряде единицы, так же как и вероятность получения нуля, была равна 0,5. Псевдослучайные последовательности чисел. Возможен следующий подход к моделированию случайной величины R, имеющей равномерное распределение на отрезке [0,1], не требующий дополнительных приставок к компьютеру. При этом подходе получают с помощью некоторой рекуррентной формулы последовательность чисел, обладающих статистическими свойствами, близкими к свойствам равномерного распределения на отрезке [0,1]. Поскольку эти числа получены алгоритмически, то они не являются случайными, и такую последовательность чисел называют псевдослучайной. Один из первых методов получения псевдослучайной последовательности чисел был предложен Дж. Нейманом. Он называется методом середины квадратов. Поясним его на примере. Возьмем некоторое число . Пусть =0,9876. Возведем его в квадрат (=0,97535376). Выберем четыре средние цифры этого числа и положим =0,5353. Затем возводим в квадрат (=0,28654609) и снова выбираем четыре средние цифры. Получаем =0,6546. Далее находим =0,42850116, =0,8501, =0,77267001, =0,2670 и т.д. Последовательность чисел , , … является псевдослучайной. Существуют и другие алгоритмы образования псевдослучайной последовательности, например, линейно-конгруэнтный метод. Метод псевдослучайных последовательностей прост и экономичен: он не требует разработки специальных приспособлений к ЭВМ, и при использовании его на получение каждого числа затрачивается всего несколько простых операций. Однако этот метод имеет ряд существенных недостатков, главным из которых является трудность теоретической оценки статистических свойств псевдослучайной последовательности. Обычно для оценки степени приближения этой последовательности к последовательности случайных чисел с равномерным распределением используют систему статистических критериев. При этом исследуют лишь сравнительно «небольшие участки» последовательности псевдослучайных чисел. В практических же задачах, решаемых методом статистических испытаний, количество используемых случайных чисел чрезвычайно велико. Помимо этого, числа, входящие в вырабатываемую программным способом псевдослучайную последовательность, зависимы между собой, а сама последовательность является периодической, так как в ЭВМ может быть представлено лишь конечное число различных чисел и повторное появление какого-либо числа (а значит, и всех последующих за ним чисел) неизбежно. Поэтому с практической точки зрения даже очень длинные последовательности нельзя считать случайными. ИМИТАЦИЯ СЛУЧАЙНЫХ ИСПЫТАНИЙ НА ЭВМ Выясним, как, зная последовательность значений случайной величины R, равномерно распределенной на отрезке [0,1], можно имитировать на ЭВМ случайные процессы. Моделирование последовательности независимых случайных испытаний. Пусть проводится последовательность k независимых испытаний. Предположим, что результатом каждого из этих k независимых испытаний может быть появление одного из n несовместных событий , образующих полную группу. Известна вероятность появления каждого события, которая не изменяется при переходе от одного испытания к другому. Так как события несовместны и образуют полную группу, то Моделирование такой последовательности испытаний осуществляется следующим образом. Разделим отрезок [0,1] на n участков , длины которых соответственно равны (рис. 1). Получаем последовательность значений случайной величины R. Если , то считаем, что в i-м испытании наступило событие . Это допущение правомерно, так как . Пример. Пусть проводится последовательность независимых испытаний. В результате каждого испытания может произойти одно из несовместимых событий , образующих полную группу; P(A1)=0,35; P(A2)=0,25; P(A3)=0,4. Моделирование такой последовательности испытаний осуществляется следующим образом. Разделим, как показано на рис.2, отрезок [0,1] на три участка. Пусть r1=0,15; это число попало на первый участок, значит, в первом испытании произойдет событие А1. Значение r2=0,34, т. е. во втором испытании опять произойдет событие А1; далее, r3=0,71 — в третьем испытании произойдет событие А3 и т. д. ОБЩИЕ МЕТОДЫ МОДЕЛИРОВАНИЯ СЛУЧАЙНЫХ ВЕЛИЧИН Если случайная величина дискретна, то её моделирование (получение последовательности значений) можно свести к моделированию независимых испытаний. Действительно, пусть имеет место следующий ряд распределения: X x1 x2 … xn P p1 p2 … pn Обозначим через Ai событие, состоящее в том, что случайная величина X примет значение xi. Тогда нахождение значения, принятого случайной величиной X в результате испытания, сводится к определению того, какое из событий A1, A2,…,An появится. Так как события A1, A2,…,An несовместны, образуют полную группу и вероятность появления каждого из них не изменяется от испытания к испытанию, то для определения последовательности значений, принятых случайной величиной X, можно использовать процедуру моделирования последовательности независимых испытаний. Помимо описанного выше общего алгоритма моделирования дискретной случайной величины для многих законов распределения существуют специальные алгоритмы. Для моделирования непрерывной случайной величины существует множество методов, большая часть которых зависит от вида заданного распределения этой величины. Рассмотрим общие алгоритмы моделирования НСВ. Простейший случай – это равномерно распределенные случайные числа. Для получения их последовательности можно использовать линейный конгруэнтный метод: xn = (cxn-1 + d) mod m, где c, d, m – это натуральные числа, причем период m берется очень большим. Генератор выдает числа r = xn/m, принадлежащие отрезку [0,1]. Имея алгоритм генерации таких чисел, можно получать числа из произвольного интервала [a,b]: x = a + (b - a)r. Более сложные распределения часто строятся с помощью равномерного распределения. Рассмотрим достаточно универсальный метод Неймана (метод отбора-отказа). Пусть необходимо генерировать случайные числа с некоторой заданной нормированной плотностью вероятности f(x) на интервале [a,b]. Введем положительно определенную функцию сравнения v(x) такую, что v(x) = v = max f(x) и v(x) > f(x) на [a,b]. Поскольку площадь под кривой f(x) равна для интервала [x, x+dx] вероятности попадания x в этот интервал, можно использовать метод случайных испытаний. Генерируем равномерно распределенное случайное число r[0,1] и получаем числа x = a + (b - a)r и y = r v. Если точка M(x,y) не попадает под кривую f(x), то ее отбрасывают, в противном случае – оставляют. При этом множество координат x оставленных точек будет распределено в соответствии с плотностью вероятности f(x). Метод эффективен, когда функции v(x) и f(x) близки. В качестве v(x) можно брать ступенчатые функции.