Моделирование случайных чисел

Размещено на http://www.allbest.ru/

Лабораторная работа

Моделирование случайных чисел

1 Цель работы

Изучить методы и алгоритмы моделирования случайных величин.

2. Теоретические сведения

случайный величина вероятностный моделирование

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

Случайным опытом или экспериментом называется процесс, при котором возможны различные исходы, так что нельзя заранее предсказать, каков будет результат. Величина X={xi}=x1, x2, …, xn, представляющая собой результат случайного опыта, называется случайной величиной. Непостоянство результата такого опыта может быть связано с наличием случайных ошибок измерений или со статистической природой самой измеряемой величины (например, процесс распада радиоактивного вещества). Будем обозначать отдельные значения, которые принимает случайная величина (не обязательно численные), как xi, где i = 1, 2, …, n. Любая функция от xi будет также случайной величиной.

Под моделированием случайной величины Х принято понимать процесс получения на ЭВМ её выборочных значений x1, ..., xn.

На практике используются три основных способа генерации случайных чисел:

- табличный (файловый) - ввод таблиц равномерно распределённых случайных чисел во внешнюю или оперативную память ЭВМ;

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

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

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

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

xi	0	1	2	3	…	9
pi	0,1	0,1	0,1	0,1	…	0,1

При составлении таких таблиц выполняется требование, чтобы каждая из этих цифр от 0; 1; ...; 9 встречалась примерно одинаково часто и независимо от других с вероятностью pi = 0,1.

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

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

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

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

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

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

Первый алгоритм для получения псевдослучайных чисел предложил Дж. Нейман. Это так называемый метод середины квадратов, который заключается в следующем:

и т.д.

Метод средин квадратов фон Неймана является сравнительно бедным источником случайных чисел, т.к. последовательность стремится войти в привычную колею, т.е. короткий цикл повторяющихся элементов.

Назовем достоинства метода псевдослучайных чисел.

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

2. Малый объем памяти ЭВМ для программирования.

3. Любое из чисел легко воспроизвести.

4. Качество генерируемых случайных чисел достаточно проверить один раз.

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

Дискретной случайной величиной называется такая величина, число возможных значений которой либо конечное, либо бесконечное счетное множество (множество, элементы которого могут быть занумерованы).

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

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

Универсальной формой закона распределения (непрерывных и дискретных величин) является функция распределения вероятностей ? это такая функция F(x), значение которой в точке x равно вероятности (P) того, что при проведении опыта значение случайной величины X окажется меньше, чем x:

F(x) = P(X < x).

Основные свойства функции распределения вероятностей следующие:

1) числовые значения заключены в пределах 0 ? F(x) ? 1;

2) если x1 ? x2, то F(x1) ? F(x2), т.е. F(x) ? неубывающая функция;

3) F(x) > 0 при x > ??, F(x) > 1 при x > ?.

Рисунок 1 - Графическое изображение функции распределения вероятностей

Если случайная величина дискретна, то ее функция распределения представляет собой ступенчатую функцию (рисунок 1, a), а у непрерывных случайных величин функция распределения также непрерывна (рисунок 1, b).

Функцию распределения вероятностей F(x) непрерывной случайной величины можно представить в виде интеграла от некоторой неотрицательной функции f(x):

.

Функция f(x) называется плотностью распределения вероятности. Основные свойства плотности вероятности таковы:

1) ;

2)

3) плотность вероятности пропорциональна вероятности события (x ? X ? x + dx).

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

2.1.1 Параметры случайной величины

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

Математическим ожиданием или средним значением дискретной случайной величины называется сумма всех возможных значений xi случайной величины X, умноженных на соответствующие вероятности:

,

,

.

Заметим, что x является не случайной, а определенной, детерминированной величиной.

Так как функция от случайной величины является также случайной величиной, то математическое ожидание функции Y = H(X) определяется следующим образом:

.

Для непрерывных случайных величин будем иметь

 и .

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

.

