AOP_Tom2 (1021737), страница 43
Текст из файла (страница 43)
9 еыпукладля Выпуклая кривая Вогнутая кривая х < 1 и вогнута длв х > 1? ь 10. [НМ04) Объясните, как вычислить вспомогательные постоянные Рэ, О„1'э, 8„8м Вэ, Е,. чтобы алгоритм М давал ответ с правильным распределением, ь 11. [НМ27] Докажите, что шаги М? и МО алгоритма М порождают глучайную величину с хвостом, бпнзким к нормальному распределению, т. е. вероятность того, что Х < х должна быть точно равна -гугдг / / -Р/гд1 х>3 / ~-.— з / уз [Указание. Покажите, что это частный случай метода отбраковки с д(г) = Сге ' г~ длн некоторого С.] 12. [НМ23] (Р. П. Брент (К. Р. Вгепг) ) Докажите, что числа а„определенные в (23), удовлетворяют соотношению а, — а,, < 2!и 2 для всех ! > 1.
г г [Указание. Если /(х) = е" гг ~' е ' !~А, покажите, что /(х) < /(у) для О < х < у.] 13. [НМ25] Дано множество и независимых нормальных случайных величин Хм Хг, Л„со средним О и дисперсией 1. Покажите, как найти константы Ь, и аи, 1 < ? < г < и, такие, что если )г = Ьг + амХг, 1г = Ьг+ аггХг + аггХг, ..., У» = Ь»+а»гХг + +а„„Х„, то Ум Уг,..., У вЂ” зависимые нормально распределенные случайные величины, 1'г имеют среднее р, и заданную ковариационную матрицу (си).
(Ковариации с,г между )) и 1 определяются как среднее значение случайной величины (К вЂ” д,)(1; — р, ). В частности, сН вЂ” это дисперсия 1;, квадрат их среднеквадратичных отклонений. Не все матрицы (си) люгут быть ковариационнымн, и ваше построение, конечно., будет работать всякий раэ, когда данное условие будет выполняться.) 14. [Мд!] Найдите распределение сЛ, если Х вЂ” случайная величина с непрерывной функцией распределения Р(х) и если с — постоянная (возможно, отрицательная). 18. [НМ2!] Если Лг и Хг — независимые случайные величины с соатветствующими функциями распределения Гг(х) и Рг(х) и плотностями /г(х) = Г,'(х), /г(х) = гг(х), какова функция распределения и плотность случайной величины Л г + Лг? ь 16.
[НМ22] (И. Г. Аренс.) Предложите алгоритм для генерированин случайной величины, имеющей гамма-распределение порядка а, когда О < а < 1, с помощью метода отбраковки с сд(1) = 1' '/Г(а) для О < 1 < 1 и с сд(г) = е '/Г(а) для г > 1. ь 17. [М24] Чему ранна функция распределения Г(х) случайной неличины, имеющей геометрическое распределение с параметром р? Чему равна производящая функция С(з)? Чему равны среднее и дисперсия этого распределения? 18. [М22] Предложите метод вычисления случайной целочисленной неличины !»', такой, что Аг принимает значение и с вероятностью прг(1 — р)" ', и > О.
(Когда р сравнительно мзлб, этот случай представляет особый интерес.) 19. [22] Случайная величина г»' с оглрицашеяьнмм биномиаяьным распределением с параметрами (1,р) принимает значения г»' = и с вероятностью (~ г ")р~(1 — р)". (В отличие от обычного биномиального распределения г не обязано быть целым, так как эта величина неотрицательна для всех и, каково бы ни была ! > О.) Обобщая упр. 18, объясните как генерировать целые случайные числа !»' с этим распределением, когда ! — малое положительное целое число.
Какай вы предложите метод длн 1 = р = гг? 20. [Мдд] Пусть А — площадь заштрихованной области на рис. 13, Н вЂ” площадь содержащего ее прямоугольника, 1 — площадь внутренней области, определенной на шаге К2, и Š— площадь между внутренней областью, отбрасываемой на шаге ВЗ, и другой частью прямоугольника. Оггределнте длительность каждого шага алгоритма В. для каждого из четырех вариантов в (25) в терминах А, В, ?и Е. 21. [НМ29] Найдите формульг для величин хй В, ?и Е, определенных в упр.
20. (Для? и особенно для Е можно использовать интерактивную алгебраическую систему.) Покажите, что с = е г . наилучшая возможная постоянная на шаге К2 для проверки "Х < !ы 4(1 + 1и с) — 4сст'. 22. [НМ40] Можно ли получить точное пуассоновское распределение для больших д, генерируя приближенно нормально распределенную величину, превращая ее в целочисленную некоторым подходящилг способом и применяя (возможно, сггожггую) коррекцию в небольшом числе случаев? 23. [ЯМЗЯ] (Дж. фон Нейман.) Ьудут ли следующие два способа генерирования случайной величины Х эквивалентны (т. а. будут лн случайные величины Х при этом одинаково распределены)? Метод 1.
Присяонть Х 2 в 21п((я/2)П), где П вЂ” равномерно распределенная случайная величина. Метод 2. Генерировать две равномерно распределенные случайные величины П и?г; если П + 1г > 1, то повторять генерирование до тех пор, пока?? + М < 1. Затем 2 2 2 г Х [Пг 122[ г(Пг + 1~2) 24. [НМ40] (С. Улам (Я. ?йаш) и Дж, фон Нейман.) Пусть ?ге — случайно выбранное действительное число между 0 н 1. Определим последовательность (1г ) с помощью правила 12 чг = 41' (1 — 12 ).
Если произвести вычигление с хорошей точностью, то в результате получится такая же последовательность, как случайная последовательность вш тП, где 12„— равномерно распределенные случайные величины, т е. с функцией рас- 2 и*) = Г'г*г г г.г — е. г 2 а И = яш яс?„, то получим, что??„г.г = (2(?„) гпос(1. Так как почти все действительные числа имеют случайное двоичное представление (см. раздел 3.5), полученная последовательность (? будет равнораспределенной. Однако если вычисление К, выполняется только с ограниченной точностью, то наши аргументы становятся несостоятельными, поскольку будет мешать ошибка округления. [См.
работу фон Неймана СоПессег? Игог)гв б, 7б8-7?О.] Проанализируйте последовательность (1:„), определенную в разделе 3.3.4, когда вычисления производятся только с ограниченной точностью. Выполните эмпирический и теоретический анализ (для различных 1ге). Ьудет ли последовательность иметь распределение, подцбггое ожидаемому? 23.
[М25] Пусть Лг, Хг, ..., Хг — двоичные слова, каждый двоичный разряд которых является независимой случайной величиной, принимающей значение 0 или 1 с вероятностью —. Чему равна вероятность того, что расположение данных двоичных разрядов Лг гг (Хг д (Хг гг (Хг ЛХ2))) содержит 1? Обобщите результат. 26. [М!8] Пусть ггг и Мг — независимые пуассоновские случайные величины со средними дг и дг, где рг > дг > О. Докажите или опровергните следующиеутверждения. '(а) М, + Мг имеет распределение пуассона со средним дг + дг; (ь) мг — 2У2 имеет распределение Пуассона со средним дг — дг. 27. [22] (И. Г.
Арсис.) В большинстве бинарных компьютеров существует эффективный способ подсчета единиц в бинарном слове (см. раздел 7.1). Следовательно, существует хороший путь получения биномиального распределения (2, р), когда р = —, путем генери- 1 рования 2 случайных двоичных разрядов н подсчета числа единиц. Предложите алгоритм, который генерирует случайные числа с биномиальным распределением (С р) для произвольного р, используя в качестве источника случайных чисел только программу для частного случая, когда р = -' [Указание, Моделируйте сначала процесс, который выглядит, как выбор самого старшего двоичного разряда равномерно распределенной случайной величины 1, затем — как выбор второго двоичного разряда этой случайной величины, если старшего двоичного разряда недостаточно, чтобы определить, будет ли случайная величина < р, и т.
д.] 28. [НМВВ] (Р. П. Бреет.) Разработайте метод генерирования случайной точки на поверхности эллипсонда, определенного гледйющим образо»с 2,'а»х„= 1, где а» » а > О. г 29. [М20] (Дж. Д. Вентли (2. Ь. ВепПеу) и Дж. Б. Сакс (2. В. Захе) ) Найдите простой метод генерирования п равномерно распределенных между О и 1 чисел Х»,, Л„, требуя, чтобы они были упорндочены; Х» « Л„.
Алгоритм должен состоять только из 0(п) шагов. 30. (МЯВ] Объясните, как генерировать множество случайных точек (Хг, 1;), таких, что если Н некоторый прямоугольник площадью о, содержащийся в единичной сфере, числа (Х», 1;), лежащие в Н, имеют пуассоновское распределение со средним од.
31. [НМЭ9] (Непосредетоенное генерирование нормальнь»х случайно»х величин.) а) Докажите, что если а, + + алг = 1 и Л»,..., Л» — независимые нормально распределенные случайные величины со средним О и дисперсией 1, то а»Л» + + а»Х»вЂ” нормальные случайные числа со средним О н дисперсией 1. Ь) В доказательстве (а) предполагается, что люжно генерировать новые нормальные случайные величины, используя старые точно так, как получают новые равномерно распределенные случайные величины из старых. Например, можно использовать идею 3.2.2 — (7), но с рекуррентным соотношением, подобным Л = (Л -ы + Х -ле)»»л/2 или Л = лх -л»+ лх — ел, после получения множества нормальных случайных величин Хо,, Х»4.
Объясните, почел»у это нехорошая идея. с) Покажите, тем не менее, что ори»еетеует более быстрый по сравнению с другими метод генерирования нормю»ьных случайных величии, использующий усовершенств»ь ванные идеи (а) и (Ь). [Указан»»е. Если Х и 1' — независимые нпрмальные случайные величины, то такими же будут Х' = Х соей + УэшВ и У' = — Хэшй+ 1'соеВ для любых углов В.] 32. [НМВВ] (К.
С. Уачлес (С. 3. %а!!асе).) Пусть Х и У вЂ” независимые случайные величины с показательным распределением со средним 1. Докажите, что Х' и 1" также являются независимыми случайными величинами, имеющими показательное распределение со среднил» 1» если получить их из Х н У любым из следующих способов. а) Заданаб<Л<1, х' = (! — л)х — л1'+(х+ 1')[(1 — л)х < лу], 1" = х+у — х'. ((2х,1' — х), х <1', Ь) (Х',1") = » ][(2УХ-~), Х>У с) Если Х и 1' имеют двоичное представление Х = (... хлх»хо.х»х гх — з . )л " 1' = (..угу»уо р — »у-гр-з .)г, то Х и У' имеют "перемешанные"' значения Х = (... хгр»хо р-»х гу-з...
)г, У вЂ” ( ° рлх»рох-» р — гх — 3 .. )2. 33. [20] Алгоритмы Р, М, Р и В. генерируют нор»»конные случайные величины, поглощая неизвестное число равномерно распределенных, случайных величин Ь»», Пг, .... Как их можно преобразовать, чтобы на выходе получить функцию только от одной случайной величины Ь'? 3.4.2. Случайные выборки н перемешнвання В многочисленных случаях при обработке данных для беспристрастного выбора, и случайных записей приходится обращаться к файлу, содержащему Х записей. Такая проблема возникает, например, при контроле качества, или других статистических вычислениях, где используются выборки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
