AOP_Tom2 (1021737), страница 14
Текст из файла (страница 14)
Джордж Марсвлья в 1984 году ввел новый критерий. Поместим п шаров в и» урн, как и в критерии конфликтов, но под урнами подразумеваем дни года, а под шарами — дни рождения. Предположим, что (Уы..., 1'„) — это дни рождения, где 0 < У» < т. расположим их в порядке неубывания 1]ц « 1~„Н определим п "промежутков" о» = У]з~ — 1'Вц , з -» = 1'< 1 — У]„-Н, 5„= 1'~П + т — 1<„~ и, наконец, расположим промежутки в таком порядке; 5~11 < < 51„9 Пусть  — число равных промежутков, а именно — число индексов у, таких, что 1 < у < п и 511) = 51 »р Когда и» = 223 и и = 512, должно получиться следующее.
В= 0 1 2 3 или больше С вероятностью .368801577 .369035243 .183471182 .078691997 (Среднее число равных промежутков для выбранных т и и должно быть равным приблизительно 1.) Примените этот критерий, скажем, 1 000 раз и воспользуйтесь Х2-критерием с тремя степенями свободы, чтобы сравнить эмпирические значения В, с правильным распределением. Так можно выяснить, будет ли генератор вырабатывать приемлемые случайные промежутки между днями рождений. В упр. 28-30 развивается теория, связанная с этим критерием, и приводятся формулы для других значений т и и. Такой критерий, как критерий промежутков между днями рождений, в первую очередь, важен в связи с тем замечательным фактом, что генератор Фибоначчи с запаздыванием пе удоелетворлет этому критерию, хотя он вполне удовлетворяет другим традиционным критериям. )Драматические примеры таких неудач приведены Марсвлья, Земаном и Тсангом (Магваб!»а, Еашап, апд Тэапк, 82ас, апд РгоЬ.
7 ессегэ 8 (1990), 35 — 39).] Рассмотрим, например, последовательность Хп 1Х« — 24 + Хп-33) пки1 п1 из 3.2.2 — (7). Числа этой последовательности удовлетворяют соотношению Хп + Хп 34 = Хп-24 + Хп 31 (ПО МОдуЛК1 »л), так как обе стороны конгрузнтны Лп 24 + Лп 33 + Лп ы. Поэтому две пары разностей равны Хп Хп-24 = ~п — 31 Хп-36 Хп Хп-31 = Хп-24 '1« — 36. Всякий раз, когда Лп приемлемо близко к Хп ы илн Хп 31 (как должно было бы произойти в настоящей случайной последовательности), одна и та же разность имеет хороший шанс появиться в двух промежутках.
Получится значительно больше случаев равенств (обычно со средним В 2, а не 1). Но если исключить из В любой равный промежуток, возникающий из условий конгруэнтности, то полученная статистика В' будет удовлетворять критерию дней рождений, (Один из способов избежать неудачи состоит в том, чтобы отбрасывать определенные элементы последовательности, используя, например, только Ле, Х2, Х»,...
как случайные числа. Тогда мы никОгда не пОлУчим вСЕ четыРе элемента множеСтва (Хп, Л«-24, Хп-31 Х вЂ” ва) н в критерии промежутков между днями рождений исчезнут проблемы. Существует даже лучший способ избавиться от проблем — отбросить последовательные группы чисел, как предложил Люшер (ЕцэсЬег); см. раздел 3.2.2. Подобные замечания можно использовать для генераторов вычитания с заимствованием и суммирования с переносом из упр.
3.2.1.1 — 14.) К. Критерий сериальной корреляции. Можно подсчитать следующую статистику: п(и„и,+и,и,+."+П„,П„,+и„,и,)-(и„+П,+" +и„,)' п(Пеэ + Пзэ + . + Пэ,) — (По + П1 + . + Пл-1)т Это коэффициенты сериальной корреляции, мера зависимости У ~1 от У . Коэффициенты корреляции часто появляются в статистических работах. Если з дано и величин Уе, Ум ..., У„~ и и других величин $а, Ъы ..., Ъ'„ы то коэффициент корреляции между ними определяется следующим образом: ' Е(П 1') — (Е П ) (Е Р' ) (24) Все суммирования в этой формуле производятся по области О < ~' < и: формула (23) — зто частный случай последней формулы для 1'. = П1 ьц э,. Знаменатель в (24) равен О, когда Уе — — У1 = . = У„1 или $е — — Ъ1 — — — — $'„ы поэтому мы исключаем из рассмотрения такой случай. Коэффициент корреляции всегда лежит между — 1 и +1. Когда он равен О или очень мал, значит, величины У, и 1; независимы одна от другой (говоря более точно, между ними нет линейной зависимости.
— Прим, ред.); если же значение коэффициента корреляции равно ~1, это означает полную линейную зависимость, Действительно, в таком случае г'. = и х 6У для всех у и некоторых констант о и р' (см. упр. 17). Следовательно, С в (23) должно быть как можно ближе к О. На самом деле, поскольку УеП1 не является полностью независимым от У1Ую нельзя ожидать, что серивльный коэффициент корреляции будет точно равен О (см. упр. 18). "Хорошим" значением С будет значение, находящееся между 11„— 2п„и р„+ 2а„, где — 1 э и р„=, п~ =, п>2. (25) и — 1' " (и — 1)э(п — 2)' Ожидается, что С находится между этими значениями в 95% случаев.
Формула для и~ в (25) — это верхняя граница сериальных корреляций между произвольно распределенными независимыми переменными. Когда У; равномерно распределены, то истинная дисперсия равна фп ~ + 0(п ~~~!ойп) (см. упр. 20). Вместо обычного коэффициента корреляции между наблюдениями Щ, Ум ..,, Г„1) и их соседями (Уы...,У„~,5ге) можно вычислить коэффициент корреляции между (Уо, Пм..., К, 1) и любой циклически смещенной последовательностью (( ю 1 ь н — м УО~ ° ° ~ Пд-!).
Пиклическая корреляция должна быть небольшой для О < д < и. Непосредственное вычисление по формуле (24) для всех о потребует около и операций умножения, однако на самом деле можно подсчитать все корреляции всего за 0(п1охп) шагов, если использовать быстрое преобразование Фурье. (См. раздел 4.6.4, а также работу Е. Р. 8с1ппЫ, САСМ 8 (1965), 115.) Е. Критерий подпоследовательиостей. Внешние программы часто вызывают случайные числа пакетами. Например, если программа работает со случайными переменными Х, У и У, она может потребовать одновременного генерирования трех случайных чисел. В таких ситуациях важно, чтобы подпоследовательность, образующая каждук> шройку членов первоначальной последовательности, была случайной.
Если программа требует сразу д чисел, то последовательность Сш С', и „,...,. может быть проверена с помощью описанных выше критериев для первоначальной последовательности С'ш !!,, !7г,.... Опыты с линейными конгруэнтными последовательностями показали, что поведение этих порожденных последовательностей редко бывает менее случайным, чем поведение первоначальной последовательности, если только 9 не имеет большого множителя., общего с длиной периода.
Яа бинарном компьютере с т, равным длине компьютерного слова, например, критерий подпоследовательностей для д = 8 даст результаты, худшие среди всех 9 < 16, а на десятичном компьютере значение 4 = 10 приведет к получению наиболее неудовлетворительных подпогледовательностей. (Это можно объяснить, в некоторой степени основываясь на потенциале, так как подобные значения 9 имеют тенденцию к уменьшению потенциала. В упр. 3.2.1.2-20 приведено более подробное объяснение.) М. Исторические замечания и дальнейшее обсуждение.
Статистические критерии, естественно, возникли в связи с потребностью доказать или опровергнуть гипотезы относительно различных наблюдений. Хорошо известны две ранние работы, посвященные проверке случайности искусственно генерируемых чисел. Это две статьи М. Дж. Кендалла и Б. Бабингтон-Смита (М. О. Кепс!а1! апб В. Ваййпйгопяш!1Ь, уопгпа! ор Гйе йоуа! $га!ибса! атос!есу 101 (1938), 147-166; также в этом журнале см.
6 (1939), 51-61). В приведенных работах внимание было сосредоточено в большей степени на проверке случайности цифр между 0 и 9, чем на случайности реальных чисел; с этой целью авторы обсуждали критерий частот, критерий серий, критерий интервалов и покер-критерий, однако они неудйчно применяли критерий ссрий.
Кендалл и Бабиигтон-Смит использовали также вариант критерия собирания купонов. Метод, описанный в этом разделе, был введен Р. Е. Гринвудом (В. Е. Отвеиной, МагЬ. Сошр. 9 (1955), 1 — 5.) Критерий монотонности имеет довольно интересную историю. Первоначально он рассматривался для восходящих и нисходящих серий одновременно. Восходящие серии следовали за нисходящими, затем — восходящие серии и т.
д. Заметим, что критерий монотонности и критерий перестановок зависят не от того, имеет ли У„ равномерное распределение, а от того факта, что У; = У появляется с вероятностью О, когда ! ф !1 Поэтому данные критерии могут применяться ко многим типам случайных последовательностей. Критерий монотонности в примитивной форме введен И. Ж. Бьензйме (1. В!епауп1е, Сошрсез Веидиз Асад. Яс!.
Раг!з 81 (1875), 417 — 423). Примерно через шестьдесят лет В. О. Кермак и А. Г. Мак-Кендрик опубликовали две обширные статьи на эту тему (%'. О. Кегшас1с апов А. О. МсКепс!пс1с, Ргос. Виуа! Яос!осу ЕйпЬиг8Ь 57 (1937), 228 240, 332 — 376). В качестве примера они установили, что количество выпавших в Эдинбурге осадков межлу 1785 и 1930 годами носило "всецело случайный характер" по отношению к критерию монотонности (хотя они проверяли только среднее и стандартное отклонения длин серий). Другие исследователи также начали использовать этот критерий, но только в 1944 году было показано, что использовать !Сз-метод в этом критерии неправомочно.
В работе Х. Левена и Я. Вольфовица (Н. Еетепе апг) 3. Жо1Ьжйх, Аппа1з МаГЬ. 81аа 15 (1944), 58 — 69) введен правильный критерий монотонности (для чередующихся восходящих и нисходящих серий). В ней же обсуждались ошибки при использовании этого критерия ранее. Отдельные критерии для восходящих и нисходящих серий, прелложенные выше в настоящем разделе, больше подходят для использоиания на компьютере, поэтому мы не приводим сложные формулы для чередования восходящих и нисходящих серий. (См. обзорную работу Д. Э.
Бартона и К. Л. Маллоу (В. Е. Ваг1оп ахи! С. 1. Ма1!ожэ, Аппа1з Ма1Ь. Ягаа 36 (1965), 236-260].) Среди всех рассмотренных выше критериев критерий частот и критерий серивльной корреляции кажутся более слабыми в том смысле, что почти все генераторы случайных чисел им удовлетворяют. Теоретические обоснования такого явления кратко обсуждаются в разделе 3.5 (см. унр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
