Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 25
Текст из файла (страница 25)
Пе!6аэ СЬгмс!апэеп) (1пэс. МагЬ. агап апб Орет. Вяэ., ТесЬ, Нп!т. ВепшагЬ (ОсгоЬег, 1975); не опубликовано), этот критерий получил распространение с появлением компьютеров; он предназначен для использования на компьютере и не подходит для вычислений вручную. Читатель, вероятно, удивлен: "Зачем применять такое количество критериев?". Может показаться, что на проверку случайных чисел затрачивается больше компьютерного времени, чем на нх использование! Это неверий, хотя можно переусердствовать в проверке.
Необходимость проверки последовательности с помощью нескольких критериев неоднократно отмечалась в литературе. Исследователи проверили, например, что некоторые генераторы чисел наподобие метода средин квадратов удовлетворяли критерию частот, критерию интервалов и покер-критерию, однако не удовлетворяли критерию серий. Линейные конгруэнтные последовательности с малым множителем, как известно, были проверены многими критериями, однако не выдержали проверку критерием монотонности, так как у них слишком мало серий единичной длины. Критерий "максимум-г" можно также использовать для поиска плохих генераторов, которые без проверки этим критерием кажутся вполне респектабельными. Генератор "вычитания с заимствованием" не проходит проверку критерием интервалов, когда максимальная длина интервала превышает самое большое запаздывание: см.
работу Ваттулайнена, Канкаала, Сааринена и Ала-Ниссила ((гесса)ашеп, Капйаа(а, Яаэг!пеп, апд А!а-%ээ!(а, Сошригег РЬуэкз Сотшишсабоаэ 86 (1995), 209-226), в которой идет речь о многих других критериях. Генератор Фибоначчи с запаздыванием, для которого теоретически гарантировано, что он имеет равно- распределенные младшие значащие разряды, тем не менее не удовлетворяет простым вариантам одноразрядного критерия равномерности (см.
упр. 31 и 35, а также 3.6 — 14). Возможно, основной смысл экстенсивной проверки генераторов случайных чисел состоит в том, что людям, неправильно применяющим генератор случайных чисел господина Х, будет тяжело допустить, что на самом деле неправильна их собственная программа. Они будут обвинять генератор до тех пор, пока господин Х не докажелз им, что его числа достаточно случайны. С другой стороны, если источник случайных чисел предназначен только для личного использования господином Х, последний может не беспокоиться о его проверке, так как с большой вероятностью технических рекомендаций, приведенных в настоящей главе, достаточно для проверки этого датчика.
Чем больше используются компьютеры, тем больше необходимо случайных чисел, и генераторы случайных чисел, которые раньше считались вполне удовлетворительными, теперь недостаточно хороши для применения в физике, комбинаторике, стохастической геометрии и т. д. Джордж Марсалья в связи с этим ввел строгие критерии, которые превосходят классические методы, подобные критерию интервалов н покер-критерию, в том смысле. что они ло сравнению с этими критериями замечают другие отклонения. Например, он нашел, что последовательность Х„+з = (62605Х„+113218009) гпод 2зэ имеет значительное отклонение в следующем эксперименте. Выло получено 2з' случайных чисел Х„и выделено 10 их старших двоичных разрядов У„= (Х„/2'э).
Подсчитано, сколько из 2ю возможных лар (р,у) 10-разрядных чисел не появятся среди (УПУз), (Уз, Уз): ", (Узм-м Узз~) Должно быть примерно 141909.33 отсутствующих лар со стандартным отклонением щ 290.46 (см. упр. 34). Но в шести последовательных испытаниях, начиная с Хз = 1234567, выполнили расчеты и получили значение стандартного отклонения между 1.5 и 3.5, которое получилось слишком низким.
Распределение оказалось слишком "плоским" для того, чтобы быть случайным, поскольку, вероятно, нз 2зз чисел значимыми дробями являются только 1/256 на весь период. Подобный генератор с множителем 69069 и модулем 2зе, как показано, яваяется лучшим. Марсалья и Земан (Еалщл) назвали эту процедуру "обезьяний критерий", так как она позволяет подсчитать количество двухсимвольных комбинаций, которые обезьяна пропустит после печатанья на клавиатуре с 1024 клавишами (см.
Сошрпзегв апд Май. 26,9 (НотешЬег, 1993), 1-10, где приведен анализ нескольких "обезьяньих критериев"). УПРАЖНЕНИЯ 1. (10) Почему критерий серий, приведенный в п. В, следует применять к (УщУ~), (Уз, Уз), ..., (Уз -з, Ут -~) вместо пар (Ущ 11), (Уп Уз), ..., (У -му,)1 2. (10] Представьте приблизительный путь обобщения критерия серий для троек, четверок и т. д, вместо пвр. 3. (М00) Сколько йз нужно проверить в критерии интервалов (алгоритм С), прежде чем будет найдено в среднем л интервалов, если предположить, что последовательность случайна? Чему равно стандартное отклонение этой величины? 4. (М10) Докажите, что вероятности а (4) верны и для критерия интервалов. б.
(Мву) "Классический" критерий интервалов Кендалла и Бвбингтон-Смита рассматривает числа 11о, У|,..., 11я-~ как циклическую пеледовательность с Пя+м совпадающую с С'~, Здесь 1т' — фиксированное число 11, определяемое критерием.
Если л — это число оо, ..., 11я и попадающих в интервал а < 11, < д„то существует л интервалов в циклической последовательности. Пусть 3, — число интервалов длиной г для О < г < 1 и пусть Я» — число интеРвалов длиной > К Покажите, что величина К = 2 о<с ы(У, — пР,)»щъ должна иметь предельное х~-распределение с г степеиями свободы, когда Д» стремится к бесконечности, а р, заданы в (4). 6. [40) (Х. Гейрингер (Н. СекЯпбег).) Подсчитав частоты первых 2 000 десятичных чисел в представлении е = 2.71828..., ыы получили»с~-значение 1.06, указывающее, что действительные частоты цифр О, 1, ..., 9 намного ближе к их о»кидаемым значениям, чем при случайном распределении. (На самом деле дт > 1.15 с вероятностью 99.99ь) Этот же критерий, примененный к первым 10000 цифр е, дает приемлемое значение Х~ = 8.61; ио тот факт, что первые 2 000 цифр так равномерно распределены, достоин удивления.
Будет ли происходить то же самое, если записать е в системе счисления с другим основанием? [См. АММ 72 (1965), 483-500.] 7. [08) Примените процедуру критерия собираиия кулонов (алгоритм С) с»1 = 3 и и = 7 к последовательности 1101221022120202001212201010201121. Чему равны длины семи послеловательиостей? 8. [МЯЯ) Сколько в среднем (7» нужно проверить в критерии собирания купонов, прежде чем с помошью алгоритма С будет найдено и полных множеств при предположении, что последовательность случайна? Чему равно стандартное отклонение7 [Указание. См. формулу 1.2.9 — (28).] 9.
[МЯЯ] Обобшите критерий собирания купонов, чтобы поиск прекрашался, как только будет найдено в» различных зиачений, где ы — фиксированное положительное целое число, меньшее или равное»(. Какие вероятности следует использовать вместо (6)? 10. [МЯЯ] Выполните упр. 8 для более общего критерия собирания купонов, описанного в упр. 9. 11.
[ОО] Восходящие серии в коикретиой перестановке показаны в (9). Каковы нисходящие серии в этой перестановке? 12. [ЯО] Пусть Уо, (7», ..., У„» — и различных чисел. Напишите алгоритм, определяюший длины всех восходящих серий в втой последовательности. Когда ваш алгоритм заверюит 1»аботу, 00087[с] должен быть равен числу серий длиной г для 1 < г < 5, а СООИТ[6] — числу серий длиной 6 или больше.
13. [МЯЯ] Покажите, что (16) — это число перестановок из р+9+ 1 различных элементов, имеющих структуру (15), ь 14. [МЛ] Если '"выброситьи элемент, который слечует непосредственно за серией, то, когда Х» болыпе Х»+», качнем следующую серию с Х;+т.
Длины серий независимы, и можно использовать обычный хэ-критерий (вместо ужасно сложного метода, описанного в разделе). Чему приближение рэвиы вероятности для длин серий этого простого критерия монртоииости? 15. [М10] Почему в критерии "максимум-1" предполагается, что величины 1е, Ъ;, ..., Ъ"„' » равномерно распределены между нулем и единицей? ь 16.
[И] Господип Дж. Г. Квик ("Студент") хотел использовать критерий "максимумы" для нескольких различных зпачеиий О а) Похожив Я»» = шах(У», (7»+»,..., (»»чм» ), ои кинел простой путь перехода от последовательности Яо», »Ь Я»»» ц, ... к последовательности Яе», Ям, ..., для которой требуется очень мало времени и места. В чем состояла его блестящая идея? Ь) Ои решил модифицировать метод "максимумй" так, чтобы»чи иаблюделием было шах(17»,..., П»+»- »); другими словами, он взял г» ж Я», вместо 1»» = 81»»Зи как предлагается в разделе. Квнк считал, что есе Я; должны иметь одно и то же распределение, поэтому критерий будет даже сильиее, если использовать кюкдое Я»», 0 < у < и, вместо кюкдого 1-го члена. Но когда он применил Х~-критерий в случае пцинаковых распределений к величинам Уу», получилнсь чрезмерно высокие значения статистики У, которые увеличивались при возрастании к Почему так произошло? 17.
[Мйб] Даны любые числа 17о,..., (/„и Уе,..., У ь Пусть их средние значения равны й=- ~~,' (7», 1 еб»<е 1 9 = — ~~~ У», и еб»сь «) Пусть Ц = (7» - й, Уь' = У» — 9. Покажите, что козффицяент корреляции С, определенный в (24), равен ~ ич/Д ч Д ч Ь) Пусть С = Ф/»1, где Ф и П вЂ” числитель и знаменатель выражения нз п. (а).
Покажите, что АЛ <»1~, отсюда -1 < С < 1. Получите формулы для разности 77~ — Х~. [Указание. См. упр. 1.2.3-30.] с) Если С = ш1, покажите, что а(7»+ )?У» = т, 0 < я < и, для некоторых не всех равных нулю постоянных о, В и т. 1В, [М39] (а) Покажите, что, если я = 2, сернальный коэффициент корреляции (23) всегда равен -1 (если знаменатель не равен нулю). (Ь) Аналогично покажите, что, когда и ы 3, сериавьный коэффициент кор1мляция всегда равен --', (с) Покажите, что знаменатель в (23) равен нулю тогда н только тогда, когда (7» = П» = -- С„ 19. [Мйд] (Дж.
П. Батлер (3. Р. Вп»!ег).) Пусть (7д, ..., (7„» — независимые одинаково распределенные случайные величины. Докаясите, что ожидаемое значение сериального к~мффющента корреляции (23), среднее по всем случаям с ненулевым знаменателем, равно -1/(и — 1). 30. [НМ41] Продолжая предыдущее упражнение, докажите, что дисперсия (23) равна п~/(н — 1)з(п — 2) — из Е(((/е — (/»)~/11~)/2(н — 2), где 17 — знаменатель из (23), а Е— ожидаемое значение по всем случаям, когда Ю 7» О.
Чему равно асимптотическое значение Е(((/о — (7») /11 ), когда каждое Ц равномерно распределено? 31. [19] Какие значения / будут вычислены алгоритмом Р, если применить его к перестановкам (1,2,9,8,5,3,6,7,0,4)? 33. [18] Длк какой перестановки (0,1,2,3,4,$,6,7,3,9) алгоритм Р выдаст значение / = 1024? 1 »-» Р(хм...,я») = — ~ , '[(Уь,....У«+с-з) = (хп...,х»)]; Л в=о 1 »-1»'-» ()(хм...,х») = — ~ ~~ ~[(Я,...,Я +»-») =(зм °,х»)] ье -» Тогда ~ (Щхм...,х») — И ') < ~ (Р(я»,...,я») — И ') . Ыь...лю) (*о- ю) 23. [МЯ3] Пусть (У„) и (У') — последовательности целых чисел„имеющие периоды длиной Л н Л' соответственно с 0 < У„, У„< И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
