в работе X. Левена и Я. Вольфовица (Н. Levene and J. Wolfowitz, AnnaJs Math. Stat. 15 (1944), 58-69) введен правильный критерий монотонности (для чередующихся восходящих и нисходящих серий). В ней же обсуждались ошибки при использовании этого критерия ранее. Отдельные критерии для восходящих и нисходящих серий, предложенные выше в настоящем разделе, больше подходят для использования на компьютере, поэтому мы не приводим сложные формулы для чередования восходящих и нисходящих серий. (См. обзорную работу Д. Э. Бартона и К. Л. Маллоу [D. Е. Barton and С. L. Mallows, Annals Math. Stat. 36 (1965), 236-260].)

Среди всех рассмотренных выше критериев критерий частот и критерий сериальной корреляции кажутся более слабыми в том смысле, что почти все генераторы случайных чисел им удовлетворяют. Теоретические обоснования такого явления кратко обсуждаются в разделе 3.5 (см. упр. 3.5-26). С другой стороны, критерий монотонности является более строгим. Результаты упр. 3.3.3-23 и 24 показывают, что линейные конгруэнтные генераторы стремятся иметь серии, в некоторой степени более длинные, чем нормальные, если множитель недостаточно большой. Поэтому рекомендуется применять критерий монотонности, приведенный в упр. 14.

Критерий конфликтов также заслуживает самых наилучших рекомендаций, так как он специально предназначен для определения недостатков многих, к сожалению, широко распространенных генераторов. Основанный на идеях X. Делгаса Христиансена (Н. Delgas Christiansen) [Inst. Math. Stat, and Oper. Res., Tech. Univ. Denmark (October, 1975); не опубликовано], этот критерий получил распространение с появлением компьютеров; он предназначен для использования на компьютере и не подходит для вычислений вручную.

Читатель, вероятно, удивлен: "Зачем применять такое количество критериев?". Может показаться, что на проверку случайных чисел затрачивается больше компьютерного времени, чем на их использование! Это неверно, хотя можно переусердствовать в проверке.

Необходимость проверки последовательности с помощью нескольких критериев неоднократно отмечалась в литературе. Исследователи проверили, например, что некоторые генераторы чисел наподобие метода средин квадратов удовлетворяли критерию частот, критерию интервалов и покер-критерию, однако не удовлетворяли критерию серий. Линейные конгруэнтные последовательности с малым множителем, как известно, были проверены многими критериями, однако не выдержали проверку критерием монотонности, так как у них слишком мало серий единичной длины. Критерий "максимум-f можно также использовать для поиска плохих генераторов, которые без проверки этим критерием кажутся вполне респектабельными. Генератор "вычитания с заимствованием" не проходит проверку критерием интервалов, когда максимальная длина интервала превышает самое большое запаздывание; см. работу Ваттулайнена, Канкаала, Сааринена и Ала-Ниссила (Vattulainen, Kankaala, Saarinen, and Ala-Nissila, Coniputer Physics Communications 86 (1995), 209-226), в которой идет речь о многих других критериях. Генератор Фибоначчи с запаздыванием, для которого теоретически гарантировано, что он имеет равно-распределенные младшие значащие разряды, тем не менее не удовлетворяет простым вариантам одноразрядного критерия равномерности (см. упр. 31 и 35, а также 3.6-14).

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

