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