е) Оцените В в частном случае, рассмотренном в упр. 31: т = 79 и Y„ = {¥„-24 + yit-55) mod 2.

*3.3.3. Теоретические критерии

Несмотря на то что каждый генератор случайных чисел можно проверить с помощью критериев, приведенных в предыдущем разделе, всегда лучше иметь априорный критерий, а именно - теоретический результат, с помощью которого можно заранее сказать, насколько хороши будут проверки генератора. Такие теоретические результаты помогают понять методы генерирования намного лучше, чем эмпирические методы проб и ошибок. В этом разделе мы подробнее изучим линейные конгруэнтные последовательности. Если можно предугадать результаты определенных проверок заранее, прежде чем генерировать случайные числа, то имеется больше возможностей должным образом выбрать а, т и с.

Развитие теории такого типа весьма сложно, хотя достигнут определенный прогресс. Получены пока далекие от общих результаты для статистических критериев, которые можно применять к полным периодам. Тем не менее статистические критерии приобретают смысл, когда они применяются ко всему периоду; например, критерий равномерности будет давать отличные результаты и без этого требования, но критерий серий, критерий интервалов, критерий перестановок, максимум-критерий и другие можно плодотворно проанализировать на всем периоде. Такие исследования будут определять глобальную "неслучайность" последовательности, т. е. неправильное поведение очень больших выборок.

Теория, которая будет здесь рассматриваться, вполне всеобъемлюща, однако она не исключает необходимости проверять локальные "неслучайности" методами, приведенными в разделе 3.3.2. Действительно, любая проверка с использованием только коротких последовательностей очень сложна. Известно лишь несколько теоретических результатов, касающихся поведения линейной конгруэнтной последовательности на промежутке, меньшем, чем целый период (они обсуждаются в конце раздела 3.3.4; см. также упр. 18).

Начнем с доказательства простого априорного закона для наименее сложного случая - для критерия перестановок. Суть нашей первой теоремы состоит в том, что для последовательности с большим потенциалом примерно в половине случаев выполняется неравенство Xn+i < Хп-

Теорема Р. Пусть а, с и т образуют линейную конгруэнтную последовательность с максимальным периодом. Пусть Ь = а - Ind - наибольший общий делитель т и Ь. Вероятность того, что X„+i < Х„, равна Ч- г, где

г = {2{с mod d)-d)/2т; (1)

следовательно, г < d/2m.

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

s{x) = {ах + с) mod т. (2)

Таким образом, Xn+i = s(X„) и теорема сводится к подсчету количества целых X, таких, что О < ж < т, а s{x) < х, поскольку такое число встречается где-то в

периоде. Необходимо показать, что это число равно

(т + 2(cmodd) - d).

Функция \(х - s{x)) /тп] равна 1, когда х > s(x), и О - в противном случае. Следовательно, искомое число, которое мы хотим подсчитать, можно записать следующим образом:

0<i<m

X - s{x)

Ex / ах + с ах + с \ т У т I т j) 0<i<m

0<х<т

(Вспомним, что f-J/] = - [j/J и Ь = а- 1.) Такие суммы можно подсчитать, используя методы из упр. 1.2.4-37, в котором было доказано, что

0<j<k

hj 4- с

= "f-g+glc/gj, S = gcd(/.,fc), (5)

для любых целых Л и fc, fc > О (gcd - наибольший общий делитель). Так как а и тп - взаимно простые числа, эта формула дает

0<i<m <-0<i<m

ах + С т

Ьх + с т

(а - 1)(т- 1)

+ с.

(Ь-1)(т-1) d-1 . ...

= ---- + - + c-{cmodd)

и (3) следует немедленно.

Доказательство теоремы Р указывает, что априорные критерии можно исследовать, если уметь удовлетворительно обращаться с суммами, содержащими функции L J и f Во многих случаях наиболее мощной техникой оперирования функциями "пол" и "потолок" является их замена двумя отчасти более симметричными операциями:

S{x) = [xj + 1- \х] = [ж-целое число]; (6)

Цх)) =х-1х\-1+ S{x) = :с - М + 1 - Six) = х - {[xj + \х]). (7)

Последняя функция - это "пилообразная" функция, встречающаяся в теории рядов Фурье. На рис. 7 приведен ее график. Причина того, что мы предпочитаем работать С функцией {{х)), а не С [х\ или fa;], состоит в том, что {{х)) обладает несколькими очень полезными свойствами:

{{-х)) = -{{х)); (8)

{{х + п)) = {{х)) для целого п; (9)

((па;)) = ((х))+х4--!-••+ж4- для целого п > 1 (10)

Рис. 7. Пилообразная функция {(х)).

(см. упр. 2).

Для приобретения практических навыков работы с этими функциями докажем теорему Р снова, на этот раз, не используя упр. 1.2.4-37. С помощью равенств (7)-(9) можно показать, что

X - sjx) ffx-iax + c)\\ 1 1,1, m ))2

X - s(x) ffbx + c\\ 1

так как [х - s{x))/m никогда не будет целым числом. Легко видеть, что

Ex- s{x)

= 0,

0<х<т

поскольку И X, И s{x) принимают значение из {0,1,... ,т - 1} точно один раз. Следовательно, (И) влечет

0<х<т

X - s{x)

(12)

0<х<т

получим

Пусть Ъ - bod, тп = mod, где bo и то - взаимно простые числа. Нам известно, что {Ьох) mod mo принимает значения {О, 1, ..., то - 1} в некотором порядке, когда х изменяется от О до то - 1. Из (9), (10) и равенства

0<i<m 0<i<mo

- Е ((Э)=<(г))•

0<i<mo

Теорема Р немедленно следует из (12) и (13).

Одно из следствий теоремы Р таково: практически при любом выборе а и с можно получить приемлемые вероятности того, что Xn+i < А„, по крайней мере