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

4.1. Интерпретация простейших критериев.

В гл 1, § 3 мы рассмотрели некоторые тесты, используемые для проверки псевдослучайных чисел, и отметили, что все такие тесты только необходимы, но не достаточны: они могут опровергнуть гипотезу о том, что независимые значения случайной величины у» но не могут доказать ее. Сузим теперь постановку вопроса: вместо «можно ли числа считать независимыми значениями зададим вопрос: можно ли числа использовать вместо независимых значений у в формуле

при любых из достаточно широкого класса?

При такой постановке вопроса рассмотренные в гл. 1 критерии оказываются и необходимыми и достаточными — каждый на своем классе функций Впервые такая интерпретация была изложена автором в 1968 г.

4.1.1. Критерий Из формулы (48) стр. 129 вытекает, что

Следовательно, малость величины необходима и достаточна для того, чтобы ошибка приближения (26) была мала для всех функций класса

4.1.2. Критерий Разобьем интервал (0, 1) на интервалов длины которых равны так, что и все Обозначим через количество

значений при принадлежащих Критерий основан на асимптотическом распределении величины

которое не зависит от , а только от числа степеней свободы

Введем множество функций постоянных на каждом из , т. е. функций вида

и таких, что

Нетрудно вычислить, что если , то

Используя известное неравенство получим оценку

причем оценка эта точная, так как при

последнее неравенство обращается в равенство. Итак,

Отсюда видно, что малость величины необходима и достаточна для того, чтобы ошибка приближения (26) была мала для всех функций класса

Мы. знаем, однако, что к формуле (26) сводятся лишь такие алгоритмы Монте-Карло, у которых Стало быть, рассмотренные критерии (как и критерий Колмогорова, см. упражнение 8

гл 1 и упражнение 6 гл 7) гарантируют применимость проверенных псевдослучайных чисел только для расчетов по алгоритмам с