Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 44
Текст из файла (страница 44)
д.] 28. [ИЮО] (Р. П. Брснт.) Разработайте метод генерирования случайной точки на поверхности эллипсопда, определенного следующим образом: 2 а»х» = 1, где а1 » . а > О. 2 29. [МОО] (Дж. Д. Бентлн (Л 1,. Вепйеу) н Дж. Б. Сакс (2. В. Бахе).) Найдите простой метод генерирования и равномерно распределенных между О и 1 чисел Л1,..., Х», требун, чтобы они были упорядочены; х1 « х,. Алгоритм должен состоять только из 0(п) агатов 30.
[МУО] Обьясните, как генерировать множество случайных точек (Хзч Уз), таких, что если Н вЂ” некоторый прямоугольник площадью о. содержащийся в единичной сфере, числа (Л, 1' ), лежащие в 12, имеют пувссоновское распределение со средним ор. 31. [ВМЯЛО] (Непосредственное генерирование нормальных случайных величии.) а) Докажите, что если а, + + аз = 1 и Х1, ..., Л» — независимые нормально распре. деленные случайные величины со средним О и дисперсией 1, то а»Л1+ . + а»Л»вЂ” нормальные случайные числа со средним О и дисперсией 1. Ь) В доказательстве (а) предполагается, что можно генерировать новые нормачьиые случайные величины, используя старые точно так, как получают новые равномерно распределенные случайные величины из старых, Например, можно использовать идею 3.2.2-(7), но с рекурреитным соотношением, подобным Х» = (Х -ы+Х -33),гчЛ или Л» 3Х» 24 + 2Х»-33, — 2 4 Х = (1 — А)Х вЂ” ЛУ+ (Х+ У) [(1 — Л)Л < ЛУ], У' = Л + 1' — Х .
( „„„) [(2Х,У вЂ” Х), солих<У; ) (Х*,У*) = ~~ с) Если Х и У имеют двоичное предстаю»ение Х = (...хзагхо.х »х зх-з.. )2 и 1 ( У»У»ро У-»У-»У-з, )2, то Л' и У' имеют "перемешанные" значения (' ' х2У!хо У-!х-2У-3 ° )2 У вЂ” ( .. у2х1уо.х-!у 2х 3... )2. ЗЗ. [ОО] Алгоритмы Р, М, Р и В генерируют нормальные случайные величины, поглощая неизвестное число равномерно рвсцредаченных, случайных величин (71, (72, ... Как их можно преобразовать, чтобы на выходе получить функцию только от одной случайной величины (1! после пшчучения множества нормальных случайных величии Хо,, Л 34. Объясните, почему это нехорошая идея.
с) Покажите, тем не менее, что сущесшвуегл более быстрый по сравнению с другими метод генерирования нормальных случайнмх величин, использующий усовершенствованные идеи (а) и (Ь). [Указание. Если Х и У вЂ” независимые нормальные случайные величины, то такими же будут Х' = Л совр+ У юпО и У' = -Л" зшО + У совр для любых углов О.] 32. [с»МЯО] (К. С. Уоллес (С. Б. АувПасе).) Пусть Л и У вЂ” независимые случайные величины с показате.чьным распределением со средним 1.
Докажите, что Х' и У' также являются независимыми случайньгми величинами, имеющими показательное распределение со средним 1, если получить их из Х и У любым из следующих способов. а) Заланаб<А<1, 3.4.2. Случайные выборки и перемешиванмя В многочисленных случаях при обработке данных для беспристрастного выбора и случайных записей приходится обращаться к файлу, содержащему Ж записей. Такая проблема возникает, например, при контроле качества илн других статистических вычислениях, где используются выборки. Обычно Х очень велико, поэтому невозможно хранить сразу все данные в памяти, да и отдельные записи часто настолько большие, что в памяти нельзя содержать даже и записей.
Поэтому необходима эффективная процедура для выбора и записей, которая определяла бы адно из двух — принимать или отбрасывать каждую запись при ее появлении, записывая принятую запись в выходной файл. Для решения данной проблемы разработано несколько методов. Наиболее очевидным подходом является выбор каждой записи с вероятностью и/Ф. Возможно, иногда такой подход оправдан, но он дает в среднем только и записей в выборке. с, ~..~, ..... '....,~ц~--;р-~,...г .
либо слишком большой либо слишком малой, чтобы дать необходимые результаты. К счастью, простое преобразование "очевидной" процедуры позволяет получить то, что нужно: (Ф + 1)-я запись будет выбрана с вероятностью (и — т)/(Ю вЂ” Ф), если т записей уже выбраны. Эта вероятность обоснована, поскольку среди всех возможных способов такого выбора и записей из Ю, чтобы точно т записей было выбрано из первых $, доля способов, когда при этом выбирается также и ($ + 1)-я запись, равна (Иначе говоря, это вероятность выбора (1+1)-й записи при условии, что и записей из Х выбирались так, что среди первых 1 было выбрано ровно т записей.
— Прим. ред.) Идея, развитая в предыдущем разделе, немедленно приводит к следующему алгоритму. Алгоритм 8 (Техника подбора выборки). Выбрать и записей случайным образом из множества Х, где О ( и < Х. 81. (Инициализация.) Присвоить | +- О, ш е- О. (В этом алгоритме т является числом записей, выбранных ранее, а 1 — общим числом введенных записей, с которыми мы работаем.) 82.
(Генерировать Ц Генерировать случайное число У, равномерно распределенное межлу О и 1, 83. (Проверка.] Если (Ю вЂ” Ф) У > и — т, перейти к шагу 85. 84. (Выбор.) Включить следующую запись в выборку и увеличить т и $ на 1. Если т с и, перейти к шагу 82. Иначе выборка является полной и алгоритм завершен, Вб.
(Пропустить.) Пропустить следующую запись (не включать ее в выборку), увеличить | на 1 и вернуться к шагу 82. 1 На первый взгляд, алгоритм может показаться ненадежным и на самом деле неправильным, но тщательный анализ (см. упражнение, пряведенпое ниже) показывает, что он вполне надежен. Нетрудно проверить следующие факты, а) Будет введено максимум Х записей (мы никогда не достигнем конца файла, пока не выберем п элементов). Ъ) Выборка полностью беспристрастна. В частности, вероятность того, что любой заданный элемент выбран, как, например, последний элемент файла, равна п/Ю.
Утверждение (Ь) справедливо несмотря на то, что выбран (1 + 1)-й элемент не с вероятностью и/Ф, а с вероятностью, заданной в (1) ) Это послужило причиной некоторой неразберихи в опубликованной литературе. Может ли читатель объяснить это кажущееся противоречие? (Замечание. Используя алгоритм В, следует позаботиться о наличии различных источников случайных чисел П при каждом выполнении программы во избежание зависимости между выборками, полученными в разные дни.
Это можно сделать, например, выбирая каждый раз различные значения Ло в линейном конгруэнтном методе. Начальному значению Ло может быть присвоено число месяца в день выполнения программы или последнее случайное число Л, которое генерировалось при предыдущем прогоне программы.) Обычно мы не проходим все Х записей. В самом деле, так как указанное вьппе утверждение (Ь) гласит, что последняя запись выбирается с вероятностью и/Х, вероятность того, .что работа алгоритма завершится до выбора последней записи, точно равна (1 — и/Х). Среднее число рассмотренных записей, когда и = 2, приблизительно равно ~3Х; общие формулы даны в упр. 5 и 6.
Алгоритм з' и другие подобные методы обсуждаются в работе Ч. Т. Фана, Мервина Э. Мюллера и Ивана Резуха (С. Т. Еап, Мегхш Е. Мийег, апд 1гап ВекисЬа, х Ашег. Ясак Аээос. 5у (1962), 387 — 402). независимо этот метод был открыт Т. Г. Джонсом (Т. С. 3опее, САСМ 5 (1962), 343). Если значение Ю заранее неизвестно, то возникают трудности, поскольку знание точного значения Х является решающим для выполнения алгоритма 6. Допустим,. необходимо случайно выбрать п записей из файла, если точно неизвестно, сколько записей в настоящее времи содержится в этом файле. Можно сначала пересчитать все записи, а затем перейти к выбору и записей, но лучше так выбрать т > и начальных записей на первом проходе, чтобы гп было намного меньше Х.
Тогда на втором проходе. нужно будет рассмотреть только ш записей. Искусство состоит, конечно, в том, чтобы прн подобном выборе в результате получить истинную случайную выборку из исходного файла. Так как заранее неизвестно, когда завершится ввод, "модель" случайной выборки из записей следует хранить на входе при первом просмотре, чтобы всегда быть готовым к его окончанию. При чтении файла мы строим '"резервуар", содержащий только записи, которые образуют предварительные выборки.
Первые и записей всегда будут входить в резервуар. Когда (г + 1)-я запись введена для $ > и, в памяти формируется таблица и индексов записей, которые были рыбраны среди первых г записей. Проблемой является сохранение этого состояния с 1, увеличенным на единицу, т. е. поиск новой случайной выборки среди 8 + 1 имеющихся известных сейчас записей. Нетрудно вилеть, что новую запись следует включить в выборку с вероятностью п/(1+ 1); при этом она заменит случайный элемент предыдущей выборки.
Итак, описанную работу выполняет следующий алгоритм. Алгоритм К (Резервуар выбора). Выбрать случайно и записей из файла неизвестного размера > и, п > 0 задано. Дополнительный файл назовем резервуаром, содержащим все записи, которые являются кандидатами для окончательной выборки. Алгоритм использует таблицу различных индексов 1[Я для 1 < / < и, каждый из которых указывает на одну из записей в резервуаре.
зс1. [Инициализация.] Введем первые и записей и скопируем их в резервуар. Присвоим 1[/] <- / для 1 < 1 < и и присвоим ! е- т +- и. (Если файл будет выборкой, имеющей меньше и записей, то, конечно, необходимо будет прервать выполнение алгоритма и сообщить о неблагоприятном исходе. В алгоритме индексы 1[1], ..., 1[п] указывают записи в текущей выборке; т является размерностью резервуара, а ! — номером входных записей, рассмотренных до снх пор.) Нй. [Конец файла?] Если записей на ввод больше нет, то перейти к шагу Йб. НЗ. [Генерирование и проверка.) Увеличить 1 на 1, затем генерировать случайное целое число А1 между 1 и 1 (включительно).
Если Аб > и, перейти к шагу Й5. К4. [Увеличить резервуар.1 Копировать следующую запись входного файла в резервуар, увеличить т на 1 и присвоить 1[И] +- т. (Запись, предварительно указанная как 1[А?], заменяется в выборке новой записью.) Возврат к шагу В2. 1ьб. [Пропустить.] Пропустить следующую запись входного файла (не включать ее в резервуар) и возвратиться к пигу Н2. Нб. [Следующий просмотр.] Упорядочить индексы 1 таблицы входов так, чтобы 1,"1] « . 1[п], затем тщательна разобрать резервуар. копируя записи с этими индексами в выходной файл, который фиксирует окончательный выбор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
