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

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

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

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

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

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

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

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

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

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

Метод серединных квадратов

Пусть имеется 2n-разрядное число, меньшее 1

Возведем его в квадрат

а затем отберем средние 2n разрядов, которые и будут являться очередным числом псевдослучайной последовательности

Этому методу соответствует рекуррентное соотношение

(2)

где В [ * ] и Ц [ * ] означают соответственно дробную и целую часть числа в квадратных скобках.

Недостаток метода - наличие корреляции между числами последовательности, а в ряде случаев случайность вообще может отсутствовать. Кроме того, при некоторых i* может наблюдаться вырождение последовательности, т.е. xi = 0 при i i*.

Метод середины произведения

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

то для получения числа хi+1 необходимо перемножить хi-1 и хi

а затем отобрать средние 2n цифр этого произведения

Данному методу соответствует рекуррентное соотношение

при заданных двух начальных числах х0 и x1.

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

Мультипликативный метод

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

где Xi, ,, М - неотрицательные целые числа. Раскрывая (2) получим

Если задано начальное значение Х0, множитель и аддитивная константа , то (5) однозначно определяет последовательность целых чисел {Xi}, составленную из остатков от деления на М, членов последовательности

Таким образом, для любого i 1 справедливо неравенство Xi<М. По целым числам последовательности {Xi} можно построить последовательность {хi}={Xi/М) рациональных чисел из единичного интервала (0,1).

Мультипликативный метод задает последовательность неотрицательных целых чисел {Xi}, не превосходящих М, по формуле

т.е. это частный случаи (4) при = 0.

Для машинной реализации наиболее удобна версия М = рg, где р - число цифр в системе счисления, принятой в ЭВМ, а g - число бит в машинном слове.

Алгоритм построения последовательности для двоичной машины М = рg сводится к выполнению следующих операций:

1) выбрать в качестве Х0 произвольное нечетное число;

2) вычислить коэффициент , где - любое целое положительное число;

3) найти произведение Х0, содержащее не более 2g значащих разрядов;

4) взять g младших разрядов в качестве первого числа последовательности X1, а остальные отбросить;

5) определить дробь из интервала (0, 1);

6) присвоить Х0 = X1;

7) вернуться к пункту 3.

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

Методы проверки качества псевдослучайных чисел с равномерным законом распределения

Методы (в дальнейшем, тесты) проверки качества псевдослучайных чисел делятся на три группы:

а) тесты проверки "случайности" последовательности псевдослучайных чисел;

б) тесты проверки равномерности закона распределения;

в) тесты проверки независимости последовательности.

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

Пусть имеется - случайная величина, о законе распределения которой выдвигается некоторая гипотеза, Х - множество возможных значений . Разобьем Х на m попарно непересекающихся множеств X1, X2,... .Хm, таких, что

Выберем N независимых значении 1, 2,… N и обозначим через j количество значений Xj,. Очевидно, что математическое ожидание j равно Npj,, т.е. М[j]= Npj. В качестве меры отклонения всех j от Npj выбирается величина

При достаточно большом N величина хорошо подчиняется закону распределения 2 с (m -1) степенью свободы:

где -плотность распределения 2 с (m-1) степенью свободы.

С помощью формулы (8) при заданном уровне значимости (обычно = 0.95) можно определить нижнюю и верхнюю границы области возможного принятия гипотезы (доверительного интервала). Для этого нужно решить соответственно следующие уравнения:

где , .

В приложении А имеется таблица, в которой приведены решения уравнения

где х = или х = ,р = или р =,

Тесты проверки "случайности"

На практике обычно применяют два теста проверки "случайности": тест проверки серий и тест проверки частот и пар.

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

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

и то цифры образуют серию первого рода длины k, цифры образуют серию второго рода длины l и цифры также образуют серию первого рода длины s-k-l. Иногда для удобства элементы серий первого рода обозначают знаками "-" (минус), а второго рода - знаками "+" (плюс). В этом случае рассматриваемая последовательность будет иметь такой вид:

