в таком порядке: < ••• < 5(„). Пусть R - число равных промежутков, а

именно - число индексов j, таких, что 1 < j < п и Зу) = Sj-i). Когда m = 2 и п = 512, должно получиться следующее.

R = О 1 2 3 или больше

С вероятностью .368801577 .369035243 .183471182 .078691997

(Среднее число равных промежутков для выбранных тип должно быть равным приблизительно 1.) Примените этот критерий, скажем, 1 ООО раз и воспользуйтесь Х-критерием с тремя степенями свободы, чтобы сравнить эмпирические значения Ri с правильным распределением. Так можно выяснить, будет ли генератор вырабатывать приемлемые случайные промежутки между днями рождений. В упр. 28-30 развивается теория, связанная с этим критерием, и приводятся формулы для других значений тип.

Такой критерий, как критерий промежутков между днями рождений, в первую очередь, важен в связи с тем замечательным фактом, что генератор Фибоначчи с запаздыванием не удовлетворяет этому критерию, хотя он вполне удовлетворяет другим традиционным критериям. [Драматические примеры таких неудач приведены Марсалья, Земаном и Тсангом (Marsaglia, Zaman, and Tsang, Stat, and Prob. Letters 8 (1990), 35-39).] Рассмотрим, например, последовательность

Хп = {Хп-24 + Хп-ьб) mod т из 3.2.2-(7). Числа этой последовательности удовлетворяют соотношению

Хп + Хп-86 = Хп-24 + Хп-31 (по модулю 7п),

так как обе стороны конгруэнтны Хп-24 + Хп-55 + Хп-86- Поэтому две пары разностей равны

Хп ~ Хп-24 = -п-З! - Хп-86

Хп - Хп-31 = Хп-24 ~ Хп-8Ь-

Всякий раз, когда Х„ приемлемо близко к Хп-24 или Xn-zi (как должно было бы произойти в настоящей случайной последовательности), одна и та же разность имеет хороший шанс появиться в двух промежутках. Получится значительно больше случаев равенств (обычно со средним Л и 2, а не 1). Но если исключить из R любой равный промежуток, возникающий из условий конгруэнтности, то полученная статистика R будет удовлетворять критерию дней рождений. (Один из способов избежать неудачи состоит в том, чтобы отбрасывать определенные элементы последовательности, используя, например, только Xq, Х2, Х4, ... как случайные числа. Тогда мы никогда не получим все четыре элемента множества {Х„, Х„ 24, Х„ з1, Х„ 8б} и в критерии промежутков между днями рождений исчезнут проблемы. Существует даже лучший способ избавиться от проблем - отбросить последовательные группы чисел, как предложил Люшер (Liischer); см. раздел 3.2.2. Подобные замечания можно использовать для генераторов вычитания с заимствованием и суммирования с переносом из упр. 3.2.1.1-14.)

к. Критерий серигшьной корреляции. Можно подсчитать следующую статистику:

