AOP_Tom2 (1021737), страница 178
Текст из файла (страница 178)
17. (а) Е(х) = 1 — (1 — р)-'*1 для х > О. (Ь) С(х) = рх/(1 — (1 — р)х). (с) Среднее равно 1/р, среднеквадратичное отклонение равна ьгТ- р/р. Для дальнейших вычислений заметим, что если Н(х) = д+(1 — д)ц то Н'(1) = 1 — д и Н" (1)+Н'(1) — (Н'(1)) = д(1 — д), поэтому среднее и дисперсия 1/Н(х) равны д — 1 и д(д-1) соответственно (см. раздел 1.2.10). В этом случае д = 1/р, дополнительный множитель х в знаменателе С(х) добавляет к греднему 1. 16.
Присвоить Н е- № + № — 1, где № и Нз — независимые случайные величины, имеющие геометрическое распределение с параметром р. (Рассмотрите производящую функцию.) 19. Присвоить Ю е- № +. + № — В где Н (независимые. — Прим. ред.) — случайные величины, имеющие геометрическое распределение с параметром р. (Это число неудач перед 1-м успехом, когда осуществляется последовательность независимых испытаний, каждое из которых приводит к успеху с вероятностью р.) Для 1 = р = з и вообще, когда среднее значение (т. е.
«(1 — р)/р) распределения мало, можно упростить вычисление вероятностей р„= ( „")р'(1 — р)" последовательно для и = О, 1, 2,..., как показано в следующем алгоритме. В1. [Инициализация.[ Присвоить РЗ с — О, д е- р', г е- д и генерировать равномерно распределенную случайную величину (у. (Будет выполняться д = рл и т =. ре + + рл на протяжении вота алгоритма, выполнение которого остановится, как тачько получим У < г.) В2.
[Итерация.[ Если Н > г, присвоить У с — Н+ 1, д е — д(1 — р)(1 — 1 Ч-Н)/№ г +- г Ч-д и повторить этот шаг. Иначе — возврат Н и конев. ] [Интересный метод для отрицательного биномиального распределения с произвольно большим действительным значением 1 предложил Р. Леже (В. Ьебег). Сначала нужно генерировать случайную величину Х, имеющую гамма-распределение порядка ц а затем положить Х равной случайной величине с пуассоновским распределением со средним, равным Х(1 — р)/р.) 20. В1 = 1-г(1 — А/Л) В1. Когда выполнен шаг В2, алгоритм завершается с вероятностью 1/Л; когда выполнен шаг ВЗ, переход к шагу В1 происходит с вероятностью Е/Л. Справедливо следующее. В1 Л/А Л/А Л/А Л/А В2 0 Л/А О Л/А ВЗ 0 0 Л/А Л/А — 1/А В4 Л/А Л/А — //А Л/А — Е/А Л/А — 1/А — Е/А 21.
1! =;/О/е — 1.71553! А = ьlя/2 - 1.25331. Так как и4/аа — Ьи 4)и = (а — 614)41~ (г(а — Ьи) — 2)/Ьг, ПОЛУЧИМ 1 = /О"1 и~/а — Ьи4!и =,4 а~1~/6~, Гдэ а = 4(1+ !ПС) И 6 ы 4С. КОГда С = Е414, 1 принимает максимальное значение э 4/5/е 1.13020. Наконец, чтобы вычислить Е, понадобятся следующие формулы для интегрирования: /4/Ьи-аииг 4!и= -'6 а ~г~ шсэш(2иа/6-1)+ -'Ьа 'Ли-аиг (2иа/6-1), 14/ьи+аид4)и= — гь а ~~~ !в(446и+аии~+ит/о+ь/24/а)+ 4ьа 11/ьи!-аи'(2иа/ь 1-1), где а, Ь > О.
Пусть на шаге В3 выполняется проверка "Х > 4е' '/С вЂ” 4х", тогда внешняя область попадет в верхнюю часть прямоугольника, когда и = г(х) = (е' — 4/ег* — 2ех)/2ех. (г(х) случайно принимает максимальное значение в точке х = 1/2, в которой г(х) ие дифференцируема!) Справедливо Е = /е ~*~(ь/2/е — 1/Ьи — аиг) 4(и, где Ь = 4е* ' и а = 4х. Е принимает максимальное значение возле точки х = —.35, где оно приближенно равно Е щ .29410. 22. (Решение Дж.
Марсалья (С. Магэаб!!а).) Рассмотрим "непрерывное пуассоновское распределение", определенное следующим образом. С(х) = / е '1* ' а41/Г(х) для х > О. Если Х имеет это распределение, то и (Х) имеет пуассоновское распределение, так как С(х+ 1) — С(х) = с "р*/х!. Если р большое, С приближенно нормально. Следовательно, С' 1!(Ее(х)) приближенно линейно, когда Р„(х) — функция распределения нормальной случайной величины со средним и дисперсией, равными р, т. е. Ре(х) = е((х — р)/4/р), где Е(х) — функция нормального распределения (10).
Пусть д(х) — реально вычисляемая функция, такая, что !с! 1! (Р„(х)) -д(х)) < е для -оо < х < оо. сейчас можно эффективно генерировать пуассоновскую случайную величину следующим образом: генерировать нормальную случайную величину Х и присвоить 1г 4 — д(р -!- 4/рХ), Аг 4- (у), М 4— (1' + 1). Затем, если )У вЂ” М) > е, получаем на выходе Л', иначе на выходе будет М вЂ” (С! '!(Е(Х))<М). Этот подход применим также к биномиальному распределению с г1 С(х) /" „*- (1 и)--*„и Г('+ 1) /, Г(х) Г(! + ! — х) ' поскольку (С! 0(Гг)) — величина, имеющая биномиальное распределение с параметрами (г,р) и С приближенно нормально.
(См. также альтернативный метод, предложенный Аренсом и Дитером (АЬгепэ эп4! Р!егег, Сошри!!лд 25 (1980), 193 — 203).) 23. Да. Второй метод дает распределение )сов 2д), где д — равномерно распределенная случайная величина между 0 и я/2. (Предполагается, что (7 = г соя д, Р = гойи д.) 25. 1г = (.10101)г Обычно двоичное представление формируется с использованием 1 для (4 и 0 — для л слева направо, затем прибавляется 1. Этот метод [см. (Точер К. Д.) К. Р.
Тосйег, 1. Еоу. Я!аи Бог. В16 (1954), 49) может привести к эффективному генерированию независимых двоичных разрядов с заданной вероятностью р, а также использоваться при генерированни случайных величин с геометрическим и биномиальным распределением. 26. (а) Верно: 2 Рг(141 = Ь) Рг(дгг = и — Ь) = е "' "(р1 + рг) "/и!. (!г) Неверно, поскольку, если рг ф О, № — № может быть отрицательным. 27. Пусть двоичное представление р имеет вид (.ЬгЬгЬз... )г. Поступилг далее в соответ- ствии со следующими правилами.
В1. (Инициализация,) Присвоить т г- 1, !г' +- О, / г- 1. (В этом алгоритме т обозначает количество моделируемых равномерно распределенных величин., для которых соотношение с р еще неизвестно, так как их старшие / — 1-двоичные разряды совпадают с этими же разрядами числа р, А' — число моделируемых случайных величин, о которых известно, что они меньше р.) В2. [Взгляд иа следующий столбец двоичных разрядов.] Генерировать случайное целое число М с биномиальным распределением (т, — '). (Сейчас М означает число неизвестных случайных величин, таких, что их /-й разряд не совпадает с 6,.) Присвоить т з- т — М, если 6, = 1, то присвоить !г'+- Аг+ ЛХ. В8. (Сделаноу) Если т = 0 или если остающиеся двоичные разряды (.6г+г6гтг )г р все равны нулю, алгоритм завершен.
Иначе — присвоить / г — /+ 1 н возвратиться к шагу В2. 1 (Когда Ьг = 1 для бесконечного числа /ь среднее число итераций Аг удовлетворяет равенствам 1 lпз А =1+ — ~ ~ )Аз дляп>1. Ь/ Ао = 0; Положив А(г) = ~" А г"/пЬ получим А(з) = е* — 1 + А(-'г)еьш Поэтому А(г)е 1 — е '+ А(-'г)е *7~ = 2, > (1 — е ьш ) = 1 — е * — ) „>г(-г) "/(п!(2" — 1)) и А, =1-ь~ ~ ) =1+ — =18п+ — + — +/о(п)+0(п ) у их (-1)зег !'" +г З 1 -1 з>1 Ь/ 2'-1 в обозначениях упр.
5.2.2-48.) 28. Генерируем случайную точку (рп...,9„) на единичной сфере и предположим, что Р = Ч 2 аз Уы Генерируем независимую равномерно распределенную случайную величину l г (/ если р"+'1/ < кт/2,азрз, то на выходе получится точка (ьч/р,..., у„/р); в остальных случаях начинаем сначала.
Здесь К = ш!п((2,'азу>) /(х озрз) ) 2 Уз = 11 = а если па„> ам ((л+ 1)/(аг -!- а„)) (ага„/п)" — в остальных случаях 29. Предположим, что Х гю = 1, затем присвоим Х» +- Х„„,(гз или Хь +- Хзеге гы — узы для Й = п, и — 1,, 1, где Пз — равномерно раснределениая случайная величина или г'з — случайная величина с показательным распределением. (АСЛ4 Тгалз. Мазй. Яойи'аге 6 (1980), 359 — 864. Этот метод введен в употребление в 60-х годах Давидом Сенешолом (Наг!с( Бепеэсйо!); см работу Ашег.
Ясаггэбг!ао 26.,4 (ОсгоЬег, 1972), 56-57. Альтернатива состоит в геверировалии и равномерно распределенных случайных чисел и их сортировке наиболее быстрым методом. Предложенный здесь метод является особенно полезным, если только требуется несколько наибольших или наименьших Х,. Заметим, что (Е! ~!(Хг),...,Е! '!(Хв)) соответствуют упорядоченным случайным величинам с функцией распредедения Е.) 30. Генерировать случайные числа Яг = -р ' !а(/г, Яг = Яг — р г !пУг, ...
до тех пор, пока не выполиится Е ьг > 1. На выходе получим (Х„,Гг) = /(Я,) для 1 < / < т, где /((ЬгЬг . Ьгг)г) = ((616г... 6)г, (Ь +гЬ+г... Ьг)г). Если менее старшие двоичные разряды значительна менее случайны, чем более старший двоичный разряд, то надежнее (но медленнее) положить, что /(( ЬгЬг Ьы)г) = ((Ьгбз...
Ьгг-г)г,( Ьг64 Ьг.)г). 31. (а) Достаточно рассмотреть случай, когда)с = 2, так как атЛт+ +алХ6 = Хсову+ УвшВ при Х = Хтт сову = а! и У = (агХг Ч- +алХ6)/вшВ. И справедливо равенство Рг(ХсовВ+УсйпВ < х) = — ) е ' ) ! )~йзйг[всовВ+звшВ<х) 2н /с,т — е ")~ ")~йийи[и< х) = (10) 2н,)„„ после подстановки и = зсовВ+1вшВ, е = -звшВ+1совВ. (Ь) Существуют числа а > 1 и В > 1, такие, что (а го + а зз)/л/2 = 1 н 6,9 гз + 6 -Ы 8)Б = 1, поскольку числа Х растут зкспоненциально по п согласно свойствам линейных рекуррентных соотношений, Если отказаться от формы линейного рекуррентного соотношения, скажем, используя рекуррентное соотношение Хс = Ло-госовВ + Л ззв)пВ„, где В выбрано равномерно в [О .. 2н), можно получить подходящий результат, но потребуется выполнить намного больше вычислений.
(с) Начните, пожалуй, с 2 048 нормальных случайных вевичин Хо,, Хтогз, )то, ..., 1;огз. После использования около 1/3 из них генерируйте еще 2 048 случайных величин следующим образом. Выберите целые числа а, Ь, с и й независимо в [О, . 1024), причем а и с должны быть нечетными. Затем присвойте т «т 6 «!о!Ел)отой)064с™В ) ))!с!+В) сод!Огзз)ПВ 6- — Х!«т+6) моа !его ВШ В + 1 <с,+В) мое лего СОВ В для 0 < й < 1024, где сов В и вш — случайные отношения (Ь)~ — «т~)/(Ы~ + Ъ'г) и 21)«'/((/~ + ~'), выбранные, как в упр.
23. Можно отбросить Ы и )т, кроме случаен, когда [сов В[ > -' и [в!и В[ > -'. 2 048 новых случайных величин заменят старые. Залтетим, что для получения новой случайной величины необходимо выполнить лишь несколько операций. Этот метод не расходится подобно последовательностям, содержащимся в (Ь), так как сумма квадратов 2 (.«г + 1'„г) = 2 ((Х„') Ч- (1'„') ) остается постоянной со значением Б — 2048.
исключая незначительную ошибку округления. С другой стороны, постоянство Б на самом деле является недостатком метода, поскольку сумма квадратов действительно должна иметь Хг-распределение с 2 048 степенями свободы. Чтобы преодолеть возникшую проблелту, следовало бы использовать не нормальные случайные величины Л;, а аЛ„где аг = )(Утогз + л/4095)~/Б является заранее вычисленным нормирующим множителем. (Величина 5(У)огз + )/4095)г будет приемлемо приближать требуемую Х~ случайную величину.) Литператпуухл С.
Я. %а11асе, АСМ 2гапв. оп МазЛ. Бойе.ате 22 (199б), 119 — 127; Н. Р. Вгепс, Лес!иге г«тозев ш Сашр. Бс!. 1470 (1998), 1-20. 32. (а) Преобразование (Х', )с') = /(Х, У) является взаимно однозначным соответствием преобразованию множества (х, у > О) самого в себя, такого, что х'+ у' = х+ у и йх' йу' = йх йу. Получим Х' Х , = ( — — Л) шой 1... = ( — + Л) пюй1. У' У (Ь) Эта ПрЕОбраЗОВаНИЕ яВЛяЕтСя таКИМ СаатВЕтетВИЕМ (гатО-ЗО-ОПЕ) От дВуХ К ОдНОМу, что х'+ у' = х+ у и йх'йу' = 2йхйу. (с) Достаточно рассмотреть "/-транспонированноес преобразование Х = (...хтегх,о)х,у) ту,-гут-з )г, ( ' ' ут+гут+ту)х) — !к! гхт з ' ' )з для фиксированных целых / и затем составить 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}
