Metod_B1.V.DV.23.01_09.03.01_04.06.2016_lz

Рекомендуется формировать не менее 1000 чисел; файл сопроводить расширением *.dat

иразместить его на диске b: .

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

6.Изменяя структуру ГПСЧ, повторить пп.4,5 несколько раз. Проанализировав визуально гистограммы, из всех вариантов выбрать ГПСЧ, для которого гистограмма наилучшим образом приближена к теоретическому виду. Запомните выбранную структуру ГПСЧ для последующих лабораторных работ; удалите с диска b: созданные Вами файлы с ПСЧ (с расширением *.dat).

7.Сделать вывод о влиянии структуры ГПСЧ на качество сгенерированных последовательностей.

8.Оформить и защитить отчет по лабораторной работе.

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

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

последовательностей на основе конгруэнтных процедур

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

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

Широкое применение получили так называемые конгруэнтные процедуры генерирования псевдослучайных последовательностей: эти процедуры описываются в виде рекуррентного соотношения, когда значение последующего хi-го числа зависит от значения предыдущего хi-1-го числа последовательности

Xi=(Lxi-1+N) MODK,

где L – множитель; N – аддитивная константа.

Начальное значение х0 выбирается в соответствии с конкретными указаниями к процедуре, число (R) MOD K есть остаток от деления на K числа R. Например, 42 MOD 25=10; L,N,K,хi являются целыми числами. Для преобразования целого числа xi в правильную дробь на

19

интервале (0,1) слева от xi подставляется запятая, т.е. xi рассматривается как дробная часть правильной дроби. Например, число xi =3269 будет преобразовано на выходе процедуры в число 0,3269. Конгруэнтная процедура получения последовательности псевдослучайных равномерно распределенных чисел может быть реализована мультипликативным либо смешанным методом.

Мультипликативный метод является частным случаем конгруэнтного при N=0; х=(Lхi-1) MODK.

В смешанном методе в отличие от мультипликативного N не равно нулю.

При выборе х0, L, N, K необходимо соблюдать следующие правила:

1.Число х0 может быть произвольным.

2.Число K должно быть велико. Удобно выбирать его равным размеру слова вычислительной машины, поскольку при этом эффективно вычисляется (L xi +N) modk.

3.Если K представляет собой степень двойки, L выбирается таким, чтобы (L)mod8=3;

L	K ; желательно выполнение условия K /100 L K			K ; последовательность
разрядов в двоичном представлении L не должна иметь регулярного вида, например,
L≠11001100…
4. Постоянная N должна быть нечетна. Желательно, чтобы
N / k 1/ 2			/ 6 0.2113248654 051871 .
		3

Конгруэнтные процедуры – не единственный источник ПСЧ. Некоторые известные методы рассмотрены в /1, 2, 3/.

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

Так, например, в языке Turbo Pascal обращение к стандартному программному датчику ПСЧ осуществляется с помощью функции RANDOM:

function RANDOM (N: WORD);

Функция возвращает одно целочисленное равномерно распределенное число в интервале

(0, N). В случае вызова функции без параметра N возвращается одно вещественное число,

равномерно распределенное в интервале (0,1).

Перед первым обращением к функции RANDOM необходимо определить начальное значение программного датчика. Программный датчик инициализируют с помощью процедуры RANDOMIZE. При этом происходит обращение к системному таймеру, и некоторое случайное число заносится в предписанную переменную с именем RANDSEED. При необходимости

20

начать генерацию с некоторого определенного состояния следует занести его значение в переменную RANDSEED присвоением.

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

В данном примере программный датчик реализован в виде функции RND на языке Turbo Pascal, которая при каждом обращении возвращает одно РРПСЧ в интервале (0,1),

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

В примере используются следующие значения констант:

L=5169, x0=7533, k=2q=216=65536.

FUNCTION RND: REAL;

{ х – глобальная переменная типа word} begin

x:=L*x; { т.к. k – целая степень числа 2, то операция (L*x) mod k сводится к выделению q младших разрядов числа L*x }

RND:=X/65536; {приведение возвращаемого числа RND к интервалу (0,1) } end;

Обращение к данной процедуре имеет вид: y:=RND;

где y – переменная типа REAL.

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

1.Изучить теоретический материал по данной теме.

2.В соответствии с полученным заданием создать программный генератор ПСЧ.

3.Пользуясь собственным программным генератором (п.2), сформировать файл ПСЧ.

Определить программно статистические оценки математического ожидания и

дисперсии для полученной последовательности.
Рекомендуется формировать не менее 1000 чисел; файл сопроводить	расширением
*.dat и разместить его на диске b.

4.Пользуясь автоматизированной системой обработки статистической информации ANALYZE.EXE, построить гистограмму статистического распределения для чисел из созданного в п.3 файла.

21

5.Сравнив полученные в п.3 статистические точечные характеристики с теоретическими и визуально оценив гистограмму, дать первичную оценку качества программного датчика.

6.Оформить и защитить отчет по лабораторной работе.

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

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

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

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

Определение выборочных оценок

