[Указание. Ваши экспоненциальные суммы должны включать С = g,/i"-) так же, как и.] Докажите, что в этом случае "средний" первообразный корень имеет разброс jDm-i = О (t(log m)4tp{m - 1)), следовательно, хороший первообразный корень существует для всех т.

29. [НМ22] Докажите, что величина Гтах из упр. 27 никогда не будет больше Х/у/Ьщ.

30. [МЗЗ] (С. К. Заремба (S. К. Zaremba).) Докажите, что Гтах = 0(max(ai,.. .,as)/m) в двумерном случае, когда ai, ..., Os - это частичные отношения, полученные в результате применения алгоритма Евклида к m и а. [Указание. В обозначениях из раздела 4.5.3 справедливо равенство а/тп = oi,..., а, ; примените упр. 4.5.3-42.]

31. [НМ47] (И. Борот (I. Borosh).) Докажите, что для всех достаточно больших тп существует взаимно простое с тп число а, такое, что все частичные отношения а/т меньше или равны 3. Кроме того, множество всех т, удовлетворяющих этому условию, но с частичными отношениями < 2, имеет положительную плотность.

► 32. [М21] Пусть mi = 21 - 1 и тг = 2 - 249 - модули генератора (38).

a) Покажите, что если Un = (Xn/mi - Уп/тг) mod 1, то Un « Zn/mi.

b) Пусть Wo = (Xomi - Yomi) modm и Wn+i = aWn modm, где a и m имеют значения, приведенные в разделе после формулы (38). Докажите, что существует простое соотношение между Wn и Un-