Положительный квадратный корень из дисперсии называется стандартным или среднеквадратичным отклонением Часто используют также эквивалентный термин квадратичное отклонение.. Среднеквадратичное отклонение количественно показывает, насколько сильно значения случайной величины X разбросаны вокруг среднего значения x.

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

Пусть N раз бросили игральный кубик и получили N1, N2, N3, N4, N5, N6 выпадений значений 1, 2, 3, 4, 5, 6 соответственно. Тогда говорят, что вероятность выпадения какого-нибудь числа i (i = 1, 2, 3, 4, 5, 6) приближенно равна

т.е. Pi равна доле числа случаев, в которых выпало значение i, от полного числа бросаний. Знак приближенного равенства означает, что если повторить еще N бросаний, то получим, вообще говоря, другое значение Ni . Соотношение для вероятности становится точным в пределе, когда N>?:

.

В нашем случае, если кубик "честный", вероятности выпадения значений 1, 2, 3, 4, 5, 6 равны P1 = P2 = P3 = P4 = P5 = P6 = 1/6.

Очевидно также, что

.

Вычислим математическое ожидание M{X} и дисперсию D{X} для игрального кубика:

2.2 Моделирование случайных событий

2.2.1 Получение равномерно распределенных случайных чисел

При моделировании систем на ЭВМ программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. В качестве базового процесса примем последовательность случайных чисел {xi} = x1, x2, …, xn, представляющих собой реализации независимых, равномерно распределенных на интервале (0;1) случайных величин {ri} = r1, r2, …, rn.

Непрерывная случайная величина R имеет равномерное распределение на интервале (a; b), если ее функции плотности вероятности (рис. 2, а) и распределения (рис. 2, б) задаются следующим образом:

.

Размещено на http://www.allbest.ru/

Легко можно вычислить, что

, а

.

В частном случае, когда a = 0 и b = 1, имеем равномерно распределенную на интервале (0;1) случайную величину, для которой математическое ожидание М(X)=1/2, а дисперсия D(X) = 1/12.

От последовательности случайных чисел, равномерно распределенных в интервале (0;1), нетрудно перейти к последовательности случайных чисел с произвольным заданным законом распределения.

Пример 2. Получение равномерно распределенной в интервале (0;1) случайной величины X может быть осуществлено следующим алгоритмом:

xi+1 = {? • xi},

x0 = 0.1.

Знак {} означает, что берется дробная часть произведения. Вычисления дают такую последовательность: x0 = 0.1, x1 = 0.415926, x2 = 0.667, x3 = 0.54422, x4 = 0.97175, x5 = 0.28426 и т.д.

К настоящему времени разработано множество алгоритмов получения псевдослучайных чисел. Наиболее популярным для получения псевдослучайных чисел x1, x2,..., xn является метод вычетов (мультипликативный датчик), который можно записать в следующей форме:

xi+1 ={M • xi}, x0 = 2?m,

где M ? достаточно большое целое число, фигурные скобки обозначают дробную часть, а m ? число двоичных разрядов в мантиссе чисел в ЭВМ. Методы выбора значений M, x0 и m разнятся для разных вариантов реализаций данного метода (это своя собственная "наука") и определяют основные свойства датчика случайных чисел (соответствие статистическим критериям, длину периода повторения последовательности и т.п.).

2.2.2 Моделирование нормально распределенных случайных величин

В технике и природе наиболее распространенное распределение случайных чисел - гауссовское или нормальное.

Нормальной (или гауссовской) называется случайная величина X, определенная на всей числовой оси (? ?, ?) имеющая плотность распределения вероятности:

.

Здесь D=?2 - дисперсия случайной величины, а M{X} - математическое ожидание случайной величины X.

Распространенный алгоритм моделирования таких величин основан на центральной предельной теореме теории вероятностей.

Размещено на http://www.allbest.ru/

Рассмотрим алгоритм моделирования нормально распределенных случайных величин.

Известно, что если случайная величина X распределена равномерно в интервале (0;1), то ее математическое ожидание М(X)=1/2, а дисперсия D(X) = 1/12. Для практического использования можно считать, что случайная величина распределена нормально при n ? 8 (n - количество случайных величин) с математическим ожиданием M{X}=n/2, дисперсией D{X}=n/12 и среднеквадратичным отклонением ?==.

