AOP_Tom2 (1021737), страница 15
Текст из файла (страница 15)
3.5-26). С другой стороны, критерий монотонности является более строгим. Результаты упр. З.З.З вЂ” 23 и 24 показывают, что линейные конгруэнтные генераторы стремятся иметь серии, в некоторой степени более длинные, чем нормальные, если множитель недостаточно большой. Поэтому рекомендуется применять критерий монотонности, приведенный в упр. 14. Критерий конфликтов также заслуживает самых наилучших рекомендаций, так как он специально предназначен для определения недостатков многих, к сожалению, широко распространенных генераторов. Основанный на идеях Х.
Делгаса Христиансена (Н. Ве!как СЬг!э11апэеп) [1пэа Ма1Ь. 81а1. апг! Орег. Неэ., ТесЬ. 1,"п1ю ПепшагЬ (ОсгоЬег, 1975); не опубликовано], этот критерий получил распространение с появлением компьютеров; он предназначен для использования на компьютере и не подходит для вычислений вручную, Читатель, вероятно, удивлен: "Зачем применять такое количество критериев?". Может показаться, что на проверку случайных чисел затрачивается болыпе компьютерного времени, чем на их использование! Это неверно, хотя можно переусердствовать в проверке.
Необходимость проиерки последовательности с помощью нескольких критериев неоднократно отмечалась в литературе. Исследователи проверили, например, что некоторые генераторы чисел наподобие метода средин квадратов удовлетворяли критерию частот, критерию интервалов и покер-критерию, однако не удовлетворяли критерию серий. Линейные конгруэнтные последовательности с малым множителем, как известно, были проверены многими критериями, однако не выдержали проверку критерием монотонности, так как у них слишком мало серий единичной длины. Критерий "максимум-1" можно также использовать для поиска плохих генераторов, которые без проверки этим критерием кажутся вполне респектабельнымн. Генератор "вычитания с заимствованием" ие проходит проверку критерием интервалов, когда максимальная длина интервала превышает самое большое запаздывание; см.
работу Ваттулайнена, Канкаала, Сааринена н Ала-Ниссила (Ча11и1а1пеп, Капйаа1а, Зааг!пеп, апб А!а-Н)аз!!а, Сотри1ег Р!~уясз Соттип1саг1опз 86 (1995), 209 — 226), в которой идет речь о многих других критериях. Генератор Фибоначчи с запаздыванием, для которого теоретически гарантировано, что он имеет равно- распределенные младшие значащие разряды, тем не менее не удовлетворяет простым вариантам одноразрядного критерия равномерности (см, упр.
31 и 35, а также 3.6-14). Возможно. основной смысл экстенсивной проверки генераторов случайных чисел состоит в том, что людям, неправильно применяющим генератор случайных чисел господина Х, будет тяжело допустить, что на самом деле неправильна их собственная программа. Они будут обвинять генератор до тех пор, пока господин Х не докаг»сею им., что его числа достаточно случайны. С другой стороны, если источник случайных чисел предназначен только для личного использования господином Х, последний может не беспокоиться о его проверке, так как с большой вероятностью технических рекомендаций, приведенных в настоящей главе, достаточно для проверки этого датчика.
Чем больше используются компьютеры, тем больше необходимо случайных чисел, и генераторы случайных чисел, которые раньше считались вполне удовлетворительными, теперь недостаточно хороши для применения в физике, комбинаторике, Стохастической геометрии и т. д. Джордж Марсалья в связи с этим ввел строгие кри»перви, которые превосходят классические методы, подобные критерию интервалов и покер-критерию, в том смысле, что онн по сравнению с этими критериями замечают другие отклонения. Например, он нашел, что последовательность Х„+» — — (62605Хо+113218009) п»о»1 2гг имеет значительное отклонение в следующем эксперименте, Было получено 2г» случайных чисел Х„и выделено 10 их старших двоичных разрядов У„= [Х„/2»г). Подсчитано, сколько из 2га возможных пар (р,у') 10-разрядпых чисел не появятся среди (У»,1г)., (Уг, Уг),, (1гг»-»,1гг»).
Должно быть примерно 141909.33 отсутствующих пар со стандартным отклонением щ 290.46 (см. упр. 34). Но в шести последовательных испытаниях, начиная с Х» —— 1234567, выполнили расчеты и получили значение стандартного отклонения между 1.5 и 3.5, которое получилось слишком низким. Распределение оказалось слишком "плоским" для того, чтобы быть случайным, поскольку, вероятно, из 2гг чисел значимыми дробямн являются только 1/256 на весь период. Подобный генератор с множителем 69069 и модулем 2га, как показано, является лучшим. Марсалья и Земан (Хашап) назвали эту процедуру "обезьяний критерий", так как она позволяет подсчитать количество двухсимвольных комбинаций, которые обезьяна пропустит после печатанья на клавиатуре с 1024 клавишами (см.
Сопгрпсеге ап») Масй. 26,9 (НоуешЬег, 1993), 1-10, где приведен анализ нескольких "обезьяньих критериев"). УПРАЖНЕНИЯ 1. [10) Почему критерий серий, приведенный в п. В, следует применять к (Уа»У»), (1г, Уг),..., (Уг — г, Уг -») вместо пар (1е, У»), (У», Уг),..., (У -», У,)? 2. [10[ Представьте приблизительный путь обобщения критерия серий для троек, четверок и т.
д. вместо пар. 3. [М20[ Сколько 11 нужно проверить е критерии интервалов (елгоритг» С), прежде чел» будет найдено в среднем и интервалов, если предположить, что последовательность случайна? Чему равно стандартное отклонение этой величины? 4. [М12) Докажите, чта вероятности в (4) верны и для критерия интервалов. б. [М20[ "Классический" критерий интервалов Кендалла и Бабивгтон-Смита рассматривает числа 1?а, 11»,..., Цг» кек циклическую последовательность с 1?г»».г, совпадающую с?1». Здесь»»" -- фиксированное число б»1, определяемое критерием. Если п — это числа 1»е, ..., 11»»», попадающих в интервал о < б» <,0, то существует и интервалов в циклической последовательности. Пусть ń— число интервалов длиной г для 0 < г < 1 и пусть Я~ — число интеРвалов длиной > б Покажите, что величина К = 2 ес,<,(Е, — пР,) /пР, должна иметь предельное т -распределение с 1 степенями свободы, когда )у стремится к бесконечности, а р„заданы в (4).
6. [40] (Х. Гейрингер (Н. Се!Нпбег).) Подсчитав частоты первых 2000 десятичных чисел в представлении е = 2.?1828..., мы получили Хз-значение 1.06, указывающее, что действительные частоты цифр О, 1, ..., 9 намного ближе к их ожидаемым значениям, чем при случайном распределении. (На самом деле 1~~ > 1.15 с вероятностью 99.9%.) Этот же критерий, примененный к первым 10000 цифр е, дает приемлемое значение Кз = 8.61; но тот факт, что первые 2 000 цифр так равномерно распределены, достоин удивления. Будет ли происходить то же самое, если записать е в светелке счисления с другим основанием? [См.
АММ 72 (1955), 483-500.] 7. [08] Примените процедуру критерия собирания купонов (алгоритм С) с Ы = 3 и и = ? кпосчедовательности 1101221022120202001212201010201121. Чему равны длины семи последовательностей? 8. [М22] Сколько в среднем П нужно проверить в критерии собирания купонов, прежде чем с помощью алгоритма С будет найдено и полных множеств при предположении, что последовательность случайна? Чему равно стандартное отклонение? [Указание. См.
формулу 1,2.9 — (28).) 9. [М21) Обобщите критерий собирания купонов, чтобы поиск прекращался, как только будет найдено ш различных значений, где ш -- фиксированное положительное целое число, меньшее или равное 4. Какие вероятности следует использовать вместо (б)? 10. [Мйу] Выполните упр. 8 для более общего критерия собирания купонов, описанного в упр. 9. 11. [00) Восходящие серии в конкретной перестагювке показаны в (9). Каковы нисходящие серии в этой перестановке? 12. [20) Пусть Пе, Пм ..., К, ~ — и различных чисел. Напишите алгоритм, определяющий длины всех восходящих серий в этой последовательности.
Когда ваш алгоритм завершит рабату, 00067[с] должен быть равен числу серий длиной г для 1 < г < 5, а С0067[6] — числу серий длиной 6 или болыпе. 13. [М23) Покажите, что (16) — это число перестановок из р+д+1 различных элементов, имеющих структуРу (1э). ь 14. [М15) Если "выбросить" элемент, который следует непосредственно за серией, то, когда Хз больше Хгьм начнем следующую серию с Х ьь Длины серий независимы, и можно использовать обычный ~~-критерий (вместо ужасна сложного метода, описанного в разделе). Чему приближенно равны вероятности для длин серий этого простого критерия монотонности? 15.
[М10] ПочемУ в кРитеРии "максимУм-1' пРедполагаетса, что величины 1ге', К, ..., 1:„', равномерно распределены между кулем и единицей? ь 16. [И] Господин Дж. Г. Квик (" Студент" ) хотел использовать критерий "максимум 1" для нескольких различных значений б а) Положив Яп = гпах((?,,??г,.„ ...,(?, „ ,), он нашел простой путь перехода от последовательности Лей О, Яцс ц, ... к последовательности Леп Ям, ..., для которой требуется очень мало времени и места. В чем состояла его блестящая идея? Ь) Он решил модифицировать метод "максимум-1" так, чтобы 1-м наблюдением было шах((,'„...,(?з,.~ ~); другими словами, он взял 1; = Яп вместо 'г; = 71пр, как предлагается в разделе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
