§ 4. Проверка псевдослучайных чисел с детерминистической точки зрения
4.1. Интерпретация простейших критериев.
В гл 1, § 3 мы рассмотрели некоторые тесты, используемые для проверки псевдослучайных чисел, и отметили, что все такие тесты только необходимы, но не достаточны: они могут опровергнуть гипотезу о том, что 
независимые значения случайной величины у» но не могут доказать ее. Сузим теперь постановку вопроса: вместо «можно ли числа 
считать независимыми значениями 
зададим вопрос: можно ли числа 
использовать вместо независимых значений у в формуле
при любых 
из достаточно широкого класса?
При такой постановке вопроса рассмотренные в гл. 1 критерии оказываются и необходимыми и достаточными — каждый на своем классе функций 
Впервые такая интерпретация была изложена автором в 1968 г.
4.1.1. Критерий 
Из формулы (48) стр. 129 вытекает, что
Следовательно, малость величины 
необходима и достаточна для того, чтобы ошибка приближения (26) была мала для всех функций класса 
4.1.2. Критерий 
Разобьем интервал (0, 1) на 
интервалов 
длины которых равны 
так, что 
и все 
Обозначим через количество
значений 
при 
принадлежащих Критерий 
основан на асимптотическом распределении величины
которое не зависит от 
, а только от числа степеней свободы 
Введем множество функций 
постоянных на каждом из 
, т. е. функций вида
и таких, что
Нетрудно вычислить, что если 
, то
Используя известное неравенство 
получим оценку
причем оценка эта точная, так как при
последнее неравенство обращается в равенство. Итак,
Отсюда видно, что малость величины необходима и достаточна для того, чтобы ошибка приближения (26) была мала для всех функций класса 
Мы. знаем, однако, что к формуле (26) сводятся лишь такие алгоритмы Монте-Карло, у которых 
Стало быть, рассмотренные критерии (как и критерий Колмогорова, см. упражнение 8
гл 1 и упражнение 6 гл 7) гарантируют применимость проверенных псевдослучайных чисел 
только для расчетов по алгоритмам с 