Величина М(X) характеризует центр тяжести распределения X и не влияет на форму кривой. Величина ? же характеризует разброс случайной величины X относительно ее среднего значения М(X) (см. рисунок 3).

Так как моделирование любого нормального распределения с параметрами (M{X}, ?) может быть осуществлено по очевидной формуле X= M{X}+?•R, где R={r1, r2, …, rn}? сгенерированная в интервале [0;1) случайная величина, то нормально распределенные случайные величины с параметрами (0;1) можно вычислять по следующей приближенной формуле:

.

При n = 12 эта формула заметно упрощается

.

Пример 3.

1. Разыграть 100 возможных значений случайной величины Х распределенной нормально с параметрами M{X} = 0 и ? = 1.

2. Оценить параметры разыгранной случайной величины Х.

Решение:

1. Выберем 12 случайных чисел распределенных равномерно в интервале (0;1) из таблицы случайных чисел, либо из компьютера. Сложим эти числа и из суммы вычтем 6, в итоге получим:

X1= R = = (0,10+0,09+…+0,67)-6=-0,99.

Поступая аналогичным образом, найдем остальные возможные значения X2, X3, …, X100.

2. Выполнив необходимые расчеты, найдем выборочную среднюю, которая является оценкой M{X} и выборочное среднее квадратичное отклонение (выборочная дисперсия), которое является оценкой ?.

Выборочное среднее:

Выборочная дисперсия

.

Величина называется выборочным средним, ? выборочной дисперсией случайной величины X. Значения и можно принять в качестве оценок математического ожидания M{X} и дисперсии D{X} величины X, т.е. , . Приближенные равенства становятся точными в пределе, когда n>. Выборочное среднеквадратичное отклонение ?n равно корню квадратному из выборочной дисперсии .

Получим:

.

Как видим, оценки удовлетворительны, т.е. близко к нулю, а близко к единице.

Если требуется разыграть значения нормальной ненормированной случайной величины с математическим ожиданием M{X} отличным от нуля и ? отличным от единицы, то сначала разыгрывают возможные значения ri нормированной случайной величины в интервале [0;1), а затем находят искомое значение по формуле

Xi= M{X}+?•ri

которая получена из соотношения

.

2.2.3 Моделирование дискретных случайных величин

Рассмотрим дискретную случайную величину X, принимающую n значений x1, x2, ..., xn с вероятностями P1, P2,..., Pn. Эта величина задается таблицей распределения

.

Или

X	x1	x2	x3	…	xn
P	P1	P2	P3	…	Pn

Для моделирования такой дискретной случайной величины разбивают отрезок [0;1] на n последовательных отрезков ?1, ?2,..., ?n, длины которых равны соответствующим вероятностям P1, P2, ..., Pn.

Тогда длины отрезков будут равны:

Длина

Длина

.......................................................

Длина

Видно, что длина частичного интервала с индексом i равна вероятности Р с тем же индексом. Длина i=Pi.

Получают случайную величину R, равномерно распределенную в интервале (0;1). Таким образом, при попадании случайного числа ri в интервал i случайная величина X принимает значение xi с вероятностью Pi.

Теорема: если каждому случайному числу ri(0? ri <1), которое попало в интервал i, поставить в соответствие возможное значение xi, то разыгрываемая величина будет иметь заданный закон распределения.

Рассмотрим алгоритм моделирования дискретных случайных величин.

1. Нужно разбить интервал [0;1) на n частичных интервалов:

1 - (0; P1), 2 - (P2; P1+ P2), …, n - (P1+P2 + … +Pn-1; 1).

2. Выбрать (например, из таблицы случайных чисел, или в компьютере) случайное число ri из интервала [0;1).

Если ri попало в интервал i, то моделируемая дискретная случайная величина приняла возможное значение xi.

Пример 4. Смоделировать 8 значений дискретной случайной величины, заданной таблицей распределения:

Решение:

1. Разобьем интервал (0;1) точками с координатами 0,25; 0,25+0,16=0,41 на три частичных интервала:

