3. 1. Метод статистических испытаний. 3 страница

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

2. Сравниваются попарно два числа из последовательностей: и , где

Предположим совпадение произошло на S-м шаге (), т. е. . Тогда

Примечание: В программных датчиках чаще всего , т. е. последовательность ПСЧ строго периодична ().

3.1.4.4 Проверка достоверности гипотезы о “случайности” ПСЧ.

Исходные данные проверки:

ДСД RAND;

Количество проверяемых чисел - N;

Количество двоичных разрядов в представлении числа - k;

Т. е. проверке на “случайность” подвергаются следующая последовательность чисел:

, где

Проверка проводится в два этапа. Вначале осуществляется поверка “случайности” разряда, а затем - “случайности” числа. При невыполнении первого этапа, второй не проверяется. При выполнении двух этапов делается вывод о достоверности гипотезы о “случайности” ПСЧ.

Последовательность проверки “случайности” разряда (j-ого):

1) Подсчитывается количество чисел (из N), содержащих в j-ом разряде единицу

				...	j	...	k
				...		...

2) Определяется теоретическая вероятность того, что j-ый разряд равен единице .

3) Вычисляется величина:

4) Определяется табличное значение , где , так как все независимы.

Если , то с достоверностью a гипотеза о “случайности” разряда состоятельна (не противоречит опытным данным).

Последовательность проверки “случайности” числа:

1) Из совокупности N псевдослучайных чисел подсчитывается количество чисел , имеющих в k разрядах мантиссы ровно j единиц ():

				...	j	...	k
				...		...

2) Рассчитывается теоретическое значение вероятности того, что числа будут иметь в k разрядах мантиссы j единиц.

где .

3) Вычисляется величина:

4) Определяется табличное значение , где , т. к. последний разряд зависимый ().

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

При проверке последовательности псевдослучайных чисел на “случайность” требуется обращаться к каждому разряду числа . На рис. представлен алгоритм определения значения j-го двоичного разряда числа , где l - счетчик номера разряда, R - ячейка для хранения значения l -го разряда. В алгоритме реализован принцип перевода дробного числа из десятичной системы счисления в двоичную.

Алгоритм выделения j-го разряда i-го слова.

Рис. 3.1.7

3.1.4.5 Проверка достоверности гипотезы о “равномерности” закона распределения ПСЧ.

Исходные данные проверки:

ДСЧ RAND;

количество проверяемых чисел - N;

количество разрядов интервала [0,1] - M;

Для проверки “равномерности” распределения последовательности ПСЧ интервал разбивается на М равных по длине разрядов (M=10-15).

1) Определяем количество чисел из N попавших в j-ый разряд интервала [0,1], :

				...	j	...	M
				...		...

2) Определяется теоретическая вероятность попадания чисел в j-ый разряд интервала [0,1] в соответствии с принятой гипотезой о равномерности.

3) Вычисляется величина:

4) Определяется табличное значение , где , т. к. последний разряд зависимый ().

Если , то гипотеза о “равномерности” распределения последовательности псевдослучайных чисел достоверна с вероятностью a.

3.1.4.6 Проверка гипотезы о “некоррелированности” ПСЧ и отдельных разрядов этих чисел.

Проверка гипотезы осуществляется в два этапа. Вначале проверяется корреляция между числами, а затем - корреляция между разрядами. Корреляция между разрядами проводится лишь при невыполнении первого этапа с целью выявления “плохих” разрядов.

Проверка корреляции между числами:

Исходные данные проверки:

* ДСЧ RAND;

* количество проверяемых чисел - N;

Последовательность проверки:

Вычисляются значения оценок коэффициентов корреляции как функция от j - интервал между числами:

где - математическое ожидание СВ x. С достоверностью a . j принимает значение 1,2,...,15, т. к. считается, что при j>15 корреляция отсутствует.

В силу ЦПТ для больших N можно считать, что отклонение от r (теоретическое значение) имеет нормальное распределение, т. е.

, где Для заданной погрешности e должно выполняться следующее условие:

Теоретическое значение r=0.

Вывод: Для решения задач методом статистических испытаний необходимо брать числа из последовательности ПСЧ с шагом j, для которых выполняется условие График функции представлен на рис. 3.1.8:

Рис. 3.1.8

Для “хороших” ДСЧ график носит “затухающий” характер (см. рис.). Если затухание нарушено, т. е. имеет место выброс значений за границы e, тогда проводят проверку корреляций между разрядами.

Проверка корреляции между разрядами.

Исходные данные проверки:

* ДСЧ RAND;

* количество проверяемых чисел - N;

* количество двоичных разрядов в представлении числа - k.

Последовательность проверки:

Вычисляется оценка коэффициента корреляции как функция от S и (S, - разряды числа).

