Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 5
Текст из файла (страница 5)
Обозначим через т'. случайную величину: номер опыта, в котором впервые будет извлечено уже записанное число. Т е о р е м а 3. В указанной модели для любого х 0 26 НОЛУЧЕНИЕ СЛУ'!АЙНЫХ ВЕЛИЧИН НА ЭВМ 1ГЛ ! Фиксируем произвольное х)О, и пусть й=/!(ха й/). Тогда Р (/.схр'у)= а а ~э~~~ ( 1)( 2) ( л — 1) и 'Легко видеть, что "~( --')- ('- — "')1= "(--') = л — ! г=-! Так как я<а=-О!)'/У), то л/А!=0!1У Аг)! поэтому 1п~(1 — —,.) ... (! — —,, Я= — — „+О(=), н интересуюшую нас вероятность мгигио записать в форме Л" Р(й С х Гггу) = ~~ е !л//у) (1+0(1/)/А/)].
(9) е=! Рассмотрим теперь разбиение интервала 0<Г<х точнами л '=л/ТА/, где л=1, 2,..., й (рис. 7). и составим интегральную сум— гчз му для функпии Ге пп эгону разсиеиию! — г !2 ~~ е "' Г„(Ä— !„!)+ е х 'тх(х — Г ). л=! Из неравенства х)г А/ — ! <А<х)' !у видно, что /а=а/~ Аг-эх при !г г зт ! Рнс.
7. А/-ь ее. Поэтому последнее слагаемое в этой сумме стремится при А!-~ ее к нулю. и Н ~и~~ — ензх и ц ~~ л/З/ (/ / ) зг-ФФа ! 'е я=! ~ )/е гз/г!/=1 — е ™ а Отсюда н из соотношения (9) следует (8), Теорема доказана. ПСЕВДОСЛУЧАИНЫЕ ЧИСЛА 27 С л е д с т в и е. Так как математическое огкидание неотрицательной случайной величины с функцией распределения 1 — е " ' равно 'гг п)2, то из (8) следует, что при ]у -» со М1, ]г'(я/2) ]у. (10) Рассмотренаая в настоящем пункте модель предложена в статье (731, там же получена формула ()0), а теорема 3 доказана Л.
Й. Большевым и Д. И. Галенко. Несмотря на грубость модели, оценки (8) и (!0) оказались полезными во многих опытах, связанных со способами «перемешивания», когда теоретико-числоваи оценка периода практически невозможна. В качестве й! выбираетсн количество возможных значений функции Ф(х) в конкретной ЭВМ; тогда можно ожядатгь что длина отрезка апериодичности окажется порядка гг(п/2) !У. Например, в методе п. 2.2.3 на ЗВМ «Стрела» значение функции Ф(к) (до нормалпзапии) записывается в форме О, ез, ев ° ..
вм значит, й!=2з«и 8-23 )О'. На практике для ряда подобных алгоритмов были экспериментально обнаружены отрезки апернодичности длиной от 0,8. !О' до 3,5 )О« 3 а меча н не. В книге ()9] параграф, содержащий теорему 3, называется «Критерий проверки периоднчноста последовательности псевдослучайных чисел», Однако по этому «критерию» судить о качестве псевдослучайных чисел нельзя. У некоторых вполне удовлетворительных последовательностей, полученных по формуле (б), длина й гораздо больше.
чем оценка ()0) (фактически С=О(М)). В го же время некоторые последовательности с В =)г(л/2) й!не удовлетворяют ни одному из основных тестов 4 3. 2.4. О более сложных алгоритмах. 2.4.1. Вместо формул вида (4), представляющих собой рекуррентные формулы первого порядка, можно пытаться использовать для получения последовательностей псевдослучайных чисел рекуррентные формулы порядка г Т.. = Ф (Т. Т.-!. " .
т.- +!) (11)' считая, что начальные значения то, Ть ..., Т, ! заданы. Вероятно, длина отрезка апериодичности у такой последовательности при г) 1 гораздо больше, чем при г= 1. Однако теорема, аналогичная теореме 3, даже для случая г=2 не доказана. В ряде работ рассматривались методы вида (11), представляющие собой обобщения методов пп', 2.2.1 н 2.2.2: Т.м=~7[10 "(((1О'"4- Т»-д1 28 получснпе случАиных ВеличиннА эвм )гл. ! И 2 +!=Д(Р+К!) +02~ -!+ - +Д' 7к-.~-!) ° Все же применяются такие методы редко. Наверно ком. пенсация за сложность этих методов по сравненщо с методами вида (4) недостаточна.
2.4.2. Для получения последовательности уо, у!, ... можно одновременно использовать два алгоритма типа (4) с различными функциями Ф(х) и Ч" (х): Ф (у„), если п чь 0 (той М), ул-Ь! = Ч' (у„), если и = — 0 (гпос( М). В счете по методу (!2) почти все время используется формула у„+!=Ф(т ), и только когда п кратно М, последовательность «возмущаетсяа! т„ь! — — Ч'(у„). Поэтому метод этот, предложенный Д. И. )'оленко, назван методом возмущений, а целое число М вЂ” периодом возмущения. Метод возмущений увеличивает длину отрезка аперноднчности по сравнению с методом (4).
Вместо оденки (10) получается оценка (см. упражнение 6 гл. 1) МŠ— )!с(п/2) Л!М. Однако необходимо предостеречь вычислителей от некритического применения этого метода: качество всех используемых псевдослучайных чпсел должно быть проверено. Наблюдались случаи, когда по каждой из формул т.+!=Ф(у„) или у„,!=Чг((„) вычислялись удовлетворительные псевдослучайные числа (с ь'='у' (п)2) !тг), а в реализованном по этим формулам методе (12) числа оказались плохими: не проходил первый тест п. 3.2 (несмотря на то, что Е было близко к )У (л(2) ))гМ).
ЗЛ.З, рассмотрим рекуррснтную формулу г-го порядка г — ! <"„+г = ~ЧР~ евган+А (шо!) 2), (13) а=о где ее=1, а все остальные козффппиенты е! и переменные а. могут ! принимать лишь два значения — О илн 1, Если начальные значения аа, аь ...а !, заданы, то (13) позволяет последовательновычислить сс, с! +!,... Случай аз=а!=...=а ! =О из рассмотрения исключается. Уравнение (13) называется мокоииклическим, если период Р ре. шения ао, а!, ° . „ав... ° равен Р= 3' — 1, пснвдослгчлпнып чмслд Нетрудно доказать, что все решения моноциклического уравнения имеют одну и ту же длину периода Р, и период их совпадаег с отрезном ачериодичностн.
П Р и м е Р. Уравнение ил+4 = ал+ а„+! (шод 2) моноппнлическое Если задать начальные значения и,=1, а,=а»=и»=0, то получим последовательность с периодом !5: 100 010 О!1 010 11! 100 010 если начать со значений ао= а| =аз=аз= 1, то снова получим последовательность с периодом !5 111 !00 О!О 011 010 !11 100 которая лишь сдвигом номеров отличается от предыдущей. Уравнение ал+о = а„ + ал] з + а„+з(опоб 2) не моноциклпческое. Если начать со значений ао= 1, а~=аз=и»=0, то получим последовательность с периодом 7 10001!О 1000!10 а если задать начальные значения ил=а~ =ао а»= 1, то получим последовательность, состоящую из одних единиц.
В статье Н. Б и р л е р а [!85], где исследованы важнейшие свойства уравнений (!3), последозателы»ости, порождаемые моноцинлпческнмп уравнен|ими, называются М-последовательностями. Термин «оюиоциклическое уравнение» введен в [82]. В [178] описаны электронные схемы, реализующие формчлы вида (!3); по этим схемам построены фнэичеснне датчики псевдослучайных двоичных цифр. Ибо решение ам аь ...,ал, ... моноциклических уравнений во многих огношениях ведут себя как двоичные случайные цифры (см. упражнение 7 гл !).
Например, формула ил+ з! = с" + а +з (щоб 2) порождает последовательности с Е=Р=2м — 1. Проверка 600000 цифр, получающихся при начальных значениях (ио, ..., аоо) = (100 !01 100 11! ! !О 00! !01 1!О 1О! 0000), показала, что эти цифры удовлетворяют основным тестам о. 3.2, сформулированным применитель. по к двоичным цифрам (проверка выполнена Ю. Л. Левитаном). Однако если пз цифр а„аь ...
° ал, ... попытаться строить т-разрядные значения случайной вели:ины у Уо —— О, ао ... сг„, о, 7, = О, а,„... аз„, Уо 0 азл ''' азы-1' ''' то пригодность таких чисел, веРоятно, окажется ограниченной; ревультаты работы Р. Таусворта [!72] дают основания оокидать, что эмпирическое распределение групп (То " Чо — !) ' [7» ° " 72» — !) (72» " Узо — !) б ет удет близким к теоретическому тольно при выполнении условии т з~г» 3О получение случАиных Величин нА эвм [Гл.
т ф 3. Статистическая проверка случайных чисел Мы видели, что случайные числа, полученные любым из трех рассмотренных в 5 1 методов, необходимо проверить. Рассмотрим важнейшие критерии, используемые обычно для такой проверки. Все эти критерии необходимы для случайных чисел, но о достаточности критериев можно говорить, только ограничив класс задач, которые предполагается решать с помощью проверяемых случайных чисел. Такая точка зрения будет развита в гл. 7,54. 3.1. Статистические критерии согласия 3.1.1.
Теорема К. Пирсона. Рассмотрим произвольную случайную величину $, которая может быть одномерной или многомерной, дискретной или непрерывной. Обозначим через Х множество возможных значений $. Фиксируем каное-нибудь разбиение множества Х на г ' попарно непересекающихся множеств Х„..., Х, таких, что РЙ~Хт) =рт)0 при 1=1, 2,..., г Очевидно, р~+ ... +р,=РД~Х) =!. Выберем М независимых значений $ь ..., $ величины $ и обозначим через т, количество значений, принадлежащих Х» Легко видеть, что математическое ожидание Мт,=ур,е).
В качестве меры отклонения «истинных» значений н, от «теоретнческих» Ур, удобно выбрать величину (т, — Атр;)а (14), 1-1 ! Теорема. Киковы бы ни были исходная величина ф и разбиение Х=Х1+ ... +Х, (такое, что все р,)0), *) Случайная величина т подчиняется бнномиальному закону ! распределения с Мт,= Ур,- н гзтт — — Л рт (1 — рГ). Сввокупность величин (ть ..., т,) подчиняется мультиномиальному закону распределеввя: при Й,+...+ А, =АГ ''Ч А А — — — А~1, т т стлтнстнческкя пРовегчсх случАЙных чисел 31 при каждом х)О х 1!1гп ХР К ( х) = ~ (г ( ) с( '(15) еде плотность й,„(х), называелгая плотностью распределения уг с пг степе!!ялга свободы, выражается формулой (рпс. 8) /г„,(х) = 12"' Г(пг!2)1 х"'и 'е "". 3.1.2.
Критерий согл а сия )Сз. Теорему преды. дущего пункта часто используют в статистике для проверки гипотез о законе распределения случайной величины. р еаэ у ггггм Ряс. а. Фиксируем достаточно болшпую вероятность р, которую будем называть доверительной вероятностью или коэффиииентол! доверия. Вероятность 1 — р обычно называют уровне,я значилгогти.
Теоретически в качестве р можно выГ>рать любое число ОС~(1, Практически же выбор () означает, что (в рассматриваемой задаче) мы считаем собыгие с вероятностью )р достоверным, а событие с вероягностью (1 — 8 невозможным при единичном и опыта и ни. Пусть теперь имеется конкретная гипотеза о законе распределения случайной величины $. В результате осушествления М независимых экспериментов были получены М значений $г, ..., е этой случайной величины (М достаточно велико). Не противоречат ли эти М значений нашей гипотезе? Чтобы ответить на этот вопрос, можно рассуждать следующим образом. Выберем какое-нибудь число г и зй ПОЛУЧЕННЕ СЛУЧАЙНЫХ ЕЕЛНЧНН НА ЗВМ !ГЛ 1 разбиение множества возможных значений Х случайной величины 5 на г попарно непересекающихся мнохкеств Х=Х1+ ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
