Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 43
Текст из файла (страница 43)
Чему аючна равна вероятность того, что [Щ = г, если О < г < й? Сравните с требуемой вероятностью 1/к. 3. [14 [ Как можно рассмотреть (1 в качестве целого числа и разделишь его ца к, чтобы получить случайное целое число между О и к -1, вместо того чтобы выполнять умножение, как предлохсено в разделе. Тогда (1) было бы заменено на Ей?А О; ьОХ О; И'э' Х с результатом в регистре Х. Хороший лн зто метод? 4.
[МФО) Докажите два соотношения в (8). б. [31[ Предложите эффективный метод генерирования случайной величины с функцией распределения Р(х) = рх+ дх~ + гхэ (О < х < 1. — Прим. ред.), где р > О, о > О, г > О яр+4+с=1. 6. [ВМ31[ Величина Л получена следующим образом. Шаг 1.
Генерировать две независимые равномерно распределенные случайные величины С и У. Шаг 2. Если С~ + 1'э > 1, возврат к шагу 1; иначе — присвоить Х э- С. Какова функция распределения Л? Сколько времени выполняется шаг 1? (Найдите среднее и среднеквадратичное отклонения). 7. [3О) (А. Дж. Уолкер (А, 1. 'этаИив),) Предположим, что имеется набор кубиков к различных цветов, скажем и кубиков цвета С, при 1 < 1 < к, и к коробок (В~,...,Вь), в калслую из которых можно поместить п кубиков. Кроме того, п~ + + нэ = кп, так что кубики булут полностью заполнять коробки. Докажите (конструктивно), чта всегда можно разместить кубики в коробках так, чтобы в каждой из них содержались кубики самое большее двух различных цветов.
Действительно, можно устроить так, чтобы всякий раз в коробке Ву содержалось два цвета, один из которых — цвет С;. Покажите, как использовать зто утверждение, чтобы подсчитать Р и У, требуемые в (3), при заданном вероятностном распределении (рм ...,рь). 8. [М15] Покажите, что операцию (3) можно заменить операцией если С < Рк, то Х э- хк~ М иначе Х +- Кк. (Таким образом, вместо 1' используется истинное значение (1.) Будет ли зто более удобным нли подходящим для изменения Ра, Рм ..., Рэ-э. 9. [НМ10) Почему кривая 7(х) на рис.
9 выпукла для Выпуклая кривая Вогнутая кривая х < 1 и вогнута для х > 1? ь 10. [НМ24[ Объясните, как вычислить вспомогательные постоянные 1', 131, У;., 3„31, В„, Вэ, чтобы алгоритм М давал ответ с правильным распраделением. ь 11. [НМ27) Докажите, что шаги уб? и М8 алгоритма М порождают случайную величину с хвостом, бдиэким к нормальному распределению, т. е.
вероятность того, что Х < х должна быть точно равна [Указание. Покажите, что зто частный случай метода отбраковки с д(1) = СГе ~~ для -сНэ некоторого С.) 12. [НМЙЯ] (Р. П. Брент (В.. Р. Вгепг).) Докажите, что числа а„определенные в (23), удовлетворяют соотношению о, — а,, < 2)п 2 для всех г' > 1. [укоэание. Если 7(э) =е*?э)' е '?эгей, покажите, что /(х) < 7(д) для О < к < у] 13. [НМЯо) Дано множество и независимых нормальных случайных велпчин Хм Лэ, Х„со средним 0 и дисперсией 1. Покажите, как найти константы Ь, н аи, 1 < 2 < 1 < и, такие, что если У~ =Ь! +амХм Ур = Ьэ+адХ~+аээХэ, ..., Уе = 6 +аыХ~+ ° +а Х„, то Уп уэ, ..., ӄ— зависимые нормально распределенные случайные величины, 1'1 имеют среднее 80 и заданную ковариацнонную матряпу (сб).
(Ковариацин су межлу У< н У? определяются как среднее значение случайной величины (У; — д,)(У1 — д„). В частности, СН вЂ” ЭтО ДИСПЕРСИЯ Уэ, КВаДРат ЦХ СРЕДНЕКВаЛРатНЧНЫХ ОтКЛОНЕНнй. НЕ ВСЕ МатРИЦЫ (сц) могут быть ковариацноннымн, н ваше построение, конечно, будет работать всякий раз, когда данное условие будет выполняться.) 14. [М81] Найдите распределение сЛ, если Х вЂ” случайная величина с непрерывной функцией распределения Р(х) и если с — постоянная (возможно, отрицательная). 18. [НМ21) Если Х~ и Лэ — независимые случайные вели пгиы с совтветствующими функциями распределения Г~(э) и Гт(к) и плотностями ~~(х) = Е~(к), уг(х) = Гэ(х), какова функция распределения и плотность случайной величины Х~ + Хэ? ь 10.
[НМ22] (И. Г. Аренс.) Предложите алгоритм для генерирования случайной величины, имеющей гамма-распределение порядка о, когда 0 < а < 1, с помощью метода отбраковки с сд(4) = Г' '/Г(а) для 0 < 1 < 1 н с сд(1) же "/Г(а) для э > 1. ь 17. [М24] Чему равна функция распределения Р(э) случайной величины, имеющей геометрическое распределение с параметром р? Чему равна производящая 4рнкчил 6(э)? Чему равны среднее н дисперсия этого распределения? 18. [М24) Предложите метод вычисления случайной целочисленной величины Ю, такой, что Н принимает значение и с вероятностью прэ(1-р)" ', и > О.
(Когда р сравнительно малб, этот случай представляет особый интерес.) 19. [88) Случайная величина Н с ошрциашельнмж биножпальнмж распредаеением с параметрами (1 р) принимает значения?э' = и с вероятностью (' '„™)р (1-р)", (В отличие от обмчного биномиального распределения 1 не обязано быть целым, так как эта величина неотрицательна для всех и, каково бы ни было С > О.) Обобщая упр. 18, объясните как генерировать целые случайные числа ?д с этим распределением, когда Э вЂ” малое положительное целое число. Какой вы предложите метод для г = р = 1э? 20. [Мдд] Пусть А — площадь заштрихованной области на рис. 13, Н вЂ” площадь содержащего ее прямоутольннка, 1 — площадь внутренней области, определенной на шаге В2, и Н вЂ” площадь между внутренней областью, отбрасываемой на шаге ВЗ, и другой частью прямоугольника.
Определите длительность каждого шага алгоритма К для кажлого нз четырех варкантов в (25) в терминах А, Я,? и Е. 21. [??Мйз[ Найдите формулы для величин А, Н, 7 н Е, определенных в упр. 20. (Для 1 н особенно для Е можно нгпользовать интерактивную алгебраическую систему.) Покажите, что с = е? — наилучшая возможная постоянная иа шаге В2 для проверки "Х < иэ 2 4(1 +!и с) — 4с(!'. 22. [??М40[ Можно ли получить точное пуассоновское распределение для больших д. гене. рируя приближенно нормально распределенную величину, превращая ее в целочисленную некоторым полходяшим гпособом и применяя (возможно, сложную) коррекцию в небольшом числе случаен? 23.
[НМ33[ (Дж. фон Нейман.) Будут ли следую~пнедва способа генерирования случайной величины Х эквивалентны (т. е. будут ли случайные величины Х при этом одинаково распределены)? Метод 1. Присвоить Л +- »1п((л/2)(/), где (/ — равномерно распределенная случайная величина. Метод 2. Генерировать две равномерно распределенные случайные величины (! н $', если Пз + 1'з > 1, то повторять генерирование до тех пор, пока (/~ + Уз < 1. Затем присвоить Х +- [(! — Р'з[/(П + У ).
24. [НМ40) (С. Улан (Я. Гйапз) и Дж. фон Нейман.) Пусть 1» — глучайно выбранное действительное число между 0 н 1. Определим последовательность (1 ) с помощью правила T„~~ = 4К,(1 — 1~ ). Если произвести вычисление с хорошей точностью, то в результате получится такая же последовательность, как случайная последовательность гйп к(?„, где К, — равномерно распределенные случайные величины, т. е. с функцией рас- Р " .Р ~К(*)=!ь/ли» 7~ Е К, = ябпз и(?ь, то получим, что (/ +~ = (2П ) шоб 1. Гак как почти все действительные числа имеют случайное двоичное представление (см, раздел 3.5), полученная последовательность П будет равнораспределенной.
Однако если вычисление К, выполняется только с ограниченной точностью, то наши аргументы становятся несостоятельными, поскольку будет мешать ошибка округления. [См. работу фон Неймана Со!!ессеях 1тогй» б, ?б8-770.) Проанализируйте последовательность ($!„), определенную в разделе 3,3.4, когда вычисления производят~я только с ограниченной точностью. Выполните эмпирический и теоретический анализ (для различных Уе).
Будет ли последовательность иметь распределение, подобное ожидаемому? 28. [Мйб) Пусть Лм Хз, ..., Хь — двоичные слова, каждый двоичный разряд которых является независимой случайной величиной, принимающей значение 0 или 1 с вероятностью -'. Чему равна вероятность того, что расположение данных двоичных разрядов Л~ 1! (Лз д (Хз У (Х» д Л»))) содержит 1? Обобщите результат. 26. [М1 8[ Пусть № и Мз — независимые пувссоновские случайные величины со средними д~ и рз, где р~ > дз > О.
Докажите или опровергните следующиеутверждения: (а) № + Из имеет распределение Пуассона со средним д~ + ды (Ь) № — Жз имеет распределение Пуассона со средним д~ — дз. 27. [22[ (И. Г. Арене.) В болыпинстве бинарных компьютеров существует эффективный способ подсчета единиц в бинарном слове (см. раздел 7.1). Следовательно, суьчествует хороший путь получения биномивльного распределения (1, р), когда р = -', путем генерирования 1 случайных двоичных разрядов и подсчета числа единиц. Предложите алгоритм, который генерирует случайные числа с бнномиальным распределением (Ср) для произ»ельм»го р, используя в качестве источника случайных чисел только программу для частного случая, когда р = 1. [Указание. Моделируйте сначала процесс, который вьллялит, как выбор самого старшего двоичного разряда равномерно распределенной случайной величины 2, затем — как выбор второго двоичного разряда этой случайной величины, если старшего двоичного разряда недостаточно, чтобы определить, будет лн случайная величина < р, и 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
