прямоугольника. Определите длительность каждого шага алгоритма R для каждого из четырех вариантов в (25) в терминах А, R, I и Е.

21. [НМ29] Найдите формулы для величин А, Я,/и Е, определенных в упр. 20. (Для / и особенно для Е можно использовать интерактивную алгебраическую систему.) Покажите, что с = е - наилучшая возможная постоянная на шаге R2 для проверки "А < 4(1 +1пс) -4с[7".

22. [НМ40] Можно ли получить точное пуассоновское распределение для больших р генерируя приближенно нормально распределенную величину, превращая ее в целочисленную некоторым подходящим способом и применяя (возможно, сложную) коррекцию в небольшом числе случаев?

23. [НМ23] (Дж. фон Нейман.) Будут ли следующие два способа генерирования случайной величины X эквивалентны (т. е. будут ли случайные величины X при этом одинаково распределены)?

Метод 1. Присвоить А <- sin((7r/2)C/), где U - равномерно распределенная случайная величина.

Метод 2. Генерировать две равномерно распределенные случайные величины С/ и V; если ц2 у2 - повторять генерирование до тех пор, пока + V < 1. Затем присвоить А <г- \и - 1/2/(С/2 + V).

24. [НМ4О] (С. Улам (S. Ulam) и Дж. фон Нейман.) Пусть vq - случайно выбранное действительное число между О и 1. Определим последовательность (Vn) с помощью правила Vn+i = 4Уп{1 - Vn). Если произвести вычисление с хорошей точностью, то в результате получится такая же последовате.льность, как случайная последовательность sin nlln, где Un - равномерно распределенные случайные величины, т. е. с функцией распределения члена последовательности, равной F{x) = dx/27rx{l - х). Если записать Уп = sin irUn, то получим, что Un+1 = (2С/п) mod 1. Так как почти все действительные числа имеют случайное двоичное представление (см. раздел 3.5), полученная последовательность Un будет равнораспределенной. Однако если вычисление Уп выполняется только с ограниченной точностью, то наши аргументы становятся несостоятельными, поскольку будет мешать ошибка округления, [См. работу фон Неймана Collected Works 5, 768-770.]

Проанализируйте последовательность (Уп), определенную в разделе 3.3.4, когда вычисления производятся только с ограниченной точностью. Выполните эмпирический и теоретический анализ (для различных vq)- Будет ли последовательность иметь распределение, подобное ожидаемому?

25. [М25] Пусть Xi, Х2, .. , Х5 ~ двоичные слова, каждый двоичный разряд которых является независимой случайной величиной, принимающей значение О или 1 с вероятностью 5. Чему равна вероятность того, что расположение данных двоичных разрядов Al V {Х2 Л (Аз V {Х4 Л As))) содержит 1? Обобщите результат.

26. [М18] Пусть NiH N2 - независимые пуассоновские случайные величины со средними Hi и Ц2, где pi > Ц2> 0. Докажите или опровергните следующие утверждения: (а) N\ 4- N2 имеет распределение Пуассона со средним щ + Ц2\ (Ь) Ni - N2 имеет распределение Пуассона со средним - 2-

27. [22] (И. Г. Арене.) В большинстве бинарных компьютеров существует эффективный способ подсчета единиц в бинарном слове (см. раздел 7.1). Следовательно, существует хороший путь получения биномиального распределения (<,р), когда Р = 5, путем генерирования t случайных двоичных разрядов и подсчета числа единиц.

Предложите алгоритм, который генерирует случайные числа с биномиальным распределением {t,p) для произвольного р, используя в качестве источника случайных чисел только программу для частного случая, когда Р = [Указание. Моделируйте сначала

процесс, который выглядит, как выбор самого старшего двоичного разряда равномерно распределенной случайной величины t, затем - как выбор второго двоичного разряда этой случайной величины, если старшего двоичного разряда недостаточно, чтобы определить, будет ли случайная величина < р, и т. д.]

28. [НМ35] (Р. П. Брент.) Разработайте метод генерирования случайной точки на поверхности эллипсоида, определенного следуюш;им образом: akxl = 1, где ai > > йп > О-

29. [М20] (Дж. Л. Бентли (J. L. Bentley) и Дж. Б. Сакс (J. В. Saxe).) Найдите простой метод генерирования п равномерно распределенных между О и 1 чисел Al, ..., Хп, требуя, чтобы они были упорядочены: Xi < < Хп- Алгоритм должен состоять только из 0{п) шагов.

30. [МЗО] Объясните, как генерировать множество случайных точек {Xj,Yj), таких, что если R - некоторый прямоугольник площадью а, содержащийся в единичной сфере, числа (Xj, Yj), лежащие в R, имеют пуассоновское распределение со средним ар.

31. [НМ39] (Непосредственное генерирование нормальных случайных величин.)