niUoUi+UiU2 + - +Un-2Un-i + Un-iUo)-{Uo + Ui + - +Un-i? n(C/2 + u + ... + ul ) (C/o + [/i + • • • + Un-i?

(23)

Это коэффициенты сериальной корреляции, мера зависимости Uj+i от Uj.

Коэффициенты корреляции часто появляются в статистических работах. Если задано п величин Uq, Ui, Un-i и п других величин Vq, Vi, Vn-i, то коэффициент корреляции между ними определяется следующим образом:

Все суммирования в этой формуле производятся по области О < j < п; формула (23) - это частный случай последней формулы для V} = mod n- Знаменатель в (24) равен О, когда Uq = Ui = = Un-i или Vq = Vi = = Vn-i, поэтому мы исключаем из рассмотрения такой случай.

Коэффициент корреляции всегда лежит между -1 и Когда он равен О или очень мал, значит, величины Uj и Vj независимы одна от другой (говоря более точно, между ними нет линейной зависимости. - Прим. ред.); если же значение коэффициента корреляции равно ±1, это означает полную линейную зависимость. Действительно, в таком случае Vj = а±pUj для всех j и некоторых констант а и Р (см. упр. 17).

Следовательно, С в (23) должно быть как можно ближе к 0. На самом деле, поскольку UqUi не является полностью независимым от U1U2, нельзя ожидать, что сериальный коэффициент корреляции будет точно равен О (см. упр. 18). "Хорошим" значением С будет значение, находящееся между „ - 2ап и /г„ + 2сг„, где

Ожидается, что С находится между этими значениями в 95% случаев.

Формула для cг в (25) - это верхняя граница сериальных корреляций между произвольно распределенными независимыми переменными. Когда Ui равномерно распределены, то истинная дисперсия равна п~ + 0{n~\ogn) (см. упр. 20).

Вместо обычного коэффициента корреляции между наблюдениями (С/о, Ui,..., Un-i) и их соседями (Ui,... ,Un-i,Uo) можно вычислить коэффициент корреляции между (Uq, Ui, ..., Un-i) и любой циклически смещенной последовательностью (Ug,Un-i,Uo, Ug-i). Циклическая корреляция должна быть небольшой для О < 9 < п. Непосредственное вычисление по формуле (24) для всех q потребует около п операций умножения, однако на самом деле можно подсчитать все корреляции всего за O(nlogn) шагов, если использовать быстрое преобразование Фурье. (См. раздел 4.6.4, а также работу L. Р. Schmid, CACM 8 (1965), 115.)

L. Критерий подпоследовательностей. Внешние программы часто вызывают случайные числа пакетами. Например, если программа работает со случайными переменными А, ¥и Z, она может потребовать одновременного генерирования трех

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

Uo,Uq,U2q, Ui,Uq+l,U2q+l, . ; Uq-l,U2q-l,Uzq-l,

может быть проверена с помощью описанных выше критериев для первоначальной последовательности Uq, Ui, U2, ....

Опыты с линейными конгруэнтными последовательностями показали, что поведение этих порожденных последовательностей редко бывает менее случайным, чем поведение первоначальной последовательности, если только q не имеет большого множителя, общего с длиной периода. На бинарном компьютере с т, равным длине компьютерного слова, например, критерий подпоследовательностей для q = 8 даст результаты, худшие среди всех 9 < 16, а на десятичном компьютере значение q = 10 приведет к получению наиболее неудовлетворительных подпоследовательностей. (Это можно объяснить, в некоторой степени основываясь на потенциале, так как подобные значения q имеют тенденцию к уменьшению потенциала. В упр. 3.2.1.2-20 приведено более подробное объяснение.)

М. Исторические замечания и дальнейшее обсуждение. Статистические критерии, естественно, возникли в связи с потребностью доказать или опровергнуть гипотезы относительно различных наблюдений. Хорошо известны две ранние работы, посвященные проверке случайности искусственно генерируемых чисел. Это две статьи М. Дж. Кендалла и Б. Бабингтон-Смита (М. G. Kendall and В. Babington-Smith, Journal of the Royal Statistical Society 101 (1938), 147-166; также в этом журнале см. 6 (1939), 51-61). В приведенных работах внимание было сосредоточено в большей степени на проверке случайности цифр между О и 9, чем на случайности реальных чисел; с этой целью авторы обсуждали критерий частот, критерий серий, критерий интервалов и покер-критерий, однако они неудачно применяли критерий серий. Кендалл и Бабингтон-Смит использовали также вариант критерия собирания купонов. Метод, описанный в этом разделе, был введен Р. Е. Гринвудом (R. Е. Greenwood, Math. Сотр. 9 (1955), 1-5.)

Критерий монотонности имеет довольно интересную историю. Первоначально он рассматривался для восходящих и нисходящих серий одновременно. Восходящие серии следовали за нисходящими, затем - восходящие серии и т. д. Заметим, что критерий монотонности и критерий перестановок зависят не от того, имеет ли С/„ равномерное распределение, а от того факта, что Ui = Uj появляется с вероятностью О, когда i ф j. Поэтому данные критерии могут применяться ко многим типам случайных последовательностей. Критерий монотонности в примитивной форме введен И. Ж. Бьенэйме (J. Bienayme, Comptes Rendus Acad. Sci. Paris 81 (1875), 417-423). Примерно через шестьдесят лет В. О. Кермак и А. Г. Мак-Кендрик опубликовали две обширные статьи на эту тему (W. О. Kermack and А. G. McKendrick, Proc. Royal Society Edinburgh 57 (1937), 228-240, 332-376). В качестве примера они установили, что количество выпавших в Эдинбурге осадков между 1785 и 1930 годами носило "всецело случайный характер" по отношению к критерию монотонности (хотя они проверяли только среднее и стандартное отклонения длин серий). Другие исследователи также начали использовать этот критерий, но только в 1944 году было показано, что использовать х-метод в этом критерии неправомочно.