2.3. Оценка L для алгоритмов вида ...
Для оценки длины отрезка апериодичности, характерного для последовательностей вида (4), можно воспользоваться следующей элементарной вероятностной моделью. Пусть имеется конечное множество, содержащее N различных чисел. Произведем последовательность независимых опытов, в каждом из которых из этого множества извлекается и записывается одно число. Вероятность извлечения каждого числа в каждом из опытов равна 
(выборка с возвратом). Обозначим через L случайную величину: номер опыта, в котором впервые будет извлечено уже записанное число.
Теорема 3. В указанной модели для любого
Доказательство. Обозначим записанные числа через 
Легко вычислить вероятность того, что L окажется равным 
где 
:
так как
а вероятность того, что 
совпадет с одним из различных чисел 
равна 
Фиксируем произвольное 
и пусть 
. Тогда
Легко видеть, что
Так как 
то 
поэтому
и интересующую нас вероятность можно записать в форме
Рассмотрим теперь разбиение интервала 
точками 
где 
(рис. 7), и составим интегральную сумму для функции 
этому разбиению:
Из неравенства 
видно, что 
при
Рис. 7.
. Поэтому последнее слагаемое в этой сумме стремится при 
к нулю, и
Отсюда и из соотношения (9) следует (8). Теорема доказана.
Следствие. Так как математическое ожидание неотрицательной случайной величины с функцией распределения 
равно 
, то из (8) следует, что при 
Рассмотренная в настоящем пункте модель предложена в статье [75], там же получена формула (10), а теорема 3 доказана Л. Н. Большевым и Д. И. Голенко. Несмотря на грубость модели, оценки (8) и (10) оказались полезными во многих опытах, связанных со способами «перемешивания», когда теоретико-числовая оценка периода практически невозможна, В качестве N выбирается количество возможных значений функции 
в конкретной ЭВМ; тогда можно ожидать, что длина отрезка апериодичности окажется порядка 
Например, в методе п. 2.2.3 на ЭВМ «Стрела» значение функции Ф( (до нормализации) записывается в форме 
значит, 
На практике для ряда подобных алгоритмов были экспериментально обнаружены отрезки апериодичности длиной от 
до 3,5 105
Замечание. В книге [19] параграф, содержащий теорему 3, называется «Критерий проверки периодичности последовательности псевдослучайных чисел». Однако по этому «критерию» судить о качестве псевдослучайных чисел нельзя. У некоторых вполне удовлетворительных последовательностей, полученных по формуле (б), длина L гораздо больше, чем оценка (10) (фактически 
). В то же время некоторые последовательности с 
не удовлетворяют ни одному из основных тестов § 3.
