► 19. Покажите, что критерий серий можно проанализировать по полному периоду в терминах обобщенных сумм Дедекинда, если найти формулу вероятности того, что а < Хп < 0иа < Х„+1 < 0, когда а, j3, ol , 0 - заданные целые числа, причем О < а < < m и О < а < < m. [Укозокие. Рассмотрите величину [(х - а)/т] - \ [х - Р)1т\\

20. {М29\ (У. Дитер.) Обобщите теорему Р, чтобы получить формулу для вероятности того, что Хп > Хп+1 > Хп+2, в терминах обобщенных сумм Дедекинда.

УПРАЖНЕНИЯ (часть 2)

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

Удобно использовать числа Un, лежащие между нулем и единицей. Для линейной конгруэнтной последовательности Un = Х„/т получим, что Un+i = {aUn +в}, где в = с/т и {х} определено как х mod 1. Например, формула для сериальной корреляции примет вид

с = + .( - (/ Xх)") / Ц 4).

► 21. [НМ23] (Р. Р. Ковэю (R. R. Coveyou).) Чему равно значение С в только что приведенной формуле?

► 22. [М22] Пусть о - целое число и пусть О < < 1. Если х - действительное число, принимающее значения между О и 1, и если s{x) = {ах + в}, чему равна вероятность, что s{x) < X? (Это аналог теоремы Р для "действительных чисел".)

23. 1М28] В предыдущем упражнении дана вероятность того, что Un+i < Un Чему равна вероятность Un+2 < Un+i < Un в предположении, что Un - случайное действительное число, лежащее между нулем и единицей?

24. [М29] Учитывая предположения из предыдущего упражнения и исключая случай для в - О, покажите, что ГЛ> > ГЛ>+1 > • • • > Un+t~i происходит с вероятностью

Чему равна средняя длина нисходящих серий, начиная с Un, где Un выбрано наудачу между нулем и единицей?

► 25. 1М25} Пусть а, Р, а , 0 - действительные числа, 0<а<<1,0<а<<1. Учитывая предположения из упр. 22, выясните, чему равна вероятность того, что а < X < /3 и а < s{x) < 0? (Это аналог упр. 19 для "действительных чисел".)

26. [М21] Рассмотрите генератор Фибоначчи, где Un+i = {Un + Un-i}- Предполагая, что Ui и Ui независимо наудачу выбраны между О и 1, найдите вероятность того, что Ui < U2 < Ua, Ui < Us < U2, U2 < Ui < Us п т. д. [Указание. Разделите единичный квадрат {{х,у) О < х, у < 1} на шесть частей, зависящих от относительного порядка х, у и {х -I- у}, и определите площадь каждой части.]

27. [М32] В генераторе Фибоначчи из предыдущего упражнения будем считать, что Со и Ui независимо выбраны в единичном квадрате, однако исключается следующее неравенство: Uo > U\. Определите вероятность, что Ui является началом возрастающей серии длиной к, так что Uo > Ui < < Uk > Uk+i. Сравните с соответствующими вероятностями для случайной последовательности.

28. [М35] В соответствии с формулой 3.2.1.3-(5) линейный конгруэнтный генератор с потенциалом 2 удовлетворяет условию X„-i - 2Х„ + = (о - 1)с (по модулю т).

Рассмотрим генератор, который обобщает предыдущий. Пусть f/n+i = {а + lUn - Un-\)-Как в упр. 26, разделите единичный квадрат на части, которые указывают относительный порядок C/i, С/2 и С/з для каждой пары (С/С/г). Существует ли какое-нибудь значение а, для которого все шесть возможных упорядочений имеют вероятность g, если предположить, что C/i и С/2 выбраны наудачу в единичном квадрате?

3.3.4. Спектральный критерий

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

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

А. Идеи, служащие обоснованием критерия. Наиболее важные испытания для проверки, насколько случайной будет последовательность, связаны со свойствами совместных распределений t последовательных элементов последовательности, и спектральный критерий как раз и используется для проверки гипотез об этих распределениях. Если задана последовательность ([/„*) с периодом т, то для построения критерия необходимо проанализировать множество всех т точек

{{Un,Un+i,...,Un+t-i)\0<n<m} (1)

в (-мерном пространстве.

Для простоты предположим, что задана линейная конгруэнтная последовательность {Хо,а,с,т) с максимальным периодом длиной т (так что с ф 0) или что т - простое число и с = О, а период имеет длину m - 1. В последнем случае прибавим точку (О, О, ...,0) к множеству (1), чтобы всегда было ровно т точек. Эта дополнительная точка почти не влияет на общую ситуацию, когда т большое, и делает теорию более простой. При таком предположении (1) можно переписать следующим образом:

{-{x,s{x),s{s{x)),...,s-\x)) 0<a:<m}, (2)

I. тп J

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

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

о о

°: s{x)

s{s{x))

Рис. 8. (а) Двумерная решетка, образованная всеми парами последовательных точек {Х„,X„+i), где С) Хп+1 = {137Х„ + 187) mod 256.

(b) Трехмерная решетка трехмерных строк {Хп,Хп+\,Х„+2)-

компонентами векторов, и спектральный критерий изучает такую зависимость для различных размерностей t со всеми точками вида (2).

Например, на рис. 8 показано множество точек в типичных случаях малых размерностей 2 и 3 для генератора с

s{x) = (137а; + 187) mod 256. (4)

Конечно, генератор с периодом длиной 256 едва ли будет случайным, но 256 достаточно мало, чтобы можно было начертить диаграммы и достичь некоторого понимания ситуации, прежде чем перейти к большим т, представляющим практический интерес.

Возможно, наиболее поразительным в схеме коробочек на рис. 8, (а) есть то, что их можно покрыть достаточно малым числом параллельных линий. На самом деле существует много различных семей параллельных линий, проходящих через все точки. Например, семейство, содержащее 20 приблизительно вертикальных линий, пройдет через все точки; семейство, содержащее 21 параллельную линию, наклоненную примерно под углом 30°, также пройдет через все эти точки. Вообще говоря, подобное явление наблюдается в старых садах, посаженных по некоторой системе.

Тот же генератор, рассмотренный в трех измерениях, дает 256 точек в кубе, полученных путем присоединения компонентов "второго порядка" s{s{x)) к каждой из 256 точек (х, s(x)) на плоскости рис. 8, (а), как показано на рис. 8, (Ь). Представим себе, что эта З-В-кристаллическая структура построена, как физическая модель, а именно - как куб, который мы можем вертеть в руках, как хотим; при этом можно заметить, что существуют различные семейства параллельных плоскостей, которые проходят через все данные точки. По словам Уоллеса Живена (Wallace Givens), случайность чисел проявляется "главным образом, на плоскостях".

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