Лабораторная работа №1 «Моделирование случайных чисел с заданным законом распределения». Лабораторная работа 1 Моделирование случайных чисел с заданным законом распределения
 Скачать 3.56 Mb.
|
1 2 3 Семестр 3 Лабораторная работа №1 «Моделирование случайных чисел с заданным законом распределения» Целью работы является 1) практическое ознакомление с алгоритмами моделирования случайных чисел с заданным законом распределения; 2) изучение основных способов статистической оценки характеристик случайных чисел. Краткие теоретические сведения Дискретные случайные величины Слова "случайная величина" в обыденном смысле употребляют тогда, когда хотят подчеркнуть, что неизвестно, каким будет конкретное значение этой величины. Причем иногда за этими словами скрывается просто незнание, какова эта величина. Математик употребляет эти же слова "случайная величина", вкладывая в них определенное содержание. «Действительно, - говорит он, - мы не знаем, какое значение примет эта величина в данном конкретном случае, но мы знаем, какие значения она может принимать, и знаем, каковы вероятности тех или иных значений. На основании этих данных мы не можем точно предсказать результат одного испытания, связанного с этой случайной величиной, но можем весьма надежно предсказать совокупность результатов большого числа испытаний. Чем больше испытаний, тем точнее будут наши предсказания». Итак, чтобы задать случайную величину, надо указать, какие значения она может принимать, и каковы вероятности этих значений. Случайная величина Х называется дискретной, если она может принимать дискретное множество значений n 2 1 x ..., , x , x Формально случайная дискретная величина Х определяется таблицей 4 p p p x x x X n 2 1 n 2 1 (1.1) где n 2 1 x ..., , x , x - возможные значения величины X; n 2 1 p ..., , p , p - соответствующие вероятности. Точнее говоря, вероятность } x X { P i того, что случайная величина Х примет значение i x , равна: p } x X { P i i (1.2) Таблица (1) называется распределением случайной дискретной величины. Числа n 2 1 x ..., , x , x могут быть вообще говоря, любыми. Однако вероятности n 2 1 p ..., , p , p должны удовлетворять двум условиям: 0 p i (1.3) и 1 p p p n 2 1 (1.4) Последнее условие означает, что Х обязана в каждом случае принять одно из значений n 2 1 x ..., , x , x Кроме распределения случайной величины, которая является исчерпывающей характеристикой, вводятся числовые характеристики, основными среди которых являются математическое ожидание и дисперсия. Получение случайных величин на ЭВМ Сама постановка вопроса "получение случайных чисел на ЭВМ" иногда вызывает недоумение: ведь все, что делает компьютер, должно быть заранее запрограммировано; откуда же может появиться случайность? Специалисты считают, что в этом вопросе есть определенные трудности, но они относятся скорее к философии, так что мы на них останавливаться не будем. Отметим лишь, что случайные величины, 5 о которых шла речь в предыдущем разделе это идеальные математические понятия. Вопрос о том, можно ли с их помощью описать какое-либо явление природы, решается опытным путем. Такое описание всегда является приближенным. Более того, случайная величина, которая вполне удовлетворительно описывает какую-то физическую величину в одном классе явлений, может оказаться плохой характеристикой этой же величины при исследовании других явлений. Точно так же дорога, которую на карте страны можно считать прямой (идеальной математической прямой "без ширины"), становится полосой с изгибами на крупномасштабном плане населенного пункта. Обычно различают три способа получения случайных величин: из заранее составленных таблиц случайных чисел; физические генераторы случайных чисел; с помощью формул (генераторов или датчиков) псевдослучайных чисел. Поскольку "качество" используемых в имитационном моделировании случайных чисел проверяется с помощью специальных тестов, можно не интересоваться тем, как эти числа получены: лишь бы они удовлетворяли принятой системе тестов. Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины X, называются псевдослучайными числами. Под словом "имитирующие" подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины. Основой или «сырьем» для моделирования случайных величин с заданным законом распределения являются так называемые базовые случайные числа. Совокупность 2, 1, i }, R { i независимых равномерно распределенных на отрезке [0, 1] случайных величин называется последовательностью базовых случайных чисел. Мы называем эти числа псевдослучайными потому, что фактически они остаются полностью детерминированными в том смысле, что если каждое обращение к соответствующей формуле (точнее, к алгоритму) начинается с одними и теми же исходными данными (константами и начальными значениями), то на выходе получаются одинаковые последовательности чисел R. 6 В настоящее время почти все стандартные библиотечные программы вычисления равномерных случайных чисел основаны на конгруэнтных методах, разработанных Лемером. Основная формула мультипликативного конгруэнтного метода Лемера имеет вид: m), (mod aR R i 1 i (1.5) где а и m – неотрицательные целые числа. Согласно этому выражении, нужно взять случайное число i R , умножить его на постоянный коэффициент а и взять модуль полученного числа m (т.е. разделить на а i R и остаток считать как 1 i R ). Поэтому для вычисления (или генерирования) последовательности i R нам необходимы начальные значения 0 R , множитель а и модуль m. Выбираются а, 0 R и m так, чтобы обеспечить максимальную длину (или, как говорят, период) неповторяющейся последовательности i R и минимальную корреляцию между генерируемыми числами. На рисунке 1.1 показан фрагмент среды MathCad, на котором проиллюстрирована математическая реализация этого метода. Переменной А присваивается значение 1220703125 5 a 13 , переменной m – значение 2147483649 1 2 m 31 . Функция ) x , x mod( 2 1 вычисляет остаток от целочисленного деления первого аргумента во второй. Получаем последовательность {X} псевдослучайных чисел, равномерно распределенных от 0 до m. Делим каждый член этой последовательности на m, получаем базовую последовательность { i R } – числа равномерно распределенные от 0 до 1. Методы генерации псевдослучайных чисел с заданным законом распределения Базовые случайные числа позволяют генерировать новые случайные последовательности, подчиняющиеся любому закону распределения. 7 Рисунок 1.1 – Моделирование базовой последовательности мультипликативным конгруэнтным методом. Фрагмент среды MathCad Существует два основных пути преобразования базовых случайных чисел { i R }, в случайные числа { i y }, распределенные по заданному закону распределения. Один из них, который называется методом инверсии, состоит в реализации определенных арифметических операций над базовым числом i R , чтобы получить i y Второй метод основывается на моделировании условий соответствующей предельной теоремы теории вероятностей. Кроме указанных двух основных подходов можно также выделить эвристические способы генерирования случайных чисел. 8 Метод инверсии Моделирование случайной величины, равномерной на (a, b) Предположим, что нам необходимо составить программу для моделирования входного потока заявок распределенного по равномерному закону в интервале (a, b). Уравнение метода инверсии (1.6) для рассматриваемого случая выглядит так: , R a b dy y a (1.6) где R – равномерно распределенное случайное число на (0; 1), т.е. базовое число. Это интегральное уравнение решается легко и ответ ясен: R a b a y (1.7) Отсюда мы имеем явное выражение для у: ), a b ( R a y (1.8) где R – как обычно, базовое случайное число. Моделирование экспоненциальной случайной величины Как известно, случайная величина x, распределенная по экспоненциальному закону описывается следующей плотностью распределения: x e ) x ( p (1.9) На рисунке 1.2 построены графики экспоненциальных плотностей распределения при различных параметрах 9 Рисунок 1.2 – Экспоненциальная плотность вероятностей x e ) x ( p с разными значениями параметра Экспоненциальному распределению, как правило, подчиняется случайный интервал времени между поступлениями заявок в систему массового обслуживания. Поэтому весьма важно уметь моделировать потоки заявок разной интенсивности . Напомним, что математическое ] [ M ожидание экспоненциально распределенной случайной величины равно: , / 1 ] [ M а дисперсия: / 1 ] [ D 2 Чтобы найти алгоритм имитации экспоненциально распределенных чисел , применим метод инверсии: R e 0 x (1.10) , R e 1 (1.11) откуда ), R 1 ln( 1 (1.12) но, поскольку случайная величина (1 - R) распределена точно так же, как R, и находится в том же интервале (0,1), то (1.12) можно заменить на более удобную формулу: 10 , R ln 1 (1.13) что дает искомый ответ. Моделирование нормальной случайной величины на основе центральной предельной теоремы Нормальное (или гауссово) распределение (рисунок 1.3) - это, несомненно, один из наиболее важных и часто используемых в имитационном моделировании видов непрерывных распределений. Рисунок 1.3 – Нормальная (гауссовская) плотность вероятностей Плотность вероятности нормально распределенной случайной величины записывается так: 2 2 2 ) m x ( e 2 1 ) x ( p (1.14) где m и - параметры нормального распределения x M m - математическое ожидание; - среднеквадратическое отклонение. Интегральная функция распределения нормальной случайной величины равна x 2 ) m x ( dx e 2 1 ) x ( p 2 2 (1.15) 11 Поэтому алгоритмы моделирования нормальных случайных чисел базируются на предельных теоремах теории вероятностей. Центральная предельная теорема говорит о том, что сумма n одинаково распределенных независимых случайных величин х со средним x M и дисперсией x D стремится к нормально распределенной величине с параметрами x nM и x nD при бесконечном увеличении n. Следствием теоремы является, в частности, и то, что для получения нормальной выборки, можно воспользоваться базовыми случайными числами R. Идея алгоритма состоит в следующем. Определим новую случайную величину s в виде суммы базовых чисел i R , (i=1, 2, 3, …, n): R R R s n 2 1 (1.16) Тогда, согласно утверждению центральной предельной теоремы, случайная величина s является асимптотически нормальной величиной с математическим ожиданием s M и дисперсией s D равными соответственно: , 2 / n M s (1.17) и 12 / n D s (1.18) Для практического использования формула (1.16) неудобна (поясните почему), поэтому введем вспомогательную случайную величину z равную 12 / n ) 2 / n s ( z (1.19) Из (1.19) следует, что z – случайная величина, распределенная по нормальному закону с нулевым средним и единичной дисперсией. Тогда для любого нормального распределения со средним и дисперсией 2 случайное отклонение y, соответствующее указанным выше n случайным числам, получается из формулы 12 12 / n 2 n s z ) y ( (1.20) Следовательно, 2 / n R 12 / n 12 / n ) 2 / n s ( y n 1 i i (1.21) Согласно той же предельной теореме, нормальность достигается быстро даже при сравнительно небольших значениях n. В практических задач n обычно принимается равным 12. При этом последняя формула упрощается и принимает вид: 6 R y 12 1 i i (1.22) Формула (1.22) и дает алгоритм моделирования нормальных случайных чисел с требуемыми параметрами и . Описанный метод считается малоэффективным, так как требует генерации нескольких случайных базовых чисел R для получения одного нормального выборочного значения y. Оценка статистических характеристик случайных величин При решении многих прикладных задач необходимые вероятностные характеристики соответствующих случайных величин неизвестны исследователю и должны определяться по экспериментальным данным. Такое статистическое описание результатов наблюдений, построение и проверка различных математических моделей, использующих понятие вероятности, составляют основное содержание математической статистики. Фундаментальными понятиями статистической теории являются понятия генеральной совокупности и выборки. Генеральная совокупность - совокупность всех мыслимых (возможных) результатов наблюдений над случайной величиной, которые в принципе могут быть проведены при данных условиях. 13 Содержательный смысл этого понятия состоит в том, что предполагается существование некоторых вполне определенных свойств, неслучайных закономерностей, присущих данной совокупности. Эти свойства и должны быть определены исследователем. Фактически эти свойства являются объективным отображением вероятностных свойств изучаемого объекта, которые могут быть охарактеризованы с помощью соответствующих законов распределения вероятностей или связанных с ними числовых параметров. Как правило, считается, что указанные свойства не изменяются во времени. Выборка - это конечный набор N 2 1 x ..., , x , x значений случайной величины, полученный в результате наблюдений. Число элементов N выборки называется ее объемом или размером. Заметим, что выборка может иметь и совпадающие значения i x случайной величины X. Интуитивно понятно, что чем больше объем выборки, тем более точно она должна отражать статистические свойства случайной величины. Определение. Выборка называется репрезентативной (представительной), если она достаточно полно характеризует свойства генеральной совокупности. Для обеспечения репрезентативности выборки чаще всего используют метод случайного выбора элементов. Предполагается, что при таком выборе каждая возможная выборка фиксированного объема имеет одну и ту же вероятность выбора, а последовательные наблюдения взаимно независимы. Оцениванием в статистике называется указание приближенного значения интересующего нас параметра (или функции от некоторых параметров) на основе наблюдаемых (экспериментальных) данных, представленных в виде выборки ограниченного объема. Оценка - это правило вычисления приближенного значения параметра (или функции от некоторых параметров) по наблюдаемым данным. При многократном извлечении выборок одного и того же объема и последующем нахождении множества оценок одного и того же параметра получаются различные числовые значении этих оценок, изменяющиеся от одной выборки к другой случайным образом. 14 Иными словами, любая оценка произвольного параметра есть случайная величина. В этом состоит принципиальное отличие оценки от самого параметра. Элементарные статистические процедуры В случае гауссовского распределения для истинного математического ожидания x m существует его оценка x m , вычисляемая по выборке объема n случайной величины ) x ..., , x , x ( X n 2 1 : x n 1 m n 1 i i x (1.23) Для истинной дисперсии x D (характеристика рассеивания случайной величины око ее математического ожидания) ее оценка x D при известном математическом ожидании x m вычисляется так: , ) m x ( 1 n 1 D n 1 i 2 x i 2 x x (1.24) где x является среднеквадратическим отклонением. В случае неизвестного математического ожидания дисперсию x D нужно вычислять по формуле: 2 n 1 i i n 1 i 2 i 2 x x x n 1 x 1 n 1 D (1.25) Приведенные оценки являются несмещенными и асимптотически эффективными. Не будем забывать о том, что оценки сами являются случайными величинами, а значит, обладают некоторым разбросом, который оценивается дисперсией. Дисперсии D {} вышеуказанных оценок соответственно таковы: дисперсия оценки среднего: 15 ; n / } m { D 2 x x (1.26) дисперсия оценки x D в случае известного математического ожидания: ; n / 2 } D { D 4 x x (1.27) в случае, если не известно математическое ожидание: ). 1 n /( 2 } D { D 4 x x (1.28) После вычисления точечных оценок обычно переходят к построению вариационного ряда, диаграммы накопленных частот и гистограммы выборки. Пусть имеется набор (выборка) экспериментальных данных n 2 1 x ..., , x , x . Вариационный ряд (или ряд распределения) n 2 1 z ..., , z , z получают из исходных данных путем расположения n) ..., 2, 1, (m x m в порядке возрастания от min x до max x так, чтобы max n 2 1 min x z z z x Диаграмма накопленных частот ) x ( P n является эмпирическим аналогом интегрального закона распределения P(x) и ее строят в соответствии с формулой ) x ( 1 j n n n 1 ) x ( P (1.29) где ) x ( n - число элементов в выборке, для которых значение x x j Практически это делается так. На оси абсцисс указывают значения наблюдений min x (или 1 z ). Значение по оси ординат равно нулю левее точки min x ; в точке min x и далее во всех других точках m x диаграмма имеет скачок, равный 1/n. Если существует совпадающих значений m x , то в этом месте на диаграмме происходит скачок, равный n / . Ясно, что для величин max x x 16 значение диаграммы накопленных частот равно 1. Отметим, что если n , то ) x ( P ) x ( P n Пример. Пусть имеется выборка объема 5: 7 x ; 5 x ; 4 x ; 2 x ; 5 x 5 4 3 2 1 Вариационный ряд для данной выборки будет таким: 7 z ; 5 z ; 5 z ; 4 z ; 2 z 5 4 3 2 1 Соответствующая диаграмма накопительных частот представлена на рисунке 1.4. Рисунок 1.4 – Диаграмма накопленных частот Гистограмма ) x ( f n является эмпирическим аналогом функции плотности распределения f(x). Последовательность построения гистограммы такова. По оценочной формуле находят предварительное количество квантов (интервалов) K, на которое нужно разбить на ось Ох: K=1+3.2lg n; найденное значение K округляется до ближайшего целого числа. Формула для K является эмпирической, что означает примерное значение. Ее величина связана с той целью, чтобы в один квант попало хотя бы одно выборочное значение i x . Интересно, что зависимость количества интервалов K от объема выборки n равна (таблица 1.1) 17 Таблица 1.1 - Зависимость количества интервалов K от объема выборки n n 100 200 300 500 1000 K 7 8 9 10 11 Далее определяют длину каждого кванта (интервала): , K / ) x x ( x min max которую для удобства построений можно несколько округлить в ту или иную сторону. Середину области изменения выборки (центр распределения) 2 / ) x x ( min max принимают за центр некоторого интервала, после чего находят границы и окончательное количество указанных интервалов так, чтобы в совокупности они перекрывали всю область от min x и max x Далее подсчитывают количество наблюдений m n , попавшее в каждый квант: m n равно числу членов вариационного ряда, для которых справедливо неравенство x x z x m 1 m Здесь m x и x x m - границы m-го интервала. Отметим, что при использовании этой формулы значения 1 z , попавшие на границу между (m-1) и m-м интервалами, относят к m-му интервалу. Далее подсчитывают относительное количество (относительную частоту) наблюдений n / n m , попавших в данных квант. Наконец, строят гистограмму, представляющую собой ступенчатую кривую, значение которой на m-й интервале ) x , x ( m m (m=1, 2, …, K) постоянно и равно n / n m , или с учетом условия 1 dz ) z ( p n , равно x ) n / n ( m 18 |