1=[0;0.25), 2=[0.25;0.41), 3=[0,41;1).

2. Сгенерируем с помощью компьютера 8 случайных чисел, например, r1 = 0,10; r2 = 0,37; r3 = 0,08; r4 = 0,99; r5 = 0,12; r6 = 0,66; r7 = 0,31; r8 = 0,85.

3. Случайное число r1 = 0,10 принадлежит первому частичному интервалу, поэтому разыгрываемая случайная величина приняла возможное значение x1 = 3. Случайное число r2 = 0,37 принадлежит второму частичному интервалу, поэтому разыгрываемая величина приняла возможное значение x2 = 11. Аналогично получим остальные возможные значения дискретной случайной величины X.

Результат: последовательность смоделированных возможных значений дискретной случайной величины X такова: 3; 11; 3; 24; 3; 24; 11; 24.

2.2.4 Моделирование непрерывных случайных величин

Размещено на http://www.allbest.ru/

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

Суть метода исключения (или метода Неймана) заключается в следующем.

Пусть случайная величина X определена на конечном интервале (a;b) и плотность ее распределения ограничена, так что f(x)?M. Тогда, используя пару равномерно распределенных на интервале (0;1) случайных чисел R, осуществляем следующие действия для розыгрыша (моделирования) значения X:

1. Разыгрываем два значения r1 и r2 случайной величины R и строим случайную точку Q с координатами (см. рисунок 4):

X0=a+r1•(b-a), ?=r2•M.

2. Если ?>f(X0), то пару значений (r1, r2) отбрасываем и переходим к пункту 1; иначе принимаем X = X0.

Таким образом, определяются координаты случайной точки Q(X0,?) и, если точка окажется под кривой f(x), то абсцисса этой точки принимается в качестве значения случайной величины X=X0=a+r1•(b-a) с плотностью распределения f(x). В противном случае точка отбрасывается, определяются координаты следующей точки, и все повторяется.

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

2.3 Проверка гипотезы о законе распределения методом гистограмм

Пусть в результате эксперимента получено n значений x1, x2, …, xn случайной величины X и все они заключены в пределах a < xi < b.

Суть проверки по гистограмме сводится к следующему.

а) Выдвигается гипотеза о равномерности распределения чисел в интервале (0;1).

б) Затем интервал (a; b) разбивается на L (любое число, не слишком большое и не слишком малое) равных подынтервалов длиной ?j, тогда при генерации последовательности {xi} каждое из чисел x с вероятностью pj =1/L, , попадает в один из подынтервалов. Всего в каждый j-й подынтервал попадает j чисел последовательности {xi}, , причем . Относительная частота попадания случайных чисел последовательности {xi} в каждый из подынтервалов будет равна j/n.

в) Над каждым из подынтервалов разбиения строится прямоугольник, площадь которого равна частоте попадания {xi} в этот подынтервал. Высота каждого прямоугольника равна частоте, деленной на ?j. Полученную ступенчатую линию называют гистограммой.

г) Вид соответствующей гистограммы представлен на рисунке 5, где пунктирная линия соответствует теоретическому значению pj, а сплошная - экспериментальному j/n. Очевидно, что если числа {xi} принадлежат псевдослучайной равномерно распределенной последовательности, то при достаточно больших n экспериментальная гистограмма (ломаная линия на рис. 5) приблизится к теоретической прямой pj=1/L.

Размещено на http://www.allbest.ru/

Гистограмма служит приближением к неизвестной плотности случайной величины X. Площадь гистограммы, заключенная между xi и xi+1, дает приближенное значение вероятности P{xi<X<xi+1}.

3. Порядок выполнения работы

1. Используя метод вычетов, сгенерировать последовательность из 1 000 псевдослучайных чисел, результат вывести на экран.

1.1. Оценить математическое ожидание полученной последовательности, математическое ожидание и выборочную среднюю вывести на экран.

1.2. Оценить дисперсию полученной последовательности, дисперсию и выборочную дисперсию вывести на экран.