a) Докажите, что если af Н-----1- а = 1 и Al, ..., А* - независимые нормально распределенные случайные величины со средним О и дисперсией 1, то aiXi -I- • • -I- ПкХк - нормальные случайные числа со средним О и дисперсией 1.

b) В доказательстве (а) предполагается, что можно генерировать новые нормальные случайные величины, используя старые точно так, как получают новые равномерно распределенные случайные величины из старых. Например, можно использовать идею 3.2.2-(7), но с рекуррентным соотношением, подобным

Хп = {Хп-24 + Xn-55)/V2 или Х„ = f Х„-24 + Х„-55,

после получения множества нормальных случайных величин Хо, . •., Х54. Объясните, почему это нехорошая идея.

c) Покажите, тем не менее, что существует более быстрый по сравнению с другими метод генерирования нормальных случайных величин, использующий усовершенствованные идеи (а) и (Ь). [Указание. Если X и У - независимые нормальные случайные величины, то такими же будут X = X cosO + Y sinO и Y = -Аsin б + Y cosO для любых углов в.]

32. [НМЗО] (К. С. Уоллес (С. S. Wallace).) Пусть X и У - независимые случайные величины с показательным распределением со средним 1. Докажите, что X и У также являются независимыми случайными величинами, имеющими показательное распределение со средним 1, если получить их из X и У любы.м из следующих способов.

a) Задана О < Л < 1,

X = (1 - Л)Х - ЛУ -Ь (X + У)[(1 - Л)Х < ЛУ], у = X + у - X.

bw vv - / У - X), если X < У;

b) (Х,У ) - < (2У, А - У), есяи X > У.

c) Если X и У имеют двоичное представление X = (... X2a;ixo.a; ix 2a; 3 ... )2 и У = (• • • У2У1У0-У-1У-2У-3 )2, то А" и У имеют "перемешанные" значения

X = (. . .Х2У1ХО.У-1Х-2У-З . . • )2, у = (• У2Х1У0.Х-1У-2Х-3 • • • )2.

33. [20] Алгоритмы Р, М, F и R генерируют нормальные случайные величины, поглощая неизвестное число равномерно распределенных , случайных величин Ui, U2, Как их можно преобразовать, чтобы на выходе получить функцию только от одной случайной величины и?

3.4.2. Случайные выборки и перемешивания

В многочисленных случаях при обработке данных для беспристрастного выбора п случайных записей приходится обращаться к файлу, содержащему N записей. Такая проблема возникает, например, при контроле качества или других статистических вычислениях, где используются выборки. Обычно N очень велико, поэтому невозможно хранить сразу все данные в памяти, да и отдельные записи часто настолько большие, что в памяти нельзя содержать даже п записей. Поэтому необходима эффективная процедура для выбора п записей, которая определяла бы одно из двух - принимать или отбрасывать каждую запись при ее появлении, записывая принятую запись в выходной файл.

Для решения данной проблемы разработано несколько методов. Наиболее очевидным подходом является выбор каждой записи с вероятностью n/N. Возможно, иногда такой подход оправдан, но он дает в среднем только п записей в выборке. Среднеквадратичное отклонение равно уп(1 - n/N), и выборка может оказаться либо слишком большой либо слишком малой, чтобы дать необходимые результаты.

К счастью, простое преобразование "очевидной" процедуры позволяет получить то, что нужно: {t + 1)-я запись будет выбрана с вероятностью {п - m)/{N - t), если т записей уже выбраны. Эта вероятность обоснована, поскольку среди всех возможных способов такого выбора п записей из N, чтобы точно т записей было выбрано из первых t, доля способов, когда при этом выбирается также и {t + 1)-я запись, равна

(N-t-l/fN-tn-m

\n-m-lJ/ \n-mJ N-t

(Иначе говоря, это вероятность выбора (i-f 1)-й записи при условии, что п записей из Л выбирались так, что среди первых t было выбрано ровно т записей. - Прим. ред.)

Идея, развитая в предыдущем разделе, немедленно приводит к следующему алгоритму.

Алгоритм S (Техника подбора выборки). Выбрать п записей случайным образом из множества Л, где О < п < N.

51. [Инициализация.] Присвоить ( О, m 0. (В этом алгоритме т является числом записей, выбранных ранее, at - общим числом введенных записей, с которыми мы работаем.)

52. [Генерировать U.] Генерировать случайное число U, равномерно распределенное между О и 1.

53. [Проверка.] Если {N - t)U > п - т, перейти к шагу S5.

54. [Выбор.] Включить следующую запись в выборку и увеличить m и ( на 1. Если m < п, перейти к шагу S2. Иначе выборка является полной и алгоритм завершен.

55. [Пропустить.] Пропустить следуюпдую запись (не включать ее в выборку), увеличить < на 1 и вернуться к шагу S2.

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