7.Генерация равномерно-распределенных случайных чисел. Оценка их качества на тестах (по книге).

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

На практике наиболее часто применяют следующие 4 метода генерации случайных чисел:

1.Метод квадратов:

При возведении в квадрат n-разрядного числа в общем случае максимально в произведении будет 2n разряда. В качестве i-го случайного числа берется n средних разрядов предыдущего случайного числа.

2.Метод произведений:

Бреется n средних разрядов произведения двух предыдущих чисел.

3.Конгруэнтный метод:

. – сравнимо по модулю.  и m – целые положительные числа. Для получения очередного случайного числа предыдущее умножается на  и затем делится на m, а остаток от деления берется в качестве i-го случайного числа.

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

Генераторы псевдослучайных чисел современных ЭВМ как правило строятся на основании смешанного конгруэнтного метода. Качество случайных чисел, в том числе длина периода, которая является существенным показателем качества, во многом зависит от выбранных значений ,,m.

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

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

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

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

Тест частот

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

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

при 0 х 1. Для оценки равномерности по тестам частот весь диапазон существования распределения от 0 до 1 разбивают на L интервалов одинаковой длины и подсчитывают попадание случайной величины в каждый из них.

Вычисляется критерий согласия ², с количеством степеней свободы R.

По вычисленным значениям ² и R по статистическим таблицам находим коэффициент доверия гипотезе о равномерности по КС Пирсона, который должен попасть в 10% интервал 0,1Р_р0,9. В противном случае гипотеза отвергается.

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

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

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

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

Коэффициент линейной автокорреляции меняется от -1 до +1. Приведем формулу для вычисления критического значения коэффициента автокорреляции:

где n – количество пар случайных чисел;

t_крит – критическое значение критерия Стьюдента, взятое по статистическим таблицам для рекомендуемого уровня значимости =0,05 для количества степеней свободы n-2; r_крит – критическое значение коэффициента линейной автокорреляции и если вычисленное значение не меньше критического, то связь между переменными считается существенной. Если же вычисленное значение по абсолютной величине не меньше 0,8

, то такая автокорреляционная связь считается близкой к линейной.

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

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

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

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