1.3. Построить таблицу 1 (количество L подынтервалов не менее 10), частотную таблицу вывести на экран.

Таблица 1 - Частотная таблица

Интервал	Кол-во СВ (частота попаданий), выпавших в данный интервал	Относительная частота попадания
?1	?1	?1/n
?2	?2	?2/n
…	…	…
?L	?L	?L/n
	? кол-во СВ

1.4. Проверить гипотезу о законе распределения методом гистограмм, построить гистограмму, вывести ее на экран.

2. Смоделировать дискретную случайную величину, заданную таблицей 2, результат вывести на экран.

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

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

2.3. Построить частотную таблицу, вывести ее на экран.

2.4. Оценить закон распределения случайной величины по графику частоты появления ее значений в результате экспериментов.

3. Смоделировать методом исключений непрерывную случайную величину с заданной плотностью распределения вероятности (таблица 3). Функции для графика рассчитываются по формулам

или y= _ kx+b (в зависимости от вида графика).

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

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

3.3. Построить частотную таблицу, вывести ее на экран.

3.4. Проверить гипотезу о законе распределения методом гистограмм, построить и вывести на экран гистограмму.

Таблица 2 - Таблица распределений

Вариант	Таблица распределения
1	xi	5	7	17	19	21	25	55
	pi	0.01	0.05	0.3	0.3	0.3	0.02	0.02
2	xi	1	3	7	10	15	18	23
	pi	0.1	0.05	0.02	0.05	0.25	0.33	0.2
3	xi	2	3	5	12	21	33	44
	pi	0.1	0.15	0.2	0.05	0.02	0.33	0.15
4	xi	5	8	13	16	21	24	29
	pi	0.1	0.02	0.25	0.15	0.35	0.03	0.1
5	xi	2	3	5	8	11	15	20
	pi	0.1	0.15	0.25	0.05	0.05	0.3	0.1
6	xi	1	8	17	23	37	42	50
	pi	0.01	0.15	0.05	0.25	0.5	0.02	0.02
7	xi	1	4	12	16	25	33	37
	pi	0.05	0.25	0.25	0.15	0.13	0.1	0.07
8	xi	1	10	15	23	29	38	42
	pi	0.02	0.05	0.1	0.28	0.23	0.22	0.1
9	xi	2	3	7	12	19	23	30
	pi	0.04	0.15	0.2	0.25	0.2	0.15	0.01
10	xi	1	5	7	14	21	26	31
	pi	0.34	0.28	0.16	0.15	0.05	0.01	0.01
11	xi	3	5	8	14	27	29	35
	pi	0.02	0.07	0.1	0.19	0.19	0.2	0.23
12	xi	7	16	28	33	39	46	56
	pi	0.01	0.05	0.07	0.1	0.17	0.25	0.35
13	xi	5	6	8	13	19	26	36
	pi	0.05	0.07	0.2	0.23	0.17	0.23	0.05
14	xi	3	9	18	23	29	27	45
	pi	0.05	0.14	0.2	0.22	0.17	0.14	0.08
15	xi	13	16	28	33	39	47	52
	pi	0.08	0.14	0.25	0.16	0.25	0.09	0.03
16	xi	1	6	8	13	19	24	27
	pi	0.09	0.1	0.21	0.17	0.23	0.15	0.05
17	xi	4	6	10	14	16	20	24
	pi	0.04	0.1	0.1	0.27	0.33	0.13	0.03
18	xi	2	6	12	16	22	26	32
	pi	0.02	0.14	0.24	0.27	0.2	0.1	0.03
19	xi	3	6	9	13	19	27	31
	pi	0.04	0.12	0.22	0.28	0.2	0.1	0.04
20	xi	1	3	8	11	19	29	33
	pi	0.02	0.26	0.18	0.32	0.16	0.02	0.04

Таблица 3 - Плотность распределения вероятности

Вариант	Плотность распределения	Вариант	Плотность распределения
1		11
2		12
3		13
4		14
5		15
Вариант	Плотность распределения	Вариант	Плотность распределения
6		16
7		17
8		18
9		19
10		20

Размещено на Allbest.ur

...