28. Пусть С = е/*"- и пусть Ski = Eo<j<m-i w+C"- Аналогом (51) будет равенство \Sko\ - у/т. Значит, аналогом (53) является

= 0((ч/т log m)/iV).

0<n<N

Теорема, аналогичная теореме N, сейчас утверждает, что

= + О ((logm)V...), D:i, = 0((logm)V.ax).

На самом деле D i < rf "("1, • • •,"() [суммируем по всем не равным нулю решениям (15)] + ;;E"("i, • , "О [суммируем по всем не равным нулю {щ,... ,ut)]. Из упр. 25, если положить d = 1, следует, что последняя сумма будет иметь порядок O(logTn). С полученной суммой поступим, как в упр. 27.

Рассмотрим величину R{a) = Er{ui,... где суммирование выполняется по

ненулевым решениям (15). Так как т - простое число, каждый (ui,... ,ut) может быть решением (15) для самое большее t - 1 значений а. Следовательно, Ео<а<т Щи) < (t - 1) Еiui,... ,щ) = C>(t(logTn)). Отсюда получаем, что среднее значение R{a), взятое по всем (fi{m - 1) первообразным корням, равно 0(t{\ogmy/(fi{m - 1)).

Замечание. Справедливо соотношение l/(fi{n) = 0(log log n/n), поэтому необходимо доказать, что для всех простых чисел т и для всех Г существует первообразный корень а по модулю тп, такой, что линейная конгруэнтная последовательность (1,а,0,тп) имеет разброс DLi = 0(Tn~r(logTn)loglogTn) для 1 < t < Г. Этот метод доказательства нельзя расширить, чтобы получить подобные результаты для линейного конгруэнтного генератора с периодом 2* по модулю 2, так как, например, вектор (1,-3,3,-1) будет решением (15) для приблизительно 2 значений а.

29. Чтобы получить верхнюю границу, позволим ненулевым компонентам и = (ui,..., щ) быть любыми действительными величинами 1 < Ы < fm. Если к компонент не равны нулю, то г{и) < 1/(2р(и)) в обозначениях ответа к упр. 27. И, если и? + • + и? равно данному значению v, минимизируем р{и), взяв щ = • = uk-i = 1 и ul = и - к + 1. Таким образом, г {и) < Xjly/v - fc + 1. Однако 2 Vi - fc + 1 > \/%v, поскольку i/ > fc > 2.

30. Сначала минимизируем q\aq - тпр для 1<д<тпиО<р<а. В обозначениях упр. 4.5.3-42 справедливо равенство ад„ -трп = {-l)"Ka~n-iian+2,... ,а«) для 0 < п < s. В области Qn-i < q < Яп справедливо неравенство \aq - тр\ > \aqn-i - тпрп-il; значит, q\aq - тр\ > qn-i\aqn-i - mpn-i\ и минимум равен mino<n<a Яп\адп - тр„\ = niino<n<j Kn{ai, ... , а„) Ka-n-i{an+2, ... , а,). Из упр. 4.5.3-32 следует равенство тп = Kn{ai, ... ,а„) On+i Кз-п-1{ап+2, ... , а,) + K„{ai, ... , an) Ка-п-2{ап+з, ... , а,) + Kn-i{ai, ... , Un-i) Ka-n-i{an+2, ... , Ua); и задача, по существу, состоит в нахождении максимума величины т/Кп{а\, ... , а„) Ка-п-\{ап+2, ... , а,,), лежащей между a„+i и ап+1-1-2.

Пусть сейчас А = max(ai,... ,as). Так как г(тп - и) = г(и), можно предположить, что Гтах - r(u)Г(au mod тп) для некоторого U с 1 < U < тп. Полагая и = min(aumodTn, (-au) modTn), получим Гтах = r{u)r{u). Из предыдущего раздела известно, что ии > qq, где А/т < l/qq < (А + 2)/тп. Кроме того, 2и < г{и)~ < пи для Q < и < тп, тогда Гтах < 1/(4W). Следовательно, Гтах < (А + 2)/(4тп). (Существует подобная нижняя грань, а именно - Гтах > А/(7гтп).)

31. Эквивалентное предположение состоит в том, что все большие тп могут быть записаны в виде тп = Kn{ai,..., Un) для некоторого п и некоторых а< € {1, 2, 3}. Для фиксированного п 3" чисел Kn{ai,... ,ап) имеют среднее значение порядка (1 + %/2)", и их стандартное

отклонение имеет порядок (2.51527)"; так что предположение почти всюду верно. С. К. Заремба (S. К. Zaremba) в 1972 году предположил, что все т могут иметь такое представление с а, < 5; Т. В. Кузик (Т. W. Cusick) достиг определенного прогресса в решении этой задачи в работе Mathematika 24 (1977), 166-172. Оказалось, что только в случаях, когда тп = 54 и тп = 150, требуются aj = 5, и самые большие mj, для которых необходимо а, = 4, - это 2052, 2370, 5052 и 6234; по крайней мере, автор нашел представление с а, < 3 для всех других целых чисел, меньших 2 ООО ООО. Чтобы выполнялось неравенство щ < 2, среднее K„{ai,... ,ап) должно быть равно 2" -(- (-2)~", в то время как стандартное отклонение растет как (2.04033)". Оказалось, что плотность таких чисел в эксперименте автора (автор рассмотрел 2® блоков из 2 чисел каждый для тп < 2°) изменялась между .50 и .65.

[См. работу I. Borosh and Н. Niederreiter, BIT 25 (1980), 193-208, в которой рассматривается вычислительный метод нахождения множителей с малым частичным отношением. Авторы нашли представление с а; для тп = 2, где 25 < е < 35.]

32. (а) Un - Zn/mi = (mj - mi)Yn/mim2 (по модулю 1) и (mi - m2)/mim2 и 2~". (Поэтому можно анализировать самый старший двоичный разряд Zn, а11ализируя Un-Младшие разряды, вероятно, также случайны, но эти соображения к ним ие применяются.) (Ь) Справедливо равенство Un = Wn/m для всех п. Из китайской теоремы об остатках следует, что достаточно только проверить соотношения Wn = Аптг (по модулю mi) и Wn = -Ynm\ (по модулю т), так как mi ± т. [Pierre LEcuyer and Shu Tezuka, Math. Сотр. 57 (1991), 735-746.]

РАЗДЕЛ 3.4.1

1. a-f (/3-a)f/.

2. Пусть и = Х/т, тогда [kU\ = г <=> г < кХ/т < г + 1 <=Ф- тг/к < X < т{г + 1)/к <=* \тг/к] < X < fm(r + 1)/к]. Точная вероятность задается формулой (l/m)([m(r + 1)/к] - \тг/к]) = 1/к + е, где е < 1/т.

3. Если заданы случайные числа, длина которых равна машинному слову, то результат будет отличаться от правильного распределения самое большее на 1/т, как показано в упр. 2, но все эксцессы приводят к наименьшим отличиям. Так, если к и т/3, результат будет меньше к/2 приблизительно в раз. Намного лучше получить совершенно равномерное распределение, отбросив U, если U > к[т/к\ [см. D. Е. Knuth, The Stanford GraphBase (New York: ACM Press, 1994), 221].

С другой стороны, если использовалась линейная конгруэнтная последовательность, то fc и модуль m должны быть взаимно простыми числами, иначе числа имеют очень короткий период, как следует из раздела 3.2.1.1. Например, если fc = 2 и m четное, наилучшими числами будут попеременно повторяемые числа О и 1. Метод слабее (1) почти в каждом случае, так что мы его не рекомендуем.

К сожалению, однако, операция "himult" в (1) отсутствует во многих языках высокого уровня (см. упр. 3.2.1.1-3). Деление т/к, возможно, наилучшее, когда "himult" отсутствует.

4. max(Ai, А2) < х тогда и только тогда, когда Xi < х и Х2 < х; min(Xi, А2) > х тогда и только тогда, когда Al > х и Х2 > х. Вероятность того, что два независимых события происходят одновременно, равна произведению вероятностей этих событий.

5. Получим независимые равномерно распределенные случайные величины Ui и С/г-Положим X <- U2. Если Ui > р, положим X <- тах(Х, [/3), где Us - третья равномерно распределенная величина. Если Ui > р+ q, положить также X «- тах(Х, [/4), где Щ - четвертая равномерно распределенная случайная величина. Этот метод можно очевидным образом обобщить для любой случайной величины с полиномиальной функцией распре-

Окружность U+V = 1

Рис. А-4. "Область принятия" для алгоритма из упр. 6.

деления и даже с функцией распределения, представимой в виде степенного ряда (как показано, например, в алгоритме S, вместо максимизации использующем минимизацию).

Можем поступить и следующим образом (предложение М. Д. Мак-Ларена (М. D. MacLaren)): если Ui < р, присвоить X <- f/i/p; иначе, если Ui < p + q, присвоить Л 4г- max(({7i -p)/q, U2); иначе присвоить X <- max{{Ui-p - q)/r, U2, U3). Этот метод по сравнению с другими требует меньше времени на получение равномерно распределенных случайных чисел, несмотря на то что он требует больше арифметических операций и несколько менее устойчив численно.

6. F{x) = Ai/{Ai + А2), где Ai и Лг - площади, показанные на рис. А-4, так что

, , 1о V-ydy 2 .2 rz-2

F{x) = ---- = - arcsinz -I-zv 1 - x.

Вероятность окончания процедуры на шаге 2 равна р = тт/4. Процедура продолжается до заверщения на шаге 2, поэтому число выполнений шага 2 имеет геометрическое распределение. Характеристиками этого числа являются (min 1, ave 4/п, max 00, dev {4/тт)л/1 - 7г/4) согласно упр. 17.

7. Если fc = 1, тогда ni = п, и задача тривиальна. В противном случае всегда можно найти г ф j, такое, что щ < п <nj. Заполните Bi щ кубиками цвета d к п ~ щ цвета Cj. Затем замените Uj иа п - щ и исключите цвет С{. Теперь перед нами стоит та же задача, но к меньше на 1. Следовательно, по индукции задача имеет решение.

Следующий алгоритм можно использовать, чтобы подсчитать Р и У для таблиц из (3). Образуем набор пар (pi, 1)... (р*,, fc) и рассортируем их по первой компоненте, получив набор (gi,oi)... (gfc,o/i), где qi < < qk- Присвоим n <- fc и будем повторять следующие операции до тех пор, пока не получим п = 0: присвоим P[ai - 1] <- kqi и Y[ai - 1] <- Жа„. Удалим (gi,ai) и (gn,a„), поместим-новый элемент {qn - (1/fc - qi),a.n) на его собственное место в наборе и уменьшим п на 1.

(Если Pj < 1/fc, то алгоритм никогда не поместит Xj в таблицу для У. Этот факт безоговорочно используется в алгоритме М. Алгоритм пытается максимизировать вероятность того, что V < Рк в (3), отбирая у самого "богатого" отброшенного элемента и отдавая самому "бедному". Однако очень трудно определить абсолютный минимум этой вероятности, поскольку подобная задача, по крайней мере, так же трудна, как "проблема упаковки корзин"; см. раздел 7.9.)

8. Нужно поменять местами Pj и {j + Pj)/k для О < j < fc.

9. Рассмотрите знак второй производной f"{x) = л/2/тт (z - 1)е~.

10. Пусть Sj = {j - 1)/5 для 1 < j < 16 и pj+ib = F{Sj+i) - F{Sj) - pj для 1 < j < 15. Пусть также рз1 = 1 - F(3) и рзг = 0. (Формула (15) определяет pi, ..., pis.) Алгоритм