AOP_Tom2 (1021737), страница 19
Текст из файла (страница 19)
Это доказывает эмпирически очевидный момент, что почти все линейные конгруэнтные последовательности имеют чрезвычайно низкую сериальную корреляцию по целому периоду. В упражнениях, приведенных ниже, показано, что другие априорные критерии, такие как критерий серий по целому периоду, могут быть выражены и в терминах небольшого обцбщения сумм Дедекинда. Из теоремы К следует, что линейная конгруэнтная последовательность будет удовлетворять этим критериям тогда и только тогда, когда определенные дроби (зависявцие от а и т, но нс от с) имеют малые частичные отношения. В частности, из результатов упр.
19 следует, что проверка по критерию серий для пар удовлетворительна тогда и только тогда, когда а/т имеет небольшие частичные отношения. В книге Суммы Дедекинда Ганса Радемахера и Эмиля Гросвальда (Наив Ва<ЗешасЬег апд Еш1! ОговввгаЫ, Май. Аввос. о( АвпеНса, Сагнэ Мопобгар1~ Хо. 16, 1972) обсуждается история и свойства сумм Дедекинда и их обобщений. Другие теоретические критерии, в том числе критерий серий для больших размерностей, рассматриваются в разделе 3.3.4. УПРАЖНЕНИЯ (часть Ц 1.
[М10) Выразите х шой у в териинах "пилообразной" и б-функций. 2. (М20) Докажите "реплективный закон", равенство (10), 2, (11М82) Найлом разложение а рнд Фурье (по синусам н косинусам) функция Цх)). ° 4. (М12) Если т = 10'о, то какое максимальное значение возможно для д (в обозначениях теоремы Р), если дано, что потенциал генератора равен 10? 5. (М21) Получите формулу (17).
6. (М27) Предположим, что ЛЛ' + ЛЛ' = 1. а) Покажите без использования леммы В, что а(Л,/с,с) = о(Л,/с,О) + 12 ~ (( †)) + б (( †)) о<в« для всех целых с > О. Л' ' Л' ' Ь) Покажите, что (( — )) + (( — „)) = 1 — 1 б (-„), если О < 1 < Л. с) Основываясь на предположениях леммы В, докажите равенство (21). ° 7. (М24) Докажите закон взаимности (19), когда с = О, используя обобщенный закон взаимности из упр.
1.2.4 — 45. 8. (МУ4) (Л. Карлиц (Ь. Саг!Вх).) Пусть р(р,е, г) = 12 ~ (( — )) (( — )). Обобщив метод доказательства, использованный в лемме В, докажите следующее прекрасное тождество Г. Рэдемахера (Н. Вэбетасбег). Если каждые из чисел Р, о, г взаимно просты одно относительно другого, то Р(Р,О,г) + Р(ч,г,р) +Р(г,Р,О) = — + — + — — 3. Р 6 Яг гр РО (Закон взаимности для сумм Дедекинда при с = О является частным случаем при т = 1.) 9.
[М40] Существует ли простое доказательство тождества Радемахера (упр. 8) с использованием в частном случае метода доказательства упр. 77 10. [М20] Покажите, что когда 0 < Л < Л, то можно легко выразить п(Л вЂ” Л, Л, с) и п(Л, Л, -с) в терминах п(Л, Л, с). 11. [МУО] Формулы, приведенные в разделе, показывают, как оценить о(Л, Л, с), когда Л и Л вЂ” взаимно простые числа и с — целое число. В общем случае докажите, что а) а(йЛ,ИЛ,4с) = о(Л, Л, с) для целых И ) 0; Ь) и(Л, Л, с+ 6) = п(Л, Л, с) + 6((Л'с/Л)) для целых с, действительных О < д < 1, Л .1 Л и ЛЛ' ш 1 (по модулю Л). 12. [М64] Покажите, что если Ь и Л вЂ” взаимно простые числа н с — целое число, то ]а(Л, Л, с)[ < (Л вЂ” 1)(Л вЂ” 2)/Л.
13. [М24] Обобщите равенство (26) так, чтобы получить выражение для а(Л, Л, с). ь 14. [Мйй] Линейный конгруэнтный генератор, для которого т = 2зэ, а = 2'э + 1, с = 1, был подвергнут сериальному корреляционному критерию для трех групп по 1 000 последовательных чисел. В результате этого была получена очень высокая корреляция, лежащая между 0.2 и 0.3 в каждом случае. Чему равна сернвльная корреляция данного генератора, взятая по всем 2 числам периодау 35 16.
[М21] Обобщите лемму В так, чтобы ее можно было применять к дебстевтельмым числам с, 0 < с < )с. 16. [Мзэ] Задана таблица Евклида, определенная в (32). Пусть.ро = 1, Р« = а~ и Р, = а,р,— ~ + рз-з для 1 < / < Л Покажите, что сложные части сумм в теореме П могут быть переписаны следующим образом, позволя1ощнм выполнять вычисления с нецелыми числами: (-1)'е' — 2 — = — ~ ( — 1)1+'61(сз+с„+~)рз т, т,+1 т1 1<~61 [Указание. Докажите тождество Я,<16„(-1)'+'/т т «.~ = (-1)'+'р„1/т1т +1 для 1 < с<1] 17.
[МОЯ] Напишите алгоритм вычисления п(Л, Л, с) для целых Л, Л, с, удовлетворяющих предположениям теоремы В. Он должен использовать только арифметику целых чисел (с неограниченной точностью), и ответ должен быть записан в виде А + В/Л, где А и В— целые числа (см. упр. 16.) По возможности используйте только конечное число переменных для временного запоминания вместо того, чтобы вводить такой массив, как ац ам..., аь ь 16. [Мбу] (У, Дитер (П. Вбеэег).) Даны положительные целые числа Л, Л, э. Пусть Я(Л,Л,с,э) = ~ (( )). Покажите, что сумма может быть вычислена в приближенной форме в терминах обоб- шенных сумм Дедекинда и пилообразной функции. [Указание. Когда э < Л, величина [у/Ь] — [(у — з)/Л) Равна 1 для 0 < у < э н равна О для э < у < Л, поэтому можно включить данный множитель и выполнить суммирование по О < у < Л.] ь 19. [МВВ) Покажите, что криглерий серий можно проанализировать по полному периоду в терминах обобщенных сумм Дедекиида, если найти формулу вероятности того, что а < Х„< В и а~ < Х з~ < В', когда а.
13, а', з3' — заданные целые числа, причем 0 < а < В < т и О < а' < В' < т. [Указание. Рассмотрите величину [(х — а)/т) — [(х В)/т) ) 20. [М29) (У. Дитер.) Обобщите теорему Р, чтобы получить формулу для вероятности того, что Х > Х„эз > Х,+з, в терминах обобщенных сумм Дедекинда. УПРАЖНЕНИЯ (часть 2) Во многих случаях точные вычисления с целыми числами достаточно трудно осуществить, но можно попытаться изучить возникающие вероятности, если усреднить по всем действительным величинам х вместо того, чтобы ограничить вычисление целыми числами. Хотя эти результаты будут только приближенными, они прольют немного света на проблему.
Удобно использовать числа П„лежащие между нулем и единицей. Для лимейной конгруэнтной последовательности Ц, = Х /т получим, что 1?„+з = (аП + В), где В = с/т и (х) определено как х шо41. Например, формула для сериальной корреляции примет внд с- (/ Ч *+Оь- (/'*зг) )/(/'*'ь-(/' у ) ). ь 21. [НМ23) (Р. Р. Ковэю (К. К, Согеуои).) Чему равно значемие С в только что приведенной формуле? ь 22. [М22) Пусть а — целое число и пусть О < В < 1.
Если х — действительное число, принимающее змачения между О и 1, и если з(х) = (ах + В), чему равна вероятностзч что з(х) < х? (Это аналог теоремы Р для "действительных чисел".) 23. (М2В[ В предыдущем упражнении дана вероятность того, что?/„+з < 1/,. Чему равна вероятность П ез < С з~ < сз„в предположении, что К, — случайное действительное число, лежащее между нулем и единицей? 24. (МВВ) Учитывая предположения из предыдущего упражнения и исключая случай для В = О, покажите, что сз„> СГ„.~.~ > > Сз„з,, происходит г вероятностью Чему равна средняя длина нисходящих серий, начиная с ?/„, где ?/„выбрано наудачу между нулем н единицей? ° 2б. [М25) Пусть а, В, а', /3' — действительные числа, О < а < В < 1, О < а' < В' < 1. Учитывая предположения из упр. 22, выясмите, чему равна вероятность того, что а < х < 13 и а' <.з(х) < В'? (Это аналог упр.
19 для "действительных чисел".) 26. (М21[ Рассмотрите гемератор Фибоначчи, где?/ею = (1/ + П ~). Предполагая, что С, и ?/з независимо наудачу выбраны между О и 1, найдите вероятность того, что з/з < Пз < ?/з, ?/~ < Пз < 1/з, Сз < 1/~ < (?з и т. д. (Указание. Разделите единичный квадрат ((х, у) [ О < х, у < 1) на шесть частей, зависящих от относительного порядка х, у и (х+ у), и определите площадь каждой части.) 2?. (М22[ В гевераторе Фибоначчи из предыдущего упражнения будем считать, что (/з и 1/~ независимо выбраны в единичном квадрате, однако исключается следующее неравенство: Уе > Сз. Определите вероятность, что Сз является началом возрастающей серии длиной?г, так что Пе > ?/з « Ц, > Пз+з.
Сравните с соответствующими вероятностями для случайной последовательности. 2В. [МЮЮ) В соответствии с формулой 3.2.1.3-(5) линейный кангруэнтный генератор с потенциалом 2 удовлетворяет условию Х„1 — 2Х„+ Х„+1 и (а — 1)с (по модулю т). Рассмотрим генератор, который обобщает предылущнй. Пусть Уя+1 = (о+ 2У~ — Уп — 1). Как в упр. 2б, разделите единичный квадрат на части, которые указывают относительный порядок Уц 0э и Уэ для каждой пары (1?ц 1?э), Существует лн какое-нибудь значение о, для которого все шесть возможных упорядочений имеют вероятность 1, если предположить, что У1 н Ур выбраны наудачу в единичном квадрате? 3.3.4. Спектральный критерий В этом разделе рассматривается особенно важный метод проверки качества линейных кангруэнтных генераторов случайных чисел. Все хорошие генераторы проходят проверку спектральным критерием; все генераторы, известные сейчас как плохие, фактически провалились при этой проверке.
Таким образом, спектральный критерий является наиболее мощным известным до сих пор критерием и заслуживает особого внимания. В процессе обсуждения будут выяснены те ограничения на степени случайности, которые не могут быть преодолены при использовании линейных конгруэнтных последовательностей и их обобщений. Спектральный критерий обладает свойствами как теоретических, так и эмпирических критериев, рассмотренных в предыдущих разделах. Он похож и на теоретические критерии, поскольку проверяет свойства последовательности на полном периоде, и на эмпирические критерии, поскольку для получения результата требует вычислений на компьютере.
А. Идеи, служащие обоснованием критерия. Наиболее важные испытания для проверки, насколько случайной будет последовательность, связаны со свойствами совместных распределений Г последовательных элементов последовательности, и спектральный критерий как раз и используется для проверки гипотез аб этих распределениях. Если задана последовательность (У„") с периодом т, то для построения критерия необходима проанализировать множество всех т точек в Г-мерном.пространстве. Для простоты предположим, что задана линейная конгруэнтная последовательность (Ха,о, с,гп) с максимальным периодом длиной т (так что с ~ 0) или что т — простое число и с = О, а период имеет длину т — 1.
В последнем случае прибавим точку (0,0,...,О) к множеству (1), чтобы всегда было ровно т точек. Эта дополнительная точка почти не влияет на общую ситуацию, когда т большое, и делает теорию более простой. При таком предположении (1) можно переписать следующим образом: ( — (х, в(х), в(в(х)),..., э[~ ~[(х)) ~ 0 < х < т), 1 а(х) = (ах + с) шаг) т где (3) представляет собой элемент, следующий за х. Здесь рассматривается лишь множества всех таких точек в Г-мерном пространстве, а не порядок, в катаром ани на самом деле генерируются.
На порядок генерирования отражен в зависимости между ) '"а д "и" 8п "а"'д д д дчг д ° д а а дд а дд д да да па а ап а ап да а падр падр пд а аддд д "арада дада дд а рю р да дада дада рд п дд а а да па д да а з(ю) а аа п па а дд ад а д д д п а р а а п П а а дд а ,д п ад а ад д рд да рд п аа а дп ад, д рд парю пд а р а д а п д а ра дада да а да аа да а дд аа а дд а ! аа ад драп адар и а а а а ша и дд пррр др ю(э(ю)) (а) Рис. 8. (а) Двумерная решетка, образованная всеми парами после- давательнмх точек (Х, Х„+~), где (Ь) Х„Ю вЂ” — (137Х + 187) шаб 256. (Ь) Трехмерная решетка трехмерных строк (Х,Х эпХ эю), компонентами векторов, и спектральный критерий изучает такую зависимость для различных размерностей 1 со всеми точками вида (2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