Чем больше используются компьютеры, тем больше необходимо случайных чисел, и генераторы случайных чисел, которые раньше считались вполне удовлетворительными, теперь недостаточно хороши для применения в физике, комбинаторике, Стохастической геометрии и т. д. Джордж Марсалья в связи с этим ввел строгие критерии, которые превосходят классические методы, подобные критерию интервалов и покер-критерию, в том смысле, что они по сравнению с этими критериями замечают другие отклонения. Например, он нашел, что последовательность Хп+1 = (62605Х„-Н 113218009) mod 2 имеет значительное отклонение в следующем эксперименте. Было получено 2 случайных чисел Х„ и выделено 10 их старших двоичных разрядов У„ = [A„/2J. Подсчитано, сколько из 2° возможных пар {у,у) 10-разрядных чисел не появятся среди (УУз), (У2,Уз), (Уз!-!,УзО-Должно быть примерно 141909.33 отсутствующих пар со стандартным отклонением W 290.46 (см. упр. 34). Но в шести последовательных испытаниях, начиная с Xi - 1234567, выполнили расчеты и получили значение стандартного отклонения между 1.5 и 3.5, которое получилось слишком низким. Распределение оказалось слишком "плоским" для того, чтобы быть случайным, поскольку, вероятно, из 2 чисел значимыми дробями являются только 1/256 на весь период. Подобный генератор с множителем 69069 и модулем 2°, как показано, является лучшим. Марсалья и Земан (Zaman) назвали эту процедуру "обезьяний критерий", так как она позволяет подсчитать количество двухсимвольных комбинаций, которые обезьяна пропустит после печатанья на клавиатуре с 1024 клавишами (см. Computers and Math. 26,9 (November, 1993), 1-10, где приведен анализ нескольких "обезьяньих критериев").

УПРАЖНЕНИЯ

1. [10] Почему критерий серий, приведенный в п. В, следует применять к (Уо,У1), (У2,Уз), (У2п-2,У2п-1) вместо пар (Уо.УО, (У1,У2), (Уп-1,Уп)?

2. [10] Представьте приблизительный путь обобщения критерия серий для троек, четверок и т. д. вместо пар.

► 3. [М20] Сколько Uj нужно проверить в критерии интервалов (алгоритм G), прежде чем будет найдено в среднем п интервалов, если предположить, что последовательность случайна? Чему равно стандартное отклонение этой величины?

4. Докажите, что вероятности в (4) верны и для критерия интервалов.

5. [М23] "Классический" критерий интервалов Кендалла и Бабингтон-Смита рассматривает числа Uo,Ui, ... ,Un-\ как циклическую последовательность с , совпадающую с Uj. Здесь N - фиксированное число Uj, определяемое критерием. Если п - это число С/о, ..., Un-1, попадающих в интервал а < Uj < /3, то существует п интервалов в циклической последовательности. Пусть Zr - число интервалов длиной г для О < г < t и пусть

Zt - число интервалов длиной > t. Покажите, что величина V = ]Со<г<«( ~ nprfjnpr должна иметь предельное х-распределение с i степенями свободы, когда Л стремится к бесконечности, а рг заданы в (4).

6. \40\ (X. Гейрингер (Н. Geiringer).) Подсчитав частоты первых 2 000 десятичных чисел в представлении е = 2.71828 ..., мы получили х-значение 1.06, указывающее, что действительные частоты цифр О, 1, ..., 9 намного ближе к их ожидаемым значениям, чем при случайном распределении. (На самом деле х > 1.15 с вероятностью 99.9%.) Этот же критерий, примененный к первым 10000 цифр е, дает приемлемое значение = 8.61; но тот факт, что первые 2 ООО цифр так равномерно распределены, достоин удивления. Будет ли происходить то же самое, если записать е в системе счисления с другим основанием? [См. АММ 72 (1965), 483-500.]

7. \08\ Примените процедуру критерия собирания купонов (алгоритм С) с d = 3 и п = 7 к поотедовательности 1101221022120202001212201010201121. Чему равны длины семи последовательностей?

► 8. [М22] Сколько в среднем Uj нужно проверить в критерии собирания купонов, прежде чем с помощью алгоритма С будет найдено п полных множеств при предположении, что последовательность случайна? Чему равно стандартное отклонение? [Указание. См. формулу 1.2.9-(28).]

9. [М21] Обобщите критерий собирания купонов, чтобы поиск прекращался, как только будет найдено w различных значений, где w - фиксированное положительное целое число, меньшее или равное d. Какие вероятности следует использовать вместо (6)?

10. [М23] Выполните упр. 8 для более общего критерия собирания купонов, описанного в упр. 9.

11. [00] Восходящие серии в конкретной перестановке показаны в (9). Каковы нисходящие серии в этой перестановке?

12. [20] Пусть Uo, Ui, Un-i - п различных чисел. Напишите алгоритм, определяющий длины всех восходящих серий в этой последовательности. Когда ваш алгоритм завершит работу, COUNT[r] должен быть равен числу серий длиной г для 1 < г < 5, а C0UNT[6] - числу серий длиной 6 или больше.

13. [М23] Покажите, что (16) - это число перестановок из р4-д4-1 различных элементов, имеющих структуру (15).

► 14. [Mi5] Если "выбросить" элемент, который следует непосредственно за серией, то, когда Xj больше Xj+i, начнем следующую серию с Xj+2. Длины серий независимы, и можно использовать обычный х-критерий (вместо ужасно сложного метода, описанного в разделе). Чему приближенно равны вероятности для длин серий этого простого критерия монртонности?

15. [МЮ] Почему в критерии "максимум-t" предполагается, что величины Vq, V/, ..., равномерно распределены между нулем и единицей?

► 16. [15] Господин Дж. Г. Квик ("Студент") хотел использовать критерий "максимум-t" для нескольких различных значений t.

a) Положив Zjt = ma.x{Uj,Uj+i,... ,Uj+t-i), он нашел простой путь перехода от последовательности .Zo(f i), ... к последовательности Zot, Zu, для которой требуется очень мало времени и места. В чем состояла его блестящая идея?

b) Он решил модифицировать метод "максимум-t" так, чтобы j-м наблюдением было max(l/,,...,Uj+t~i); другими словами, он взял Vj = Zjt вместо Vj = Z(tj)t, как предлагается в разделе. Квик считал, что все Zj должны иметь одно и то же распределение, поэтому критерий будет даже сильнее, если использовать каждое Zjt, О < j < п,