Выборочное среднее	~
	M

математического ожидания M xn объемом n:

представляет собой несмещенную состоятельную оценку случайной величины. Для выборки случайных величин x1, x2,…,

	~			1	n
		x			i
	M
				n	x
					i 1

~

Выборочная дисперсия D есть несмещенная состоятельная оценка для теоретического значения дисперсии D случайной величины, определяемая следующим образом:

~	1	n	~	2
D		(xi M x )
	n 1 i 1

22

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

Выборочный корреляционный момент для двух последовательностей x1, x2,…, xn и y1, y2,…, yn

определяется по формуле:

~

1

n

~

~

(x

)( y

)

k

xy

M

x

M

y

n 1

i

i

i 1

~

~

где

Mx

и

My

– выборочные средние для приведенных последовательностей.

Рассмотрим выборку x1, x2,…, xn, xn+1,…, xn+τ объемом n+τ. Введя обозначение y1=x1+τ, y2= x2+τ,…, yn=xn+τ, получаем, что выборочный автокорреляционный момент определяется зависимостью вида:

~

1

n

~

~

)(x

)

k

(x M

x

M

x

n 1

i

i

i 1

Если последовательности независимы, то момент

~

. Нормированный

K ( ) 0

корреляционный выборочный момент

~

характеризует как независимость в

~

~

~ ~

~

~

последовательностях, так и рассеяние и определяется как

k

/

Dx Dx

, где

Dx и

Dx

выборочные дисперсии в последовательностях x1,…,xn

и x1+τ,…, xn+τ.

~

Если τ≠0, а n достаточно большое и выполняется соотношение | ( ) |

1/(n

это означает, что с доверительной вероятностью β рассматриваемая последовательность удовлетворяет гипотезе корреляционной независимости.

–

) , то

Критерии согласия

Для того, чтобы решить вопрос о согласовании теоретической функции распределения,

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

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

Наиболее распространенные из них – критерии хи-квадрат и критерии Колмагорова.

Гистограмма

Гистограмма находится по следующему алгоритму:

1.В выборочной последовательности x1, x2,…,xn определяют минимальное и максимальное значение чисел A=min(x1, …,xn); B=max(x1, …,xn) и диапазон выборки

23

2.

разбивают на М равных интервалов длиной H=(B-A)/M. Обычно разбиение производится на 20-30 интервалов.

Для каждого интервала определяется количество попаданий Si, i 1, M , где Si равно тому количеству чисел из последовательности, значения которых принадлежат i-му

интервалу. Очевидно, что

M Si

i 1

n

. Массив

	S	'	S		/ n
		i		i

представляет собой набор

частот для каждого интервала. Статистическая функция плотности распределения f*(x) определяется по формуле f * (x) Si' , где i – номер того интервала, которому принадлежит х. Графическое изображение f*(x)называется гистограммой.

3. Статистическая функция распределения F*(x)строится следующим образом:

k

определяется массив Gk Si' , k 1,M , по которому строится F*(x)=Gk, где k –

i 1

номер того интервала, которому принадлежит х.

Критерий хи-квадрат

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

1.Строят гистограмму, осуществляя разбиение всего диапазона выборки таким образом, чтобы S1≥10, i 1,M .

2.Определяют теоретические вероятности pi, i 1, M , попадания в каждый из интервалов: если f(x) – непрерывная функция плотности распределения и границы i-

го интервала равны E и Q, то

i		Q
p			f (x)dx
		E

	l
3.	Вычисляют величину r (Si npi )	2	/
	i 1

имеет хи-квадрат распределения с M-1

npi : при достаточно больших n эта величина

степенью свободы.

4.Задаются уровнем значимости q (например, q=0,05) и для заданного числа степеней свободы по таблице хи-квадрат распределения находят критическое значение rкр.

5.Если r<rкр, то с вероятностью, равной 1-q, считают, что статистическое распределение согласуется с теоретическим.

Критерий Колмагорова

24

В качестве примера расхождения между теоретической функцией распределения F(х) и

статической F*(x) рассматривается величина

L

n max | F * (x) F(x) | . Величина L имеет

закон распределения Колмагорова. Алгоритм проверки гипотезы о соответствии статистической функции распределения теоретической по критерию Колмагорова следующий:

1. В выборке х1, x2,…,xn, пользуясь алгоритмом упорядочения, расположить элементы в порядке возрастания:

х1< x2<…<xn.

2. Определить

Ln max |

xj

1 n

F(x	j	)

|

,

j

1, n

.

3. По заданному уровню значимости q из таблиц для функции распределения Колмагорова определить Lкр.

4. Если L<Lкр, то гипотеза о соответствии распределения принимается с вероятностью, равной 1-q.

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

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

Проверка равномерности

Тест комбинаций

Тест комбинаций заключается в подсчете количества единиц в l старших разрядах случайных чисел. Для случайной выборки х1, х2,…,хn получают случайную выборку целых чисел k1,k2,…,kn, где ki равно количеству единиц в старших разрядах двоичного представления числа хi. Теоретический закон появления j единиц в l разрядах двоичного числа описывается биномиальным законом распределения

p( j,l) cl j p j (1 p)l j cl j 0,5l ,

где p=1/2 – вероятность появления единицы в отдельном разряде.

Алгоритм проверки чисел тестом комбинаций следующий:

1. Определить последовательность k1,k2,…,kn.

25

2.По заданному уровню значимости протестировать последовательность k1,k2,…,kn

критериями согласия.

Тест пар

Тест пар состоит в подсчете количества единиц для каждого разряда случайного числа.

Для равномерно распределенных чисел теоретическая вероятность p появления единицы в разряде равна 1/2 (противоположное событие – появление нуля, его вероятность равна 1/2).

Алгоритм проверки по этому тесту следующий:

1.	Получить последовательность х1, х2,…,хn.
2.	Поочередно выделяя в каждом числе очередной двоичный разряд, подсчитать
	количество единиц в данном разряде среди всех n значений данного разряда.
3.	Для каждого разряда определить величину r1,r2,…,rl (l – количество разрядов), каждая
	из которых имеет хи-квадрат распределение с одной степенью свободы, по формуле:
	r	(k		np)	2	/( p(1 p)n).
			i
	i
4.	Оценить полученные результаты по критерию хи-квадрат.

Тест многомерности

Тест многомерности проверяет равномерность заполнения m-мерного гиперкуба km

группами равномерно распределенных чисел.

Алгоритм проверки чисел тестом многомерности следующий:

1.Исходную последовательность чисел х1, х2,…,хn разбивают на n/m групп по m чисел в каждой группе (n должно быть кратно m) следующим образом:

х1, х2,…,хm

хm+1, хm+2,…,х2m

…

xn-m+1, хn-m+2,…,хn

2.Каждое ребро m-мерного гиперкуба разбивают на k равных интервалов, получая при этом km гиперкубиков. При этом необходимо выполнение условия: n/(mkm)>10+20.

3.Каждая из групп чисел попадет в один из гиперкубиков. Определяют количество попаданий для каждого гиперкубика Ri, i 1, K m .

26

4. Зная теоретическую вероятность pi=1/Km,

i 1, K m

, попадания в каждый гиперкубик

и определив соответствующую статистическую вероятность

*

Ri /

n

, применяют

pi

m

критерий хи-квадрат с (Km-1) степенью свободы, где

n

K

m

( p

*

p )

2

r

2

i

i

m

i 1

p

i

Тест «Наибольшее из t»

Этот тест считается одним из наиболее критичных, алгоритм имеет вид:

1.Исходную последовательность чисел х1,х2,…,хn разбивают на подпоследовательности по t чисел в каждой.

2.Из каждой подпоследовательности выбирают наибольшее число и заносят его в величину уi, i 1,n / t (например уi=max(х1,х2,…,хt).

3.Случайные числа у1,у2,…уn/t, имеющие функцию распределения F(y)=yt проверяют по критерию Колмогорова.

Проверка случайности

Тест серий

Этот тест проверяет случайность попадания чисел в интервалы [0;0,5) и [0,5;1).

Алгоритм имеет вид:

1) в соответствие исходной последовательности х1,х2,…,хn ставят бинарную последовательность r1, r2,…rn, где

	r	0,если x 0,5
	i
		1,если x 0,5

2) в последовательности r1, r2,…rn определяют количество серий S, состоящих из знаков одного вида.