где - математическое ожидание СВ ,

;

Выражение после подстановки и принимает вид:

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

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

3.1.5 Моделирование СВ с заданным законом распределения.

Для решения задач методом статистических испытаний необходимо уметь получать значения СВ подчиненных некоторому заданному закону распределения (ЗЗР).

Значения любой СВ можно получить с помощью случайных равномерно распределенных чисел в интервале [0,1]. Для этого существует ряд методов, эффективно используемых при работе на ЭВМ.

3.1.5.1 Моделирование дискретной СВ X.

Исходные данные:

Задан закон распределения СВ X:

Необходимо построить модель ДСЧ удовлетворяющую условию: СВ X принимает значение с вероятностью .

Интервал [0,1] разобьем на n-отрезков длинной

Обозначим точки границ этих отрезков

Рис. 3.1.9

т. е.

Для построения модели воспользуемся ДСЧ RAND.

Для СВ x равномерно распределенной в [0,1] - известно, что вероятность попадания x в подинтервал не зависит от местоположения подинтервала и равна длине этого подинтервала. Т. е.

Объединяя (12) и (13), получим:

Последнее соотношение определяет алгоритм моделирования дискретной СВ:

Вызываем процедуру RAND, получаем случайное число x;

Определяем номер подинтервала (разряда), которому принадлежит x, т. е. если , тогда номер равен i, где

Присваиваем СВ X значение , т. е. .

Пример: Построить модель датчика СВ X подчиненной закону распределения, который задан в виде ряда распределения:

X
P	0,05	0,1	0,05	0,05	0,15	0,1	0,15	0,5	0,2	0,1

Модель датчика СВ:

Номер реализации	ДСЧ RAND	Номер Подинтервала	Значение СВ X=
1.	0,17
2.	0,85
3.	0,41
4.	0,03
5.	0,21
6.	0,53
7.	0,92
8.	0,74
...	...	...	...

Если все значения СВ X равновероятны, т. е. для всех то алгоритм моделирования можно упростить.

В соответствии с рассмотренным алгоритмом , если или, что тоже самое, если

Последнее неравенство равносильно утверждению о том, что целая часть числа равна i-1, т. е.

Тогда модель датчика значений ДСВ X будет иметь вид:

где int - целая часть числа.

3.1.5.2 Моделирование непрерывной СВ X.

НСВ X определена в интервале (a,b) с плотностью распределения вероятностей f(x). Необходимо построить модель ДСЧ, вырабатывающего последовательность случайных чисел с ЗЗР.

Методы моделирования делятся на точные и приближенные. К точным относятся метод обратных функций, к приближенным - метод Неймана, модифицированный метод Неймана и метод кусочной аппроксимации функции f(x).

Метод обратных функций.

Данный метод основан на следующей теореме: Если СВ X распределена по закону , то СВ равномерно распределена в [0,1].

Если функция непрерывна и строго возрастает, то существует обратная функция , которая и принимается за модель СВ X.

Рис. 3.1.10

В самом деле Пример:

Построить модель СВ X распределенной по закону:

Решение:

Отсюда модель НСВ равномерно распределенной на отрезке [a,b] имеет вид:

;

Решение:

Отсюда . Т. к. равномерно распределена в [0,1] получаем модель НСВ с показательным законом распределения:

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

Приближенные методы. Метод Неймана.

Предположим, что СВ X определена на конечном интервале [a,b].

Если f(x) определена в интервале , то границы отрезка [a,b] с учетом заданной погрешности D находятся из выражения:

Так как функция f(x) непрерывна на отрезке, значит она и ограничена . График функции f(x) лежит внутри прямоугольника со сторонами [a,b] и (см. рис. 3.1.11):

Рис. 3.1.11

Алгоритм моделирования СВ X:

Моделируем случайную точку равномерно распределенную в прямоугольнике (A,B,C,D):

где x и h - случайные числа равномерно распределенные в [0,1].

2. В качестве значений СВ X, подчиненных заданному закону f(x) выбираем такие , для которых выполняется условие:

т. е.

Геометрически это можно объяснить следующим образом: из всех точек равномерно распределенных в прямоугольнике (a,b,c,d) выбираются те, которые лежат под графиком функции f(x).

Метод прост, однако имеет существенный недостаток, а именно: велико количество точек лежащих над графиком функции f(x). Эти точки иногда называют “мертвыми”.

Модифицированный метод Неймана.

Появление этого метода продиктовано желанием уменьшить общее число “мертвых точек”. Для этого интервал [a,b] разбивается на M(M= ) подинтервалов , одинаковой длины - На каждом из подинтервалов (i-ом) как на основании строится прямоугольник высотой равной - максимальное значение f(x) на i-ом подинтервале (см рис. 3.1.12).