23. Существующие методы проверки качества генераторов случайных чисел.
От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайная последовательность, порождаемая ГСЧ, должна удовлетворять целому ряду критериев.
Осуществляемые проверки бывают двух типов:
проверки на равномерность распределения;
проверки на статистическую независимость.
Проверки на равномерность распределения 1___ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона:
мат ожидание: mr=Σri/n≈0,5
дисперсия: Dr=Σ (ri-mr)^2/n≈0,0833
среднеквадрат. отклонение: σ r = sqrt(Dr)≈0,2887
2___Частотный тест
позволяет выяснить, сколько чисел попало в интервал: (mr - σ r; mr + σ r), т.е. (0.5 – 0.2887; 0.5 + 0.2887)
в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел
Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5), должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1).
3___Проверка по критерию «хи-квадрат»
это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.
процедура проверки имеет следующий вид.
Диапазон от 0 до 1 разбивается на k равных интервалов.
Запускается ГСЧ N раз (N должно быть велико, например, N/k > 5).
Определяется количество случайных чисел, попавших в каждый интервал: ni, i = 1, …, k.
Вычисляется экспериментальное значение X^2эксп. по следующей формуле:
Проверки на статистическую независимость 1___Проверка на частоту появления цифры в последовательности
Рассмотрим пример. Случайное число 0.2463389991 состоит из цифр 2463389991, а число 0.5467766618 состоит из цифр 5467766618. Соединяя последовательности цифр, имеем: 24633899915467766618.
Понятно, что теоретическая вероятность pi выпадения i-ой цифры (от 0 до 9) равна 0.1.
Далее следует вычислить частоту появления каждой цифры в выпавшей экспериментальной последовательности.
Например, цифра 1 выпала 2 раза из 20, а цифра 6 выпала 5 раз из 20.
Далее считают оценку и принимают решение по критерию «хи-квадрат».
2___Проверка появления серий из одинаковых цифр
Обозначим через nL число серий одинаковых подряд цифр длины L. Проверять надо все L от 1 до m, где m — это заданное пользователем число: максимально встречающееся число одинаковых цифр в серии.
В примере «24633899915467766618» обнаружены 2 серии длиной в 2 (33 и 77), то есть n2 = 2 и 2 серии длиной в 3 (999 и 666), то есть n3 = 2.
Вероятность появления серии длиной в L равна: pL = 9 · 10–L (теоретическая). То есть вероятность появления серии длиной в один символ равна: p1 = 0.9 (теоретическая). Вероятность появления серии длиной в два символа равна: p2 = 0.09 (теоретическая). Вероятность появления серии длиной в три символа равна: p3 = 0.009 (теоретическая).
Например, вероятность появления серии длиной в один символ равна pL = 0.9, так как всего может встретиться один символ из 10, а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0.1 · 0.1 · 9, то есть вероятность 0.1 того, что в первой позиции появится символ «X», умножается на вероятность 0.1 того, что во второй позиции появится такой же символ «X» и умножается на количество таких комбинаций 9.
Частость появления серий подсчитывается по ранее разобранной нами формуле «хи-квадрат» с использованием значений pL
Примечание: генератор может быть проверен многократно, однако проверки не обладают свойством полноты и не гарантируют, что генератор выдает случайные числа. Например, генератор, выдающий последовательность 12345678912345…, при проверках будет считаться идеальным, что, очевидно, не совсем так.
