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

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

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

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

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

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

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

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

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

СТАТИСТИЧЕСКОЕ ОЦЕНИВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СЛУЧАЙНЫХ ЧИСЕЛ

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

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

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

Выборочное среднее представляет собой несмещенную состоятельную оценку математического ожидания M случайной величины. Для выборки случайных величин x₁, x₂,…, x_n объемом n:

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

Корреляционный момент – это характеристика зависимости между числами последовательности. Он зависит от расстояния между элементами последовательности. Выборочный корреляционный момент для двух последовательностей x₁, x₂,…, x_n и y₁, y₂,…, y_n определяется по формуле:

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

Рассмотрим выборку x₁, x₂,…, x_n, x_n+1,…, x_n+τ объемом n+τ. Введя обозначение y₁=x_1+τ, y₂= x_2+τ,…, y_n=x_n+τ, получаем, что выборочный автокорреляционный момент определяется зависимостью вида:

Если последовательности независимы, то момент . Нормированный корреляционный выборочный момент характеризует как независимость в последовательностях, так и рассеяние и определяется как , где – выборочные дисперсии в последовательностях x₁,…,x_n и x_1+τ,…, x_n+τ.

Если τ≠0, а n достаточно большое и выполняется соотношение , то это означает, что с доверительной вероятностью β рассматриваемая последовательность удовлетворяет гипотезе корреляционной независимости.

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

Для того, чтобы решить вопрос о согласовании теоретической функции распределения, которой должны подчиняться получаемые последовательности случайных чисел, и статистической функции распределения, которая может быть определена построением гистограммы для полученной последовательности, применяют критерии согласования. Наиболее распространенные из них – критерии хи-квадрат и критерии Колмагорова.

Гистограмма

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

1. В выборочной последовательности x₁, x₂,…,x_n определяют минимальное и максимальное значение чисел A=min(x₁, …,x_n); B=max(x₁, …,x_n) и диапазон выборки разбивают на М равных интервалов длиной H=(B-A)/M. Обычно разбиение производится на 20-30 интервалов.

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

3. Статистическая функция распределения F*(x)строится следующим образом: определяется массив , по которому строится F*(x)=G_k, где k – номер того интервала, которому принадлежит х.

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

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

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

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

3. Вычисляют величину : при достаточно больших n эта величина имеет хи-квадрат распределения с M-1 степенью свободы.

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

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

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

В качестве примера расхождения между теоретической функцией распределения F(х) и статической F*(x) рассматривается величина . Величина L имеет закон распределения Колмагорова. Алгоритм проверки гипотезы о соответствии статистической функции распределения теоретической по критерию Колмагорова следующий:

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

х₁< x₂<…<x_n.

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

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

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

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

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

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

Тест комбинаций заключается в подсчете количества единиц в l старших разрядах случайных чисел. Для случайной выборки х₁, х₂,…,х_n получают случайную выборку целых чисел k₁,k₂,…,k_n, где k_i равно количеству единиц в старших разрядах двоичного представления числа х_i. Теоретический закон появления j единиц в l разрядах двоичного числа описывается биномиальным законом распределения

,

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

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

1. Определить последовательность k₁,k₂,…,k_n.

2. По заданному уровню значимости протестировать последовательность k₁,k₂,…,k_n критериями согласия.

Тест пар

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

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

1. Получить последовательность х₁, х₂,…,х_n.

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

3. Для каждого разряда определить величину r₁,r₂,…,r_l (l – количество разрядов), каждая из которых имеет хи-квадрат распределение с одной степенью свободы, по формуле:

4. Оценить полученные результаты по критерию хи-квадрат.

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

Тест многомерности проверяет равномерность заполнения m-мерного гиперкуба k^m группами равномерно распределенных чисел.

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

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

х₁, х₂,…,х_m

х_m+1, х_m+2,…,х_2m

_…

x_n-m+1, х_n-m+2,…,х_n

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

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

4. Зная теоретическую вероятность p_i=1/K^m, , попадания в каждый гиперкубик и определив соответствующую статистическую вероятность , применяют критерий хи-квадрат с (K^m-1) степенью свободы, где

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

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

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

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

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

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

Тест серий

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

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

1. в соответствие исходной последовательности х₁,х₂,…,х_n ставят бинарную последовательность r₁, r₂,…r_n, где

2. в последовательности r₁, r₂,…r_n определяют количество серий S, состоящих из знаков одного вида.

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

_{< S <}

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

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

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

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

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

,

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

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

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

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

При этом для тестируемой последовательности х₁,х₂,…,х_n отыскивают такой номер L, что x_L+1=x₁; x_L+i+1=x_i+1 и т.д.; величина L называется периодом. Если в пределах тестируемой последовательности L найти не удается, то констатируют тот факт, что L>n.

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

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

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