AOP_Tom2 (1021737), страница 18
Текст из файла (страница 18)
Карлицу (Е. Саг! Кх). Это действительно более простое доказательство, чем доказательство с использованием элементарных преобразований сумм (см. упр. 7), но для следующего метода необходимо больше математических понятий, чем требуется обычно для задач такого типа, поэтому он более поучителен. Пусть /(х) и д(х) —. полиномы, определенные следующим образом: /(х) = 1+х+. +х' = (х — 1)/(х — 1), д(х) = х + 2хэ + . + (/с — 1)хь (22) = х/ (х) = йх /(х — 1) — х(х — 1)/(х — 1) .
3(к — 1) 12 э 1 й и ~ (ы эь — 1)(ьд' — 1) с<э<а (26) Аналогичная формула получена для п(Ь, Ь, О) с ~ = ез"'уь вместо ы. Не ясно, что делать с суммой (26), однако существует элегантный метод ее пре- образования, основанный на том факте, что каждый член суммы является функцией от ы1, где 0 < у < Ь. Следовательно, суммы, в сущности, берутся по lс-м корням из единицы, отличным от 1.
Когда хы хю ..., х„— различные комплексные числа, получаем равенство Е, 1 ,, (х — х~)... (х — х ~)(х — ху)(х — х +~)... (х — х„) (ЬЬО) ( ) (ЬхО) 6(Ь Ь ЬЬ) 2 1 1 2Ь 2Ь' эквивалентное желаемому результату. $ Лемма В дает явно заданную функцию ДЬ, Й, с), такую, что а(Ь, Ь,с) = 7'(Ь, Ь,с) — и(Ь,Ь,с), (ЗО) какими бы ни были взаимно простые числа Ь и Ь, такие, что 0 < Ь < Ь, О < с < Ь, Из определения (16) следует, что и(Ь,Ь,с) = и(йгпод Ь, Ь, сгпск1Ь). (31) (27) (х — х~)... (х — х„) которое можно вывести в результате применения обычного метода разложения на элементарные дроби в правой части этого равенства.
Кроме того, если д(х) (х — у~)(х — Рз)... (х — у ), справедливо Ч (Уу) = (Уу У1) ° (Уу У~-1НУу Уэ+г) ° (Уз У~п)~ (28) это тождество часто используется для упрощения выражений, подобных левой части (27). Когда Ь и Ь вЂ” взаимно простые, все числа ы, ыз, ..., ыь " различны. Поэтому можно рассмотреть формулу (27) в частном случае для полннома (х-ы)... (х — ыь ')(х — ~)... (х — ~" ') = (х" — 1)(х" — 1)/(х — 1)т, получив следующее тождество для х: 1 ~т(('У-1)т 1 ыт(шу — 1)з (х-1)т Ь /-; Куь — 1)(х — ~1) я Г (ыуь — 1)(х — ыз) (хл — 1)(хь — 1) Оно имеет много интересных следствий и позволяет получить многочисленные формулы для сумм наподобие (26).
Например, если (29) дважды продифференцировать по х и устремить х -~ 1, получится 2 ~1(~~ — 1)з 2 ыз(ыз — 1)~ Е (~ус Ц(1 ~~)з + ь Е ( уь 1)(1 ь,,)з 1~Ь й 1) 1 1 1 6~Ь Ь ЬЬ/ 2 2Ь 2Ь Заменим 1' на Ь вЂ” 1 н на Ь вЂ” у в этой сумме и используем (26), чтобы получить равенство Поэтому можно повторно испольэовать (30) для оценки а(Ь, Ь, с) путем уменьшения параметров, как в алгоритме Евклида. Дальнейшие упрощения произойдут, когда мы более подробно исследуем эту итеративную процедуру. Положим, что тп1 — — Ь, тг = Ь, с, = с, и построим следующую таблицу. (32) Здесь 51 (су/ту+1 3 с+1 — — с шот1т,+1. а, = (ту/т;+1), Ш,4.2 = т шо44 т +1, (33) Отсюда следует, что 0<ту+1<ту, 0<с <т.
(34) Для удобства предположим, что алгоритм Евклида закончится в (32) после четырех итераций. Это предположение будет иметь структуру, подобную той, которая наблюдается в общем случае. Так как Ь и Ь вЂ” взаимно простые числа, для начала в (32) следует положить тб = 1 и сб — — О. Допустим также, что сз ~ О, но сб — — 0 для того, чтобы получить эффект от применения рекуррентной процедуры. Равенства (30) и (31) дают а(Ь,Ь,с) = и(тг,тпз,с,) = /(тг~тйз~с1) а(тз~тг~сг) — У(тг,тп1,с1) У(тз,тй2,с2) + У(Ш4 тйз,сз) У(пббзтт14~с4) Первая часть Ь/Ь+ Ь/Ь формулы для /(Ь, Ь, с) в (19) приводит к добавлению ТП2 Ш1 ШЗ ТП2 П14 ТПЗ Тйб ТП4 — + — — — — — + — + — — — —— ТП1 тг тг тб тз тб тб тб к общей формуле, которая сводится к п11 тпз тпг т4 тз — пбб п14 Ь + + — — — +аз — аг+ аз — аб.
Ь тг Тйз Ш4 тпб Следующая часть (19), 1/ЬЬ, также приводит к простому добавлению; в соответ- ствии с 4.5.3-(9) и другими формулами раздела 4.5.3 получим 1 1 1 1 Ь' + (35) 3 тп\ тп2 ш2шз тзш4 Ш4™б й где Ь' — единственное целое число, удовлетворяющее (36) ЬИЬ ив з 1 (по модулю Ь), 0 < Ь' < Ь. Тпз = абпзг + Тпз тпг = агтз + тйб ттбз = азт4 + ™б тб = абтб с1 = 61Тпг+ сг сг = 62тз + сз сз = Ьзтб + сб сб 51тпб + сб Добавляя все эти слагаемые, вспомним о предположении, что с4 — — 0 (так что е(тз, сз) = О, см.
(20)). Находим, что Ь+ Ь' а(Ь,к,с) = + (аз — аз+аз — ав) — 6(ьз— Ь ь, + ь, — ь,) с2 сз сз 2 + 3 +2 газ«аз газ щ4 ™44пь / сз +6 ЗП! Газ в терминах таблицы (32). Подобный результат имеет место в общем случае. Теорема П. Пусть Ь, Ь и с — целые числа с 0 < Ь < Ь, 0 < с < Ь и Ь, взаимно простым с Ь. Образуем "таблицу Евклида", как определено в (32), и предположим, что процесс остановится после 1 шагов с тз Ы -- 1. Пусть 3 — наимеиыпий индекс, для которого с, = О, и пусть число Ь' определено в (36). Тогда Ь+ Ь' / с2 а(Ь,к,с) = + ~~~ ( — цу+'~ау — 6Ь, +6 2 <1<4 + 3(( — Ц'+ б,з) — 2+ (-Ц'.
1 Алгоритм Евклида тщательно анализируется в разделе 4.5.3; величины аы аз, ..., аз называются часпзичнмззи отношениями Ь/Ь. Теорема 4.5,3Е указывает, что число итераций 3 никогда не превосходит!ойь Ь; следовательно, суммы Дедекинда могут быть быстро вычислены. Члены сз/пз пз +3 можно упростить еще больше; эффективный алгоритм для оценки а(Ь, Ь, с) можно найти в упр. 17. Изучив обобщенные суммы Дедекинда, применим полученные знания для вычисления сериального коэффициента корреляции.
Пример 1. Найти серпвльпый коэффициент, когда пз = 23ь„а = 234 + 1, с = 1. Решение. Из (17) следует, что справедливо соотношение (2зьа(234+ ! 2зь Ц 3+ 6(223 (234 Ц Ц)/(22о Ц Чтобы вычислить а(234 + 1, 233, Ц, можно образовать следующую таблицу. Так как Ь' = 234 + 1, это значение в соответствии с теоремой П становится равным 233 — 3+ 2 32. Таким образом, С = (2 в+5)/(22о ц 1+«, !«! < 2-вт (37) Подобная корреляция намного превышает ту, которая должна быть у гчучайной последовательности. Конечно, этот генератор имеет очень низкий потенциал и его можно было бы отбросить и раньше, как неслучайный. П21 Щз = Пьз = П24 = гаь = 233 234+ 1 2з4 2 1 аз — — 1 аз=1 аз = 233 -1 а4 — — 2 сз =1 С2 сз — — 1 с4 = 1 сь — — 0 ь,=о 52=0 Ьз — — 0 Ь4 — 1 Пример 2.
Найти прябляженное значение когда т = 10'з, а = 10001, с = 2113248653. Решение. Справедливо равенство С = следующим образом: коэффициента серивльной корреляции, бт(а, т, с)/т. Вычислении производим сз = 2113248653 сг = 7350 сз = 50 сз = 0 тд = 10000000000 тг = 10001 тз= 100 тз 1 Ь, = 211303 Ьг= 73 Ьз —— 50 аз = 999900 аг — — 100 аз = 100 а(тг,тз,сз) = -31.6926653544; С вЂ” -3 10 з. (38) На самом деле это очень приемлемое значение С. Но потенциал генератора равен только 3, так что реально это не очень хороший датчик случайных чисел, несмотря на то что у него низкая ссрпзльная корреляция. Таким образом, необходимо (но не достаточно) иметь низкий сериальный коэффициент корреляции. Пример 3.
Оценить серивльцую корреляцию для произвольных а, бп я с. Реп!ение. Если применить тачько один раз соотношение (30), то пазучится т сг с бт(а, т, с) — + 6 — — 6- — а(т, а, с). а ат а Поскольку из упр. 12 следует, что [а(т, а, с) ~ с а, справедливы соотношения С ' ' -(1 — б — бб( — )). (39) Небольшие познания — опасная вещь. — АЛЕКСАНДР ПОП (АЬЕХАМОЕбб РОРЕ), эссе о кРитике, 215 (1711) Если серьезно проанализировать ошибки, то можно лучше понять, как были допущены злоупотребления в (39). Во-первых, кое-кто некритична предполагал, что маленькая сериальная корреляция по целому периоду является хорошей гарантией Ошибка этой аппроксимации по абсолютной величине меньше (а + 6)/т.
Оценка в (39) — это первый известный теоретический результат, касающийся случайности конгруэнтных последовательностей (генераторов). Р. Р. Ковзю (В. В. Сохеуоп) [ЗАСМ 7 (1960), 72-74] получил его методом усреднения по всем действительным числам т, лежащим между 0 и т, вместо того, чтобы рассматривать только целые числа (см. упр. 21). Затем Мартин Гринбергер (Магг!п ОгеепЬегйег) [МасЛ. Собир. 15 (1961), 383-389) нашел точное отклонение, включая и оценку ошибки. Так началась одна из самых грустных глав в истории компьютерной науки! Хотя приведенная выше аппроксимация была вполне корректной, она была совершенно неприемлемой на практике.
Люди отбросили хорошие генераторы и заменили их ужасными генераторами, казавшимися хорошимн с точки зрения критерия (39). Более чем на десятилетие репутация наиболее используемых генераторов случайных чисел была серьезно подорвана только в связи с прогрессом теории. случайности. На самом же деле она не может обеспечить даже маленькую сериальную корреляцию для 1 000 последовательных элементов последовательности (см. упр. 14). Во-вторых, (39) и точность приближения обеспечивают относительно малое значение С только при а в ~/т. Поэтому предлагалось выбирать множитель, равный примерно ~/т.
На самом деле почти все множители дают значения С, постоянно меньшие, чем 1/~/т, поэтому (39) не является очень хорошей аппроксимацией истинного поведения оценки. Минимизация грубой верхней границы С не минимизирует само значение С. В-третьих, было замечено, что (39) дает свои самые лучшие оценки, когда с/тп з х е ~/3, (40) Теорема К. Прн предположениях теоремы О всегда выполняется 1 а — —. (41) 1 с<у<с 1 — — ау — ~ а < а(Ь,Ь,с) с<у<с с<с<с !<1<с 1»еа 1 еаа с ече» С ече» Доказательство. Обратитесь к работе Д. Э.
Кнута (В. Е. КппсЬ, Асса АгсйЬ- шеВса ЗЗ (1978), 297-325), в которой, кроме всего прочего, показано, что эти границы, по существу, — наилучшие возможные границы, когда частичные отношения большие. $ Пример 4. Оцените серивльиую корреляцию для а = 3141592б21, т = 2зь и нечетного с. Решение. Частичные отношения а/т равны 10, 1, 14, 1, 7, 1, 1, 1, 3, 3, 3, 5, 2, 1, 8,'7, 1, 4, 1, 2, 4, 2. Таким образом, по теореме К вЂ” 55 < а(ач гп, с) < 67.5 и сериальная корреляция гарантированно будет крайне низкой для всех с. Заметим, что эта граница значительно лучше, чем можно было получить из (39), так как ошибка в (39) имеет порядок а/т.
Наш егтучайныйе множитель не может быть настолько лучше специально выбранного множителя, чтобы хорошо выглядеть так как эти значения являются корнями уравнения 1 — бх+ бхт = О. »При отсутствии любого другого критерия выбора с можно использовать и этот." Последнее утверждение имеет смысл, но оно вводит в лучшем случае в заблуждение, так как эксперимент показал, что значение с оказывает большое влияние на истинное знасение сериального коэффициента корреляции, когда а — хороший множитель. Выбор (40) в значительной степени снижает значение С только в случаях, аналогичных примеру 2.
И мы обманываем себя, так как плохой множитель продемонстрирует свои недостатки другим путем. Ясно, что необходима лучшая оценка, чем (39), Такан оценка сейчас доступна благодаря теореме В, в основных чертах доказанной в работе Ульриха Дитера (1ЛНсЬ В!есег) [МаСЬ. Сошр. 25 (1971), 855 — 883]. В соответствии с теоремой В а(а,сп,с) будет малым, если частичные отношения а/т малы. Кроме того, детальнее анализируя обобщенные суммы Дедекинда, можно получить вполне точные оценки.
при использовании (39). На самом деле можно показать, что среднее значение , а„взятое по всем множителяи а, относительно простым с т, равно — (1и т)з + 0((1ой т)(1о51обт)') (см. упр. 4.5.3-35). Поэтому вероятность того, что случайный множитель имеет большую сумму Я, а„скажем, больше (1обт)'ч' для некоторого фиксированного е > О, стремится к нулю при т -~ оо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
