которое по невероятному совпадению преобразовалось само в себя по алгоритму (табл. 1). С другим стартовым числом последовательность начала повторяться после 7401 значения с периодом длиной 3178.

Мораль этой истории в том, что случайные числа не следует генерировать методом, выбранным наудачу. Не мешало бы использовать немного теории.

В следующих разделах будут рассмотрены генераторы случайных чисел более высокого уровня, чем метод средин квадратов и алгоритм К. Соответствующие последовательности гарантированно обладают желаемыми случайными свойствами и не вырождаются. Мы исслед-ем некоторые причины такого, похожего на случайное, поведения, а также покажем, как можно обращаться со случайными числами. Например, одно из наших исследований будет посвящено программе, которая тасует смоделированную на компьютере колоду карт.

В разделе 3.§ приводятся итоги к этой главе и содержатся некоторые библиографические источники.

УПРАЖНЕНИЯ

► 1. [20] Предположим, вы хотите получить случайную десятичную цифру. Какой из следующих методов вы выберете?

a) Откроете телефонный справочник, ткнув пальцем куда-нибудь, выберете первый попавшийся номер телефона и возьмете младшую цифру (цифру младшего разряда) этого номера.

b) Поступите, как в (а), но выберете младшую цифру номера страницы.

c) Покатите игральную кость в форме икосаэдра, имеющую двадцать граней, которые помечены цифрами О, 0,1,1,..., 9,9. Когда кость остановится, выберете верхнюю цифру. (Для катания игральной кости рекомендуется использовать стол с хорошо натянутым сукном.)

d) На одну минуту выставите счетчик Гейгера у источника радиоактивного излучения (предварительно обезопасив себя) и воспользуетесь младшей цифрой показаний счетчика. Предполагается, что на счетчике Гейгера представлены числа в десятичной системе счисления и вначале на нем был установлен нуль,

e) Бросите быстрый взгляд на свои часы и, если секундная стрелка находится между 6п и 6(п + 1) секундами, выберете цифру п.

f) Попросите приятеля задумать любую цифру и воспользуетесь ею.

g) Попросите врага задумать любую цифру и воспользуетесь ею.

h) Предположите, что 10 лошадей участвуют в забеге и вам о них абсолютно ничего не известно. Присвоите каждой лошади в произвольном порядке номер от О до 9, а после забега выберете в качестве случайной-цифры номер победителя.

2. [М22] Какова вероятность того, что в случайной последовательности из миллиона десятичных цифр каждая возможная цифра встречается ровно 100 ООО раз?

3. [10] Какое число следует за 1010101010 в методе средин квадратов?

4. [20] (а) Почему на шаге К11 алгоритма К значение X не может быть равно нулю? Какая ошибка,возникла бы в алгоритме, если бы X мог принимать Значение "нуль"? (Ь) Используя табл. 1, установите, что происходит, когда алгоритм К применяется повторно со стартовым значением X = 3830951656.

5. [15] Объясните, почему в любом случае, даже если совпадение, приведенное в табл. 1, не произошло, алгоритм К не сможет выдать бесконечную последовательность случайных чисел в том смысле, что любая последовательность, генерируемая алгоритмом К, станет в конце концов периодичной.

► 6. [М21] Предположим, что необходимо получить последовательность целых случайных чисел Хо, Xi, Х2, ... на интервале О < Х„ < т. Пусть f{x) - любая функция, такая, что неравенство О < ж < m влечет О < f{x) < т. Рассмотрим последовательность Xn+i = f{X„). (Примеры таких последовательностей - метод средин квадратов и алгоритм К.)

a) Покажите, что такая последовательность периодична в том смысле, что существуют числа Хи fj,, для которых значения

Хо, Xi, Xfi, ...,ЛГ4-л-1

различны, однако Хп+х = Х„, когда п > ц. Определите возможные максимальное и минимальное значения ц и X.

b) (Р. Флойд (R. W. Floyd).) Покажите, что существует такое тг > О, что Хп = Х2„ и наименьшее такое значение п лежит в интервале ц < п < fi + X. Более того, значение Х„ является единственным в том смысле, что если Хп = Х2п ч Хг = Хгт, то Хг = Хп

c) Используя идеи (Ь), составьте алгоритм вычисления и Л для любой заданной функции / и любого заданного Хо, используя только 0{р+Х) шагов и только ограниченный объем памяти.

► 7. [М21] (Р. П. Брент (R. Р. Brent), 1977.) Пусть £{п) - наибольшее целое число, такое, что е{п) < п, i{n) = 2*, где к - целое число. Так, например, (15) = 8 и £{Е{п)) = е{п).

a) Покажите, что в терминах обозначений упр. 6 существует такое п > О, что Хп = ЛГ£(„) 1. Найдите формулу для наименьшего такого п в терминах чисел fj, и X, определяющих период.

b) Примените этот результат для составления алгоритма, который может быть использован совместно с любым генератором случайных чисел типа Xn+i = ЦХп), чтобы предотвратить циклическую неопределенность. Вашему алгоритму следует вычислять период длиной Л и использовать только небольшой объем памяти - вы просто не должны заполнять всю память вычисленными значениями последовательности!

8. [23] Выполните полную проверку метода средин квадратов для случая, когда десятичные числа состоят из двух цифр.

