Laba_3-4_Laboratorny_praktikum_GSCh
.pdf
11
примем последовательность случайных чисел {xi} = x1, x2, …, xn, представляющих собой реализации независимых, равномерно распределенных на интервале (0;1) случайных величин {ri} = r1, r2, …, rn.
Непрерывная случайная величина R имеет равномерное распределение на интервале (a; b), если ее функции плотности вероятности (рис. 2, а) и распределения (рис. 2, б) задаются следующим образом:
f (x)
F (x)
|
1 |
|
|
|
, |
|
||
b a |
|
|
|
0, |
|
|
|
|
0,
х а ,в а1,
если a x b
впротивномслучае.
ха,
ах в,
хв.
Легко можно вычислить, что
|
M X |
|
в |
|
|
в а |
|
|
|
|
|
|
|
|
xf (x)dx |
, |
|
|
|
|
|||||
|
x |
|
|
|
||||||||
|
|
|
|
|
||||||||
|
|
|
а |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
в |
|
в а |
2 |
(в а)2 |
||||||
а |
D X M X M X |
х |
|
|
f (x)dx |
|
. |
|||||
|
|
|
||||||||||
|
|
|
|
а |
|
|
2 |
|
12 |
|
||
В частном случае, когда a = 0 и b = 1, имеем равномерно распределенную на интервале (0;1) случайную величину, для которой математическое ожидание М(X)=1/2, а дисперсия D(X) = 1/12.
Первый алгоритм для получения псевдослучайных чисел предложил Дж. Нейман. Это так называемый метод серединных квадратов, который заключается в следующем:
х0 =0.9876, |
х02 =0.97535376, |
12
х |
|
=0.5353, |
х2 |
=0.28654609, |
1 |
|
1 |
|
|
х |
2 |
=0.6546 |
х2 |
=0.42850116 |
|
|
2 |
|
|
и т.д.
Достоинства метода серединных квадратов для получения псевдослучайных чисел следующие:
1.На получение каждого случайного числа затрачивается несколько простых операций, так что скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ.
2.Малый объем памяти ЭВМ для программирования.
3.Любое из чисел легко воспроизвести.
4.Качество генерируемых случайных чисел достаточно проверить один раз.
Недостатки метода:
1.Если на некоторой итерации число х0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения х0.
2.Генератор будет повторять последовательность через Mn
шагов (в лучшем случае), где n — разрядность числа х0, M — основание системы счисления.
Метод серединных произведений заключается в следующем.
Число х0 умножается на х1, из полученного результата х2 извлекается середина х2* (это очередное случайное число) и умножается на х1. Из полученного результата х3 извлекается середина х3* (это очередное случайное число) и умножается на х2*. По этой схеме вычисляются все последующие случайные числа.
Вметоде перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное
число х0. Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число х0*. Точно так же, циклически сдвигая
содержимое ячейки х0 вправо на 1/4 длины ячейки, получаем второе число х0**. Сумма чисел х0* и х0** дает новое случайное число х1. Далее
х1 заносится в х0, и вся последовательность операций повторяется. В случае, если число, полученное в результате суммирования чисел х0* и х0** полностью не умещается в ячейке х1, то от полученного числа необходимо убрать один «лишний» крайний левый бит.
13
К настоящему времени разработано множество алгоритмов получения псевдослучайных чисел.
Линейный конгруэнтный метод является одной из простейших и наиболее употребительных в настоящее время процедур для
получения последовательности целых чисел, равномерно распределенных в интервале (0, M-1). В этом методе используется операция mod(x, y), возвращающая остаток от деления первого аргумента на второй. Каждое последующее случайное число рассчитывается на основе предыдущего случайного числа по
формуле: хi + 1 = mod(k · хi + b, M), где M — модуль (0 < M) M p q (p
– основание системы счисления, q – число разрядов в случайном числе); k — множитель (0 ≤ k < M) k 8t 3 (t – любое целое положительное число; b — приращение (0 ≤ b < M); х0 — начальное значение (0 ≤ х0 < M). Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью. Методы выбора значений M, x0
и в разнятся для разных вариантов реализаций данного метода (это своя собственная "наука") и определяют основные свойства датчика случайных чисел (соответствие статистическим критериям, длину периода повторения последовательности и т.п.). Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом, а при b ≠ 0 — смешанным конгруэнтным методом.
Пример. Выбираем Х0, например, Х0=234567. Вычисляем коэффициент k: пусть t=1, тогда k=8*1-3=5. Выбираем модуль М: пусть система счисления десятичная (p=10), разрядность случайных чисел q=6, тогда М=106. Вычисляем произведение k*Х0=5*234567=1172835. Найдем остаток от деления по модулю М:
Х1= kХ0*(mod106)=1172835*(mod106)=172835. Найдем число последовательности случайных чисел из интервала [0;1]: x1=X1/106=0.172835. Присвоим Х0= x1 и повторим процедуру.
Пример. Получение равномерно распределенной в интервале (0;1) случайной величины X может быть осуществлено следующим алгоритмом (Метод π):
14
xi+1 = {π ∙ xi∙102},
x0 = 10.
Знак {} означает, что берется дробная часть произведения. Вычисления дают такую последовательность: x0 = 0.1, x1 = 0.415926, x2
= 0.667, x3 = 0.54422, x4 = 0.97175, x5 = 0.28426 и т.д.
Если пользователю потребуется, чтобы случайное число x находилось в интервале (a; b), отличном от (0; 1), нужно воспользоваться формулой
x = a + (b – a) · r,
где r — случайное число из интервала (0; 1).
От последовательности случайных чисел, равномерно распределенных в интервале (0;1), нетрудно перейти к последовательности случайных чисел с произвольным заданным законом распределения.
В системе MATLAB случайные числа, равномерно распределенные в интервале [0;1], формируются встроенной функцией rand (см. helprand).
Пример. Сформируем 20 случайных чисел равномерно распределенных из интервала [2;5] встроенной функцией rand в системе Matlab. Программный код решения примера:
a=2; b=5; N=20; t20=a+(b-a)*rand(N,1)
Качество алгоритмического метода оценивается тем, насколько полно он удовлетворяет следующим требованиям:
закон распределения формируемых чисел должен быть равномерным (квазиравномерным);
числа должны быть статистически независимыми;
числа не должны повторяться;
формирование чисел должно занимать минимальное машинное время и минимальный объем памяти.
1.3.2Моделирование дискретных случайных величин с заданным распределением
Рассмотрим дискретную случайную величину X, принимающую n значений x1, x2, ..., xn с вероятностями P1, P2,..., Pn. Эта величина задается таблицей распределения
|
|
|
|
|
|
|
15 |
x |
x |
|
x |
|
, |
n |
|
X |
1 |
|
2 |
|
n |
P 1 |
|
P |
P |
P |
|
i |
|||
|
1 |
|
2 |
|
n |
|
i 1 |
Или
X |
x1 |
x2 |
x3 |
… |
xn |
P |
P1 |
P2 |
P3 |
… |
Pn |
Для моделирования такой дискретной случайной величины разбивают отрезок [0;1] на n последовательных отрезков ∆1, ∆2,..., ∆n, длины которых равны соответствующим вероятностям P1, P2, ..., Pn.
Тогда длины отрезков будут равны: Длина 1 Р1 0 Р1 , Длина 2 Р1 Р2 Р1 Р2 ,
.......................................................
Длина n 1 Р1 Р2 ... Pn1 Рn .
Видно, что длина частичного интервала с индексом i равна вероятности Р с тем же индексом, т.е. длина i = Pi.
Получают случайную величину R, равномерно распределенную в интервале (0;1). Таким образом, при попадании случайного числа ri в интервал i случайная величина X принимает значение xi с вероятностью Pi.
Теорема: Если каждому случайному числу ri (0≤ ri <1), которое попало в интервал i, поставить в соответствие возможное значение xi, то разыгрываемая величина будет иметь заданный закон распределения.
Рассмотрим алгоритм №1 моделирования дискретных случайных величин.
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 значений дискретной случайной величины, заданной таблицей распределения:
16
Х |
Х1=3 |
Х2=11 |
Х3=24 |
Р |
Р1=0.25 |
Р2=0.16 |
Р3=0.59 |
Решение:
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,1; r2.=.0,37; r3 = 0,08; r4 = 0,99; r5 = 0,12; r6 = 0,66; r7 = 0,31; r8 = 0,85.
3.Случайное число r1 = 0,1 принадлежит первому частичному интервалу, поэтому разыгрываемая случайная величина приняла
возможное значение x1 = 3. Случайное число r2 = 0,37 принадлежит второму частичному интервалу, поэтому
разыгрываемая величина приняла возможное значение x2 = 11. Аналогично получим остальные возможные значения дискретной
случайной величины X.
Результат: последовательность смоделированных возможных значений дискретной случайной величины X такова: 3; 11; 3; 24; 3;
24; 11; 24.
1.3.3Моделирование непрерывных случайных величин с заданным законом распределения
Суть метода исключения (или метода Неймана) для моделирования непрерывной случайной величины заключается в следующем.
Пусть случайная величина X определена на конечном интервале (a;b) и плотность ее распределения ограничена, так что f(x)≤M (рис. 4). Тогда, используя пару равномерно распределенных на интервале (0;1)
17
случайных чисел 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). В противном случае точка отбрасывается, определяются координаты следующей точки, и все повторяется.
Существуют и другие многочисленные способы формирования случайных величин с различными определенными законами распределения.
1.4Проверка гипотезы о законе распределения
Вслучае равномерного распределения ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона:
|
|
|
n |
|
|
|
|||
— математическое ожидание M X |
xi |
|
1 |
|
|||||
i 1 |
|
0,5 ; |
|||||||
n |
2 |
||||||||
|
|
|
|
|
|||||
|
n |
|
|
|
|
|
|
||
— дисперсия D X |
xi M X 2 |
|
1 |
|
|
|
|
||
i 1 |
|
|
|
0,0833; |
|||||
|
|
||||||||
|
n |
12 |
|
|
|
||||
— среднеквадратичное отклонение 
D 0,2887.
Пусть в результате эксперимента получено n значений x1, x2, …, xn случайной величины X и все они заключены в пределах a < xi < b.
Суть метода проверки по гистограмме сводится к следующему. а) Выдвигается гипотеза о равномерности распределения чисел в
интервале (0;1).
18
б) Интервал (a; b) разбивается на L (любое число, не слишком большое и не слишком малое) равных подинтервалов длиной j. При генерации последовательности {xi} каждое из чисел xi с
вероятностью pj=1/L, j 1, L , попадает в один из подинтервалов. Всего в каждый j-й подинтервал попадает j чисел последовательности {xi}, i 1, n . Относительная частота попадания случайных чисел последовательности {xi} в каждый из подинтервалов будет равна j/n.
в) Над каждым из подинтервалов разбиения строится прямоугольник, площадь которого равна частоте попадания {xi} в этот подинтервал. Высота каждого прямоугольника равна частоте, деленной на j. Полученную ступенчатую линию называют
гистограммой.
г) Вид соответствующей гистограммы представлен на рис. 5, где пунктирная линия соответствует теоретическому значению pj, а сплошная – экспериментальному j/n. Очевидно, что если числа {xi} принадлежат псевдослучайной равномерно распределенной последовательности, то при достаточно больших значениях n экспериментальная гистограмма (ломаная линия на рис. 5) приблизится к теоретической прямой pj=1/L.
Гистограмма служит приближением к неизвестной плотности случайной величины X. Площадь гистограммы, заключенная между xi и xi+1, дает приближенное значение вероятности P{xi<X<xi+1}.
19
1.5 Вопросы для самоконтроля
1.Какой процесс называют случайным опытом или экспериментом?
2.Что называют случайной величиной?
3.Какой процесс называют моделированием случайной величины?
4.Какие основные способа генерации случайных чисел Вы знаете?
5.В чем заключается табличный (файловый) способ генерации случайных чисел?
6.В чем заключается алгоритмический (программный) способ генерации случайных чисел?
7.В чем заключается аппаратный (физический) способ генерации случайных чисел?
8.Какие числа называют псевдослучайными? Приведите пример их получения.
9.В чем заключается метод серединных квадратов?
10.В чем заключается метод серединных произведений?
11.В чем заключается метод перемешивания?
12.В чем заключается линейный конгруэнтный метод?
13.Чем мультипликативный конгруэнтным метод отличается от смешанного конгруэнтного метода?
14.В чем заключается Метод π?
15.Какие виды случайной величины Вам известны?
16.Что является полной характеристикой случайной величины с вероятностной точки зрения?
17.Что является универсальной формой представления закона распределения?
18. Какие основные свойства функции распределения вероятностей F(x) вам известны?
19.Какую функцию f(x) называют плотностью распределения вероятности?
20.Что называют математическим ожиданием (средним значением) случайной величины и как оно определяется?
21.Что называют дисперсия случайной величины и как она определяется?
22.Что называют стандартным или среднеквадратичным отклонением случайной величины?
23.Что количественно показывает среднеквадратичное отклонение?
20 24.Что называют выборочной средней случайной величины и как она
определяется? Чем она отличается от математического ожидания? 25.Что называют выборочной дисперсией случайной величины и как
она определяется?
26. Как задаются функции плотности вероятности и распределения непрерывной случайной величины R с равномерным распределением на интервале?
27.Как строится гистограмма?
28.Изложите суть метода проверки гипотезы о законе распределения случайной величины по гистограмме.
29.Изложите суть метода моделирования дискретных случайных величин.
30.Изложите суть метода исключения (метода Неймана) для моделирования непрерывных случайных величин.