3) задают доверительную вероятность и определяют выполнение неравенства:

n 2 2

t

n1 2

< S <

n 2 2

t

n1 2

Тест монотонности

27

Этим тестом проверяется случайность по следующему алгоритму:

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

2.В величины t1, i=1,6 заносят количество групп, состоящих из i чисел (группы, состоящие из шести и более чисел, относят к i=6).

3.Строят величину

	6	6		i	i	j
V n
			(t		b )(t
	i 1	j 1

b	)a
j	ij

,

где bi, bj и aij- числовые коэффициенты; величина V имеет хи-квадрат распределения с 6 степенями свободы.

4. Задают доверительную вероятность и применяют критерий хи-квадрат.

Проверка периодичности

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

При этом для тестируемой последовательности х1,х2,…,хn отыскивают такой номер L, что xL+1=x1; xL+i+1=xi+1 и т.д.; величина L называется периодом. Если в пределах тестируемой последовательности L найти не удается, то констатируют тот факт, что L>n.

Описанные выше методы оценки качества последовательностей ПСЧ лежат в основе функционирования автоматизированной системы исследования статистической информации ANALYZE.EXE. В данной лабораторной работе используется следующие функциональные возможности системы:

-аппроксимация статистического распределения теоретическим, проверка их согласованности по критериям хи-квадрат и Колмогорова

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

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

1.Изучить теоретический материал по данной теме.

2.Используя систему GENERATO.EXE. смоделировать работу генератора ПСЧ, основанного на регистре сдвига. В качестве исходных данных рекомендуется задать

структуру ГПСЧ, отобранную по итогам лабораторного занятия №2.

Результат выполнения данного пункта – файл ПСЧ.

28