a) Можете начать процесс с любого из 100 допустимых чисел 00,01,..., 99. Сколько из этих значений в конечном счете приведут к повторению цикла (зацикливанию) 00,00,...? [Пример. Начиная с числа 43, получим последовательность 43, 84, 05, 02, 00, 00, 00, ....]

b) Сколько существует финальных циклов? Каков размер самого длинного цикла?

c) Какое начальное значение (или значения) даст наибольшее число различных элементов, прежде чем последовательность повторится?

9. [Ml4] Докажите, что метод средин квадратов, использующий 27г-значные числа в Ь-ичной системе счисления, имеет следующие недостатки: если последовательность включает любое число, в котором п старших значащих цифр - нули, то последующие числа становятся все меньше и меньше, пока не превратятся в нули.

10. [М16] Пусть выполняются предположения предыдущего упражнения. Что можно сказать о последовательности чисел, следующих за X, если младшие значащие п цифр числа X равны нулю? Что если п + 1 младших Значащих цифр равны нулю?

► 11. [М2б] Рассмотрим последовательности генераторов случайных чисел, имеющих вид, описанный в упр. 6. Если выбрать f{x) и Хо наудачу (другими словами, если предположить, что каждая из т"" возможных функций f{x) равновероятна и каждое из m возможных значений Хо равновероятно), то какова вероятность того, что последовательность в конечном счете выродится в цикл длиной Л = 1? [Замечание. Предположения этой задачи дают повод задуматься о "случайности" генераторов случайных чисел такого типа. Можно

ожидать, что метод, подобный алгоритму К, отчасти ведет себя так же, как рассмотренный здесь генератор; ответ на эту задачу дает колоссальное число совпадений в табл. 1.]

► 12. [М31] Какова средняя длина финального цикла, если выполняются предположения предыдущего упражнения? Какова средняя длина последовательности до вхождения в цикл? (В обозначениях упр. 6 необходимо определить средние значения X и fj, + X.)

13. [М42] Если f{x) выбрана наудачу, как в упр. 11, какова средняя длина самого длинного цикла, полученного путем варьирования начального значения Хо? [Замечание. Мы уже рассмотрели аналогичную проблему для случая, когда f{x) - это случайные перестановки; см. упр. 1.3.3-23.]

14. [М38] Если f{x) выбрано наудачу, как в упр. 11, каково среднее число различных финальных циклов, полученных в результате варьирования начальных значений? [См. упр. 8, (Ь).]

15. [М15] Если f{x) выбрано наудачу, как и в упр. 11, чему равна вероятность, что ни один из финальных циклов не имеет длину, равную 1, невзирая на выбор Хо?

16. [15] Последовательность, генерируемая, как в упр. 6, должна повторяться после того, как было сгенерировано не более т значений. Предположим, что мы обобщим метод таким образом, что Х„+1 будет зависеть от Xn-i так же, как от Хп; формально пусть f{x,y) - такая функция, для которой Q <х,у <т влечет неравенства О < f{x,y)< т. Последовательность строится так: сначала произвольно выбирают .Yo и .Yi, а затем полагают, что

Хп+1 = f(Xn,X„-i), где тг > 0.

Чему предположительно равен максимальный период в этом случае?

17. [10] Обобщите ситуацию из предыдущего упражнения так, чтобы Xn+i зависело от предыдущих к значений последовательности.

18. [М20] Придумайте метод, аналогичный методу из упр. 7, для определения цикла генератора случайных чисел, описанного в упр. 17, в общем виде.

19. [М48] Выполните упр. 11, используя упр. 15, в более общемслучае, когда Xn+i зависят от к предыдущих значений последовательности; каждая из т"" функций f{xi,... ,Хк) считается равновероятной. [Замечание. Число функций, которые дают максимальный период, анализируется в упр. 2.3.4.2-23.)

20. [30] Найдите все неотрицательные числа X < Ю", которые при использовании алгоритма К в конечном счете приводят к самовоспроизводящимся числам из табл. 1.

21. [42] Докажите или опровергните следующее утверждение: отображение X >-¥ f{X), определенное алгоритмом К, имеет ровно пять циклов длиной 3178, 1606, 1024, 943 и 1.

22. [21] (Г. Роллетшек (Н. Rolletschek).) Хороша ли идея генерирования случайных чисел с помощью последовательности /(0), /(1), /(2), ..., где / - случайная функция, вместо того, чтобы использовать хо, /(жо), fif{xo)) и т. д.?

► 23. [М26] (Д. Фоата (D. Foata) и А. Фучс (А. Puchs), 1970.) Покажите, что каждая из функций f{x), рассмотренных в упр. 6, может быть представлена как последовательность (жо,xi,...,Xm~i), имеющая такие свойства.

i) {xo,xi,.. .,xm-i) - это перестановки последовательности (/(0), /(1),..., /(т - 1)).

") (/(0), • •, /{т - 1)) может быть единственным образом восстановлена из последовательности {xo,Xi,. . . ,Xm-l).

iii) Элементы, которые появляются в циклах из /, имеют вид {xo,xi,... ,Xk-i}, где к - самый большой индекс, такой, что эти к элементов различны.

i) 3 {хо, xi,...,Xj~i} влечет Xj~i =/(xj), если не является наименьшим элементом в цикле из /.