Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 6
Текст из файла (страница 6)
+Х,. Исходя из нашей гипотезы, можно вычислить вероятности р1= Р(5~Х,). Предположим, что разбиение выбрано так, что все р,)0. Тогда по значениям $1, ..., $ нетрудно вычислить величины чь ...,ч, (зтот этап в статистике называют группировкой значений) и по формуле (14) — величину тхн. Если наша гипотеза справедлива, то (при достаточно большом йг) эга величина достаточно хорошо подчиняется закону распределения тх с (г — 1)-й степенью свободы. Из урав- нения Х'1ИГ-,УЛ Рис.
9. можно найти значение тх(г — 1, ! — р), о1вечающее фиксированному нами уровню значимости 1 — р (рнс. 9). Если наше значение Х,'„(2х(г — 1, 1 — р), то этот результат не противоречит нашей гипотезе; если же Х~)~ >ух(г — 1, 1 — Р), то, в со- У у4 алзх ответствии со сделанным л хд — соглашением, это означает, что наступило невозможное событие, и гипотеза должна быть отброшена, так как она привела к противоречию. Конечно, вывод этот У з зависит от выбранной доверительной вероятности и поэтому не носит абсолютного характера. Чаще других используют доверительные вероятности р=0,95; 0,99; 0,999; соответствующие уровни значимости 1 — р=0,05; 0,01; 0,001 называют 5ь/ь-ным, 1 /ь-ным и О,! ь/ь-ным уровнями. Если ухн ~~!1х(г — 1, 1 — р) при р=0,95, то значение у.' называют почти значилгым, при р=0,99 — значимь1м, а при (1=0,999 — вьгсоко значимым (рис.
10). На практике широко используют таблицы распреде- ления )(х (см. стр. 293), в которых приведены значения 9 з! Статистическая проверка оду~явных чисел 33 уз=Ха(лг, Р) — корни уравнения Ш ! )гл (к) г(х = Р, х* (16) 313. Замечания о применении критерия а) О выборе р аз б и ен и я. Если М заранее ограничено, то нельзя выбирать г слишком большим, так как тогда будут малыми величины Фр) и цеустойчивымв значения т!. Обычно рекомендуют выбирать Хг так, чтобы минимальные ЛР) были не меньше чем 20.
б) О больших г. В таблицах Хз число степеней свободы гл обычно ие превосходнг 30, При болыппх значениях малою использовать таблицу интеграла вероятностей (стр. 293), так как распрелеление величины ~=У2кз — )йш близко к нормальному с параметрами (О; 1): Ю Р = ~ й (к) дк —, (1 — бз(з)1, х' где а = )г 2хз — "г'2т. В [5] имеется таблица поправок к последней приближенной формуле.) в) О многократном применении критерия Хз.Соглашение о нсвозмозкности события с вероятностью (1 — Р=Р справедливо для единичного испытания.
Если мы будем повторять наш опыт много раз, то (в среднем) для 100 Ре)е полученных значений Хм соответствующие вероятности окажутся меньше Р (при условии, что гипотеза наша верна). г) В н е к о т о р ы х с л у ч а я х гипотетическое распределение величины содержит неизвестные параметры аь ..., а, и зги параметры оцениваются по результатам тех же Л! испытаний (т. е. по значениям Сь ..., 4), Тогда также можно использовать критерий ам. м. соа где, очевидно, Р=1 — р. Если полученному в эксперие 2 менте значению Хм при п=г — 1 отвечает в таб-,р У йзл Ц =гТ г лице Р(0,001, то это зна- аукл) чепне Хам высоко значи- длл -- — -- — — —— мо.
Например, если при г= !О получено значение Х' =9,4, то по табл!где при девяти степенях сво- йгглл '(йлгллмг! Ьгжг боды находим что Р идг — — злгмлги (жлггллл~злаалмг злплвгг ! ! лглгузля -0,40; следовательно, полученное значение Ххч ДО-, Х!ЛУХ! Х)жгХ! Х гл,дЛХУл пустимо. Рпс. !О. 34 ПОЛУЧЕНИЕ СЛУЧАИНЫХ ВЕЛИЧИН НА ЭВМ !ГГ! ! х» для проверки согласия мюкду значениями бь ..., ЕА, и гипотетическим распределением с подобранными параметрами. Однако предельное распределение следует рассматривать с т=г-з — ! степенями свободы !44). д! О «слншком хороших» значениях Х».
допусти»!, чго сосчитанное значение Хн оказалось столь малым, что соответствую- 2 шее ему значение Р)0,99 В этом случае значения а„..., $, настолько хорошо подчиняются гипотетическому распределению, что... возникает сомнение в нх «случайности». Как мы увидим ниже в гл. 7, для решения некоторых задач важно именно хорошее распределение значений (а не «случайность»), и такие «слишком хорошо» распределенные значения позволяют быстрее решать эти задачи. 3.1.4.
К р и те р и й юя. Рассмотрим одномерную случайную величину В с функцией распределения Р(х). Выберем Л! независимых значений $г,..., 5н этой случайной величины и построим эмпирическую (или выборочную) функцию распределения сд (х) = Ян (х)г7!г', (17) где Я„(х) равно количеству значений, меньших чем х. (На рис. !! 7»'=5). Так как 4~ «д Е ь" «*„чз х г"и (х) — это частота события Д(х) при !»' испытаниях, а вероятность этого события Рд(х)=р(х), то ра (х) сходится по вероятности") к р(х), когда !т'-ь оо.
В качестве меры отклонения Рн(х) от Р(х) часто используют величину «О втй Лг ) [р(х) — Гн(х)] йр(х). '(!8) Т е о р е м а (Р. Мизес, Н. В. Смирнов). Какова бы ни была случайная вели'гана я с непрерывной функцией ') Последовательность случайных величин Чг, ..., ч!н, ... сходятся по вероятности к постоянной с, если при любом Н)0 вероятность Р !)Чи — с(~й) -г-о, когда Д!-»ео. $3! стАт!!стичгскля пРОВВРкл случ1пных чпсвл 35 раснределения Е(х), лри каясдом х)0 11ш Р (!Вй <. х) = а, (х), (19) где ф(гнк!(ия а, (х) от $ не зависит.
На этой теореме основан критерий согласия св', позволяющий проверять гипотезы о функции распределения одномерной непрерывной случайной величины Схема использования этого критерия точно такая же, как схема использования критерия Х': фиксируется доверительная вероятность р; из уравнения а1(ха) =(5 находится соответствующее значение ха (рис. !2; таблица функции а!(х) па стр.
293); по гипотетической функции распределения г" (х) и эмпирической функции распределения г„(х) вычисляется В!й', если величина Св-,у)ХВ, тО Эта ОЗНаЧаЕт, Чта НаСтУПИЛО НЕВОЗМОЖНОЕ событие или, другими словами, наша гипотеза привела е' Ю 1с (в сс -в1л,и!с «!гг А,1ий!л Рис. 12. Рис. 13. к противоречию. Конечно, предполагается, что количество значений 1!! достаточно велико. По сравнению с критерием )1з критерий В!' имеет одно преимущество: це нужна группировка значений (и, стало быть, не надо вводить параметр г). Применять критерий можно обычно уже при М)50.
Однако, чтобы вычислить свз, нужно расположить значения $1, ..., $и в порядке возрастания: $!и ~~$!а! ~~ ° ~ ~В1ин 8Ф 36 ПОЛУЧЕННЕ СЛУЧАПНЫХ ВГЛ1ПН1Н НА ЗВМ 1ГЛ. 1 (Такой ряд выборочных значений называется в стаснстнке варпационным рлдол1). Если количество значений (т. е. 1у) превышаетобъем внутреннего накопителя ЭВМ, то расположение их в порядке возрастания представляет собой весьма трудоемкую процедуру. Из-за этого прп очень больших й( критерий щя используют редко.
Выведем теперь.формулу для расчетным. Во-первык, нетрудно 2 проверить, что ЕФ(л) = Ауй! прн 5,1о < л < е„,+11, где А=О, 1, ..., 1У, и условно ь(е1= — ю,$<м+Н=от(рнс. !3). Далее условимся для краткости писать ее вместо е(3 21) тогда на (!8) следует, что 2 м 312-1- Н вЂ” ( Е (х) — у~ с(Е (л) = А=О т(гн Г! 3 3 й 2 2 йа = ~' '( з (Еае! ЕА) А (Е1ы ! — ЕА) +)Уа(ЕАа1 ЕА)1= а=о С1мма первых двух квадратных скобок легко вычисляется.
Послед. яне члены дополним до пот!ого квадрюа: Перле несложных вычислений получим окончательную формулу, ко- торую удобно записать в следующем виде: (20) 2=-1 $31 стлтистическля ПРОВеРкл слу'!л!4!4ых 'и!сел 37 « О,=Р!. +Ч.з, 4=о о ч;. = хз у!л 4=3 Смысл этих величин очевиден: чь — коли зество цифр, 3.2.
Проверка таблиц случайных цифр. Для проверки таблицы случайных цифр е!, 32, ..., е„М. Г. Кендалл и Б. Б. Смит предложили использовать четыре теста. В каждом из них цифры классифицируются по некоторому признаку и эмпирические частоты сравниваются с их математическими ожиданиями при помощи критерия Хз. Тесты эти: проверка частот ((ге!)попсу (ез!) — проверяется частота различных цифр в таблпне; 2) проверка пар (зег(а! (ез!) — проверяется частота различных двузначных чисел среди пар е! еь 32 ез, ез е4..., е„! е; 3) проверка интервалов (дар (ез!)— проверяется частота различных и!первалов между двумя последовательными нулями; 4) проверка комбинаций (ро!Лег !ез!) — проверяется частота различных типов четверок (аЬса', ааЬс, ааЬЬ, аааЬ, аааа) среди чет- ВЕРОК Е!Е2ЕЗЕ4 Е2ЕЗЕзвз Большинство последузощнх авторов также испольэовали эту систему тестов, внося, однако, в нее некоторые изменения, среди которых отметим два.
Вместо проверки интервалов обычно используют проверку серий (тип (ез!): цифры е,+и е,«2, ..., е„, образуют серн!о длины С если ез„!=.аз+2= ... =ез ь но езде„+!, ел4.,+!Фел+!. Вместо проверки пар е!32, 3233, езе4, ... преверяют независимые парь! е!ем 3334, езем ° С. детерминистической точки зрения (она изложена в гл. 7) проверка частот и проверка независимых пар-- важнейшие необходимые тесты, Проверка серий обобщает «критерззй случайности», часто используемый в статистике [24).
И только проверка комбинаций носит несколько искусственный характер. Поэтому можно рекомендовать в качестве основных использовагь следующие два теста. Первы й тест (провеока ь стог и пар), Предположим, что количество цифр М=2М' четное. Цифры е!,... ..., 3» Разобьем на паРы е!еь езе4, ..., ен-43«, Обозначим через чв количество пар 4/. Сосчитав матрицу ,(чи), 0(!', )(9, легко вычислить также величины ПОЛУЧГН!!Е СЛУЧЛПНЫХ ВЕЛНЧ!!Н НЛ ЭВМ 1ГЛ ! РаВНЫХ 1, СРЕДИ ЦИФР а!, ЕЗ, ЕМ ..., Еи !1 Уи — КОЛНЧЕ- ство цифр, равных т, среди цифр ез, еь ..., е;; у — общее количество цифр, равных !'.