Подсчитаем количество гl серий второго рода длины l в последовательности псевдослучайных цифр . Пусть l= 1, 2, .... m и - количество серий второго рода с l m + 1 (они объединяются в одну группу). Обозначим общее количество серий через

Величина с т степенями свободы вычисляется по формуле:

где

Если, с заданным уровнем значимости , значение попадает в доверительный интервал, то тест проверки серий удовлетворяется.

В практике встречается также другая разновидность теста проверки серий, когда к элементам серий первого рода относят цифры, меньшие 0.5, а к элементам серий второго рода-не меньшие 0.5.

При достаточно большом объеме выборки (практически при N 20) и уровне значимости = 0.95 нижний предел общего числа серий равен:

а нижний предел числа серий элементов первого и второго родов равен:

Максимальная длина серий не должна быть больше, чем

Тест проверки равномерности закона распределения

Данный тест строится на основе применения критерия согласия 2. Пусть имеется выборка псевдослучайных чисел в интервале (0, 1). Интервал (0, 1) изменения случайной величины разбивается на m интервалов хj, j = 1, 2, ..., m, очевидно, что xm, = 1, а нижняя граница первого интервала равна нулю. Обычно принимают m =10-20.

Далее производится определение вероятности рj попадания случайной величины в j-й интервал. Для равномерного на интервале (0, 1) закона распределения рj = хj - хj-1. Затем определяется величина j , j = 1, 2, ... ,m - число попаданий случайной величины в j-й интервал и подсчитывается величина распределенная по закону 2 c (m-1) степенью свободы.

По заданному уровню значимости путем решения уравнений (9) и (10) (с помощью таблицы, приведенной в приложении А) можно определить нижнюю и верхнюю границы доверительного интервала. Если подсчитанное значение не попадает в доверительный интервал, то гипотезу о равномерном законе распределения случайной величины следует отвергнуть.

Дополнительно можно подсчитать эмпирическое математическое ожидание

и эмпирическую дисперсию

и сравнить их с теоретическими значениями соответственно 0.5 и 1/12.

Для математического ожидания можно для заданного уровня значимости определить также доверительный интервал:

где определяется из уравнения:

Значения интеграла вероятностей Ф (х) приведены в приложении Б.

Полезно бывает сравнить также теоретическую функцию распределения Р(х) и теоретическую плотность распределения f(х) случайной величины с экспериментально полученными функцией распределения F*(x) и гистограммой частот. Известно, что для случайной величины, равномерно распределенной на интервале (0, 1):

По известной выборке из N значений случайной величины экспериментальная функция распределения F*(х) определяется следующим образом:

где SN(x) равно количеству значений < х.

Гистограмма частот, являющаяся аналогом плотности распределения, строится следующим образом. Весь интервал (xmin, xmax) от наименьшего значения xmin до наибольшего значения xmax полученной выборки случайной величины разбивается на q равных промежутков длины h. Затем определяется число значений j выборки, попавших в i-ый промежуток, после чего для каждого 1 i q строится прямоугольник с основанием на i-ом промежутке и высотой j/h. Полученный чертеж называется гистограммой частот или просто гистограммой. Отметим, что при таком построении площадь i-го прямоугольника равна h * (j/h) = j, т.е. числу значений случайной величины, попавших в i-ый промежуток, а площадь всей гистограммы равна объему выборки.

Тесты проверки независимости последовательности псевдослучайных чисел

В основе этих методов лежит представление полученных псевдослучайных чисел в качестве реализации дискретного стационарного случайного процесса х(t).

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

Если при заданном уровне значимости

где - верхняя граница доверительного интервала, а z определяется из уравнения:

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

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

Изучить методы получения на ЭВМ равномерно распределенных псевдослучайных чисел и тесты проверки их качества.

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

Произвести анализ полученных результатов.

Таблица решений уравнения для распределения степенями свободы

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

Таблица значений интеграла вероятностей

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