fB следующем издании данной книги я планирую ввести новый раздел 3.3.5 под названием "L-алгоритм". Это будет отклонение от общей темы ("Случайные числа"), но в нем будет продолжено рассмотрение решетчатого базиса, описанного в разделе 3.3.4. Основным предметом изучения станет неоклассический алгоритм А. К. Ленстра (А. К. Lenstra), Н. W. Lenstra, Jr., and L. Lovasz, Math.Annalen 261 (1982), 515-534, для нахождения приближенно оптимального множества базисных векторов и демонстращ{и того, что алгоритм можно применять к другим исследованиям. Примеры таких исследований приводятся в следующих статьях и содержащейся в них библиографии: М. Seysen, Cotnbinatorica 13 (1993), 363-375; С. Р. Schnorr and Н. Н. Homer, Lecture Notes in Сотр. Sci. 921 (1995), 1-12.

3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

В ПРЕДЫДУЩИХ РАЗДЕЛАХ МЫ обсуждали, как генерировать на компьютере последовательность чисел Uq, Ui, U-z, , которые ведут себя так, как если бы каждое число выбиралось независимо и случайно между О и 1 с равномерным распределением. Однако при использовании случайных чисел часто требуются другие виды распределений. Например, чтобы сделать случайный выбор из к альтернатив, нужны случайные целые числа, лежащие между 1 и /с. Если необходимо моделировать случайное время ожидания между появлениями независимых событий, желательно получить случайные числа с показательным распределением. Иногда в случайных числах нет необходимости, но нужны случайные перестановки (случайное размещение п объектов) или случайное сочетание (случайный выбор к объектов из совокупности, содержащей п объектов).

В принципе, любая из этих случайных величин может быть получена из равномерно распределенных случайных величин Uq, U\, U2,---- Значительное число

"случайных трюков" было придумано для эффективного преобразования равномерно распределенных случайных чисел. Изучив эти методы, получим возможность правильно использовать случайные числа при любом применении метода Монте-Карло.

Вероятно, что кто-нибудь когда-нибудь придумает генератор случайных чисел, который будет вырабатывать одну из этих случайных величин непосредственно, а не косвенно через равномерное распределение. Но прямые методы, как доказано, не практичны, за исключением генератора "случайный двоичный разряд", описанного в разделе 3.2.2. (См. также упр. 3.4.1-31; в нем равномерное распределение используется, главным образом, для инициализации, после которой метод является почти полностью прямым.)

В следующем разделе предполагается наличие случайной последовательности равномерно распределенных между О и 1 независимых действительных чисел. Равномерно распределенная случайная величина U генерируется всякий раз, когда в ней возникает необходимость. Эти числа обычно представлены в компьютере словом с десятичной точкой слева.

3.4.1. Численные распределения

В этом разделе объединены наиболее известные методы получения случайных чисел для различных важных распределений. Многие из методов первоначально были предложены Джоном фон Нейманом (John von Neumann) в начале 50-х. Постепенно они усовершенствовались другими математиками, особенно Джорджем Марсалья (George Marsagha), И. Г. Аренсом (J. И. Ahrens) и У. Дитером (U. Dieter).

А. Случайный выбор из ограниченного множества. Самые простые и наиболее общие типы распределений, используемых в приложениях, - это распределения случайных целых чисел. Целые числа между О и 7 могут быть извлечены из трех двоичных разрядов U на бинарном компьютере; поэтому эти три двоичных разряда можно извлечь из старшей значащей (слева) части компьютерного слова, поскольку самые младшие двоичные разряды, производимые многими генераторами случайных чисел, недостаточно случайны (см. раздел 3.2.1.1).

в общем случае случайные целые числа X, которые лежат между О и А; - 1, можно получить, умножив и на, к и положив X = [kU\. На MIX можно записать

LDA и ,,4

MUL К

После выполнения этих двух операций требуемое целое число появится в регистре А. Чтобы получить случайное целое число, лежащее между 1 и А;, следует добавить единицу к этому результату. (Операция "INCA 1" последует за (1).)

С помощью данного метода каждое целое число можно получить с приблизительно равной вероятностью. Существует незначительная ошибка, так как длина слова компьютера конечна (см. упр. 2), но эта ошибка совершенно незначительна, если А; мало, например к/т < 1/10000.

В более общем случае можно получить, если необходимо, различные веса для различных целых чисел. Предположим, что значение X = xi должно быть получено с вероятностью pi, X = Х2 - с вероятностью р2) • • • и X = - с вероятностью рк-Генерируем равномерное число U и положим

Х= <

Xl, если О <и < pi;

Х2, если pi <и < Р1+Р2;

. Хк, если pi -(- р2 Н----+ Рк-1 <и <1.

(Заметим, что pi -f Н-----hpk = 1-)

Существует "наилучший возможный" способ сравнения U с различными значениями Pi + Р2 + + Ps, как подразумевается в (2) (см. раздел 2.3.4.5). В частных случаях можно обойтись более эффективными методами; например, для того, чтобы получить одно из одиннадцати чисел 2, 3, ..., 12 с соответствующими "игре в кости" вероятностями можно вычислить два независимых

случайных целых числа между 1 и 6 и сложить их.

Тем не менее существует действительно более быстрый способ выбора Xi, Хк с произвольно заданной вероятностью, основанный на остроумном подходе, который был введен в употребление А. Дж. Уолкером (см. А. J. Walker, Electronics Letters 10,8 (1974), 127-128; ACM Ъ-ans. Math. Software 3 (1977), 253-256). Предположим, что мы образуем kU и рассматриваем целую часть К = [kU\ и дробную часть V = (kU) mod 1 раздельно, например после выполнения операций (1) получим К в регистре А и У - в регистр. Затем всегда можно получить желаемое распределение, выполнив операции

если V<Pk, то Xt-XK+i, иначе Х--Ук (3)

для некоторых подходящих таблиц (Pq,..., Pk-i) и {Уо,Fjt-i). В упр. 7 показано, как вообще можно вычислить такие таблицы. Метод Уолкера иногда называют методом псевдонимов .

На бинарном компьютере обычно полезно предполагать, что А; является степенью 2, потому что умножение может быть заменено сдвигом. Это можно делать без потери общности, введя дополнительные xj, которые появляются с вероятностью 0. Например, снова рассмотрим игру в кости. Предположим, что равенство X = j