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

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

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

Наиболее часто используют два теста: частот и разрядов. Оценку производят по критерию согласия c² (КС Пирсона).

Тест частот

Функция распределения равномерно распределенных случайных чисел в диапазоне от 0 до 1 представлена на рис.14.1, а функция плотности на рис.14.2.

Рис. 14.1. Функция распределения Рис. 14.2. Функция плотности

равномерного закона равномерного закона

Тест разрядов

Для равномерного закона вероятность появления любого символа в любом разряде числа одинакова. Для десятичных чисел она равна 0,1; для двоичных – 0,5. Для проведения тестирования подсчитывается количество каждых символов в каждом разряде числа, то есть их частоты. И аналогично предыдущему вычисляется критерий c² и количество степеней свободы R. А далее проверяем попадание коэффициента доверия гипотезе в 10%-ный доверительный интервал. При отрицательном результате гипотеза отвергается.

Тест оценки случайности

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

Тест периодичности

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

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

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

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

Аналитический метод

Аналитические методы, как правило, используют метод обратной функции, названный так ввиду того, что аргумент при его применении откладывают
по оси y, а функцию снимают с оси x. Применение метода представлено
на рис. 3.8.

Применение метода обратной функции основано на теореме, что если

случайная величина Х имеет функцию плотности f(x), то случайная величина распределена равномерно в диапазоне от 0 до 1 и для вычисления j-го случайного числа используется формула:

,

Табличный метод

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

Интервал, в который попало случайное число, определяется по выполнению неравенства a_i-1 £r_j £a_i.

На основании подобия треугольников:

.