AOP_Tom2 (1021737), страница 17
Текст из файла (страница 17)
*3.3.3. Теоретические критерии Несмотря на то что каждый генератор случайных чисел можно проверить с помощью критериев, приведенных в предыдущем разделе, всегда лучше иметь априорнмп критерий, а именно — теоретический результат, с помощью которого можно заранее сказать, насколько хороши будут проверки генератора.
Такие теоретические результаты помогают понять методы генерирования намного лучше, чем эмпирические методы проб и ошибок. В этом разделе мы подробнее изучим линейные конгруэнтные последовательности. Если можно предугадать результаты определенных проверок заранее, прежде чем генерировать случайные числа, то имеется больше возможностей должным образом выбрать а, га н с. Развитие теории такого типа весьма сложно, хотя достигнут определенный прогресс.
Получены пока далекие от общих результаты для статистических критериев, которые можно применять к полным цериадам. Тем не менее статистические критерии приобретают смысл, когда они применяются ко всему периоду; например, критерий равномерности будет давать отличные результаты и без этого требования, но критерий серий, критерий интервалов, критерий перестановок, максимум- критерий и другие можно плодотворно проанализировать на всем периоде. Такие исследования будут определять глобальную "неслучайность" последовательности, т.
е. неправильное поведение очень больших выборок. Теория, которая будет здесь рассматриваться, вполне всеобъемлюща, однако она не исключает необходимости проверять локальные "неслучайности" методами, приведенными в разделе 3.3.2. Действительно, любая проверка с использованием только коротких последовательностей очень сложна,,Известно лишь несколько теоретических результатов, касающихся поведения линейной конгрузнтной последовательности на промежутке, меньшем, чем целый период (онн обсуждаются в конце раздела 3.3.4; см. также упр. 18).
Начнем с доказательства простого априорного закона для наименее сложного случая — для критерия перестановок. Суть нашей первой теоремы состоит в том, что для последовательности с большим потенциалом примерно в половине случаев выполняется неравенство Х„+1 < Х„. Теорема Р. Пусть а, с и т образуют линейную конгруэнтную последовательность с максимальным периодом, Пусть 6 = а — 1 и а — наибольший общий делитель т и 6.
Вероятность того, что Х„.ь~ < Х„, равна -' + г, где г = (2(спкм1 г() — И)/2т; следовательно, ~г! < й/2т. Доказательство. Для доказательства этой теоремы используются методы, интересные сами по себе. Сначала определим (2) г(х) = (ах+ с) шос1т. Таким образом, Х„~1 —— г(Х„) и теорема сводится к подсчету количества целых х, таких, что О < х < т, а г(х) < х, поскольку такое число встречается где-то в периоде. Необходимо показать, что это число равно 1~(т+ 2(сщос1И) — д).
(3) Функция ] (х — э(х))/гп] равна 1, когда х > э(х), и 0 — в противном случае. Следовательно, искомое число, которое мы хотим подсчитать, можно записать следующим образом: (4) (Вспомним, что ] -р] = — '19] и 6 = а — 1.) Такие суммы можно подсчитать, используя методы из упр. 1.2А-37, в котором было доказано, что для любых целых Ь и /с, й > 0 (кои — наибольший общий делитель). Так как а и гп — взаимно простые числа, эта формула дает ] ах+ с ] (а — 1)(гп — 1) Е ~ +с, гп ! 2 о«* э-ц( -с а-1 + + с — (с шод и) гп 2 2 0<а<и и (3) следует немедленно.
$ Доказательство теоремы Р указывает, что априорные критерии можно исследовать, если уметь удовлетворительно обращаться с суммами, содержащими функции ( ] и ( ], Во многих случаях наиболее мощной техникой оперирования функциями "пол" и "потолок" является ик замена двумя отчасти более симметричными операциямн: Ю(х) = (х] + 1 — (х] =, (х-целое число]; (б) ((х)) = х — (х/ — 1+ 1Ю(х) = х — ]х] + э — фб(х) = х — —,((.] + Гх]) ( ) (8) (9) (( — х)) = — ((х)); ((х+и)) = ((х)) для целого и; ((пх)) = ((х))+ (~х+ — )) +. + ((х+ — )) для целого и > 1 Последняя функция — это "пилообразная" функция, встречающаяся в теории рядов Фурье. На рис.
7 приведен ее график. Причина того, что мы предпочитаем работать с функцией ((х)), а не с 1х] илн ] х], состоит в том, что ((х)) обладает несколькими очень полезными свойствами: 1 +- э Рис. 7. Пилообразная функция ((х)). (см. упр. 2). Для приобретения практических навыков работы с этими функциями докажем теорему Р снова, на этот раз, не используя упр. 1.2.4-37. С немотные равенств (7) — (9) можно показать, что х — а(х) х — а(х) х — е(х) 1 1 х — э(х) х — в(х) х — (ах + с) 1 х — в(х) Ьх+ с 1 так как (х — а(х))/т никогда не будет целым числом.
Легко видеть, что х — в(х) пт с«*< поскольку и х, и в(х) принимают значение из (0,1,...,тп — 1) точно один раз. Следовательно,(11) влечет (12) Пусть Ь = Ьст(, тп = птес1, где Ье и пте — взаимно простые числа. Нам известно, что (Ьсх) пих$ тпе принимает значения (О, 1,..., те — 1) в некотором порядке, когда х изменяется от 0 до ьче — 1. Из (9), (10) и равенства Ь(х + гас) + с Ьх + с получим (13) Теорема Р немедленно следует из (12) и (13). Одно из следствий теоремы Р таково: практически прн любом выборе а н с можно получить приемлемые вероятности того, что Х„.тт с Х„, по крайней мере при полном периоде, за исключением больших Н. Большие значения д соответствуют низкому потенциалу. (Уже известно, что генераторы с низким потенциалом нежелательны).
Следующая теорема дает более точные условии выбора а и с. Рассмотрим критерий сериальной корреллции, применяемый на полном периоде. Величина С, определенная в разделе 3.3.2 (формула (23)), равна с = ( л ь) †( т *) ) / ( т . †( ь *) ). (1< Пусть х' — такой элемент, что в(х') = О.
Тогда в(х) = т(( )) + ™[х ф х'[. (15) Формулы, которые необходимо получить, лучше всего выразить с помощью суммы о(Ь,Й,с) = 12 ~~~ ((-)) (( )), о<1<а (16) важной функции, возникающей в некоторых математических задачах. Ее называют обобщенной суммой Дедекинда, так как Ричард Дедекинд (Пес1еЫпо) ввел функцию о(Ь, Ь, О) в 1876 году, когда комментировал неоконченную рукопись Римана. [См. работу В. Ббешапп, Сачашп1ейе шасИ.
Юегйе, 2пс1 еф (!892), 466-478.[ Используя достаточно известные формулы 2 ( 2)( 2 3 к т(п1 — 1) х= 2 0«к<пав 0«к< к можно легко преобразовать (14) в С— то(а, т, с) — 3+ 6(т — х' — с) ('7) тз — 1 (см. упр. 5). Так как гп обычно очень большое, можно отбросить члены порядка 1/гп и получить приближенную 4юрмулу (18) С вЂ” о(а, т, с) (т с погрешностью по абсолютной величине, меньшей, чем 6/т. Критерий серивльной корреляции сейчас сводится к определению значения суммы Дедскинда о(а, т, с). Вычислять о(а, т, с) непосредственно из определения (16) не легче непосредственного вычисления коэффициента корреляции, но, к счастью, существуют простые методы быстрого подсчета сумм Дедекинда.
о(Ь,Ь,с) + о(Ь, Ь,с) = — + — + — + — — 6[ — [ — Зе(Ь, с), Ь ЬЬ ЬЬ '(Ь[ (19) где е(Ь, с) = [с = О[ + [с 1пос1 Ь ф О[. (20) Лемма В (кЗакон взаимностик длл сумм Дедекинда). Пусть Ь, й н с — целые числа. Если О < с < Ь, О < Ь < Ь и если Ь и Ь - — взаимно простые числа, то Доказашельсгпво. Оставляем читателю доказательство того, что при наших предположениях имеет место равенство Если ы — комплексный А-й корень из единицы еэ '~", то из формул 1.2,9-(13) получим 1 — ы у"д(ьг'х) = гх", если О < г < /с. /с (23) о<э<а Положим х = 1, тогда д(ызх) = к/(м' — 1), если у ф О, иначе это выражение равно Л(й — 1)/2.
Поэтому — 1г гшобк = ,'~, + -'(й — 1), если г целое. и~ — 1 о<т<ь (Равенство (23) показывает, что правая часть равна г, когда О < г < к, и она не изменяется при прибавлении к г числа, кратного к.) Следовательно, (( ))= — ~ . — — + — 3( ). а<~<ь Эта важная формула, которая справедлива для всех целых г, позволяет свести многие вычисления, включающие ((г/к)), к суммам, содержащим Й-й корень единицы. Она предоставляет новые возможности для вычислений. В частности, получим следующую формулу, когда Й 1 Ри о<г<ь о«ь в<1<э (24) Правая ее часть может быть упрощена, если просуммировать ее по г.
Получим 2.'е«„ь ы"' — — /(и') = О, если э шо4 и ф. О. Равенство (25) сведется к бст ~ с! а(п,к, с) + а(к, й,с) = а(п, 1с, О) + а(ь, и, О) + — ' — 6(- ) — 3е(й,с) + 3 (21) (см. упр. 6). Теперь докажем лемму только для с = О. Приведенное ниже доказательство, в котором используются комплексные корни из единицы, по существу, принадлежит Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
