Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 20
Текст из файла (страница 20)
Но время между действительным испвльзвваннем величин в специальных сумматорах с помощью сопутствующих программ было достаточно большим н постоянно менялось. Позтому на самом деле множитель был равен 23" для достаточно больших, но меняющиеся значений lс.) С. История, библиография и теория. !Гт-критерий был предложен Карлом Пирсонам (Реагзоп) в 1900 году (РИ!оворЫса! Малая!ле, Яейез 5, $0, 157-175).
Его замечательная работа рассматривается как фундамент современной математнческой статистики. Предшественники Пирсона просто строили графики зкспернментальных результатов и утверждали, что онн правильны. В своей статье Пирсон привел несколько интересных примеров злоупотреблений статистикой.
Он также доказал, что некоторь1е результаты наблюдений за рулеткой (на которой он проводил зкспернменты в течение двух недель в Монте-Карло в 1892 году) были так далеки от ожидаемых частот, что шансы получить их снова при предположения, что рулетка устроена добросовестно, равны одному нз 10зз! Общее обсуждение Хз-критерия н обширную библиогрг4~ню можно найти в обзорной работе Вильяма Дж. Кокрена (»»я!))!шй С. СосЬгап, АппаЬ Маг)ь йаг.
23 (1952), 315-345). Рассмотрим вкратце теорию, лежащую в основе Хг-критерия. Легко увидеть, что точные вероятности того, что У, = уы..., У» = р», равны и! руя ргя »" » Кслн предгюложить, что У, принимает значение ря с вероятностью Пуассона е "ю(пр„)г' н что Уя- независимы, то (1'„..., У») будет равен (рм ., ., у») с вероятностью с- э.(„р )г. яя.
П ! и У» + + У» будет равно и с вероятностью Е у,! и! »я+" +гя=яя я=1 г,-,г» >о Жслн предпояюжнть, что онн независимы, кроме того, что выполняется условие У~+. "+1» = и (т. е. У„..., У»» независимы, а У» выражается через УП...,1'» с помощью зтого равенства. — Прцм. ред,), вероятность, что (Уы..., У») = (у»,..., 9»), равна отношению которое, в свою очередь, равно (17). По»тому можно рассматривать У,„в = 1, ..., Й вЂ” 1 как независимые случайные величины, имеюшие распределение Пуассона н тиаре, что 2, 'У, = и.
я»о Теперь удобно сделать замену переменных, У, — цр, (18) по»таму У = Я»г+ + Я»г. Условие У, + + У» = и зквивалентно требованию (19) /р1 2» + " +»/р» 7» = О. Рассмотрим теперь (й — 1)-мерное пространство 3 векторов (Я»,..., Я»), таких, что выполняется (19). Для больших значений п каждое 2, имеет приближенно нормальное распределение (сн.
упр. 1.2.10-15). Позтому вероятность попасть в диФФеренциальный объем я!г»... я1г» области Я приблигясенно пропорцнональна величине ехр (-(г~ + + г»г)/2). (Именно из-за етого Хг-критерий можно использо- Пусть Ъ' = пГ(Лу) для 1 < у < и, где Х„должны быть рассортированы, как на шаге 2 перед формулой (13). Поэтому случайные величины У' независимы и имеют одно и то же распределение, а именно — равномерное распределение между О и и.
Они рассортированы в порядке неубывания У1 < Ъ~ < " < У„, и первое равенство в (13) может быть преобразовано следующим образом: 1 Ке = — шах(1 — Ум 2 — Уе, ..., и — У„). ~/и Р.(к„в — ) - — „т' (")о-е'е+.-е -'-' (25) — ч ~' (")(й- )'(г+ -й)"-"-' па ~51 с<а<а Распределение К„точно такое же.
Равенство (26) впервые получено Н. В. Смирновым [Успехи мат. наук 10 (1944), 176-206) (см. также работу 3. В. Бнрнбаума и Фреда Х. Тинги (Е. Ж. В!гпЬашп апб Бед Н, Тшйеу, Аппп)в Маей. Бваа 22 (1951), 592-596)). Смирнов вывел также асимптотическую формулу Рг(К+ < в) = 1- е з' (1 — -в/ь/й+ 0(1/и)) (27) для всех фиксированных в > О, что привело к получению приближенных значений для больших и, которые приведены-в табл. 2, Биномиальная теорема Абеля, равенство 1.2.6-(16), показывает, что равенства (25) и (26) эквивалентны. Можно расширить табл.
2, используя ту либо другую формулу. Существует интересный компромисс: хотя сумма в (25) имеет лишь около вт/й членов, когда в = $/т/й, она должна вычисляться с помощью арифметики с многократной точностью, поскольку члены большие и их главные цифры сокрапшются. Но такая проблема не возникает в (26)„так как члены этой формулы положителькы, но (26) имеет и — в,/й членов. УПРАЖНЕНИЯ 1. [00) Какую строку хв-таблицы следовало бы использовать, чтобы проверить, будет ля величина $' = 7 ~и формулы (5) невероятно болыпойт Если О < г < и, вероятность, что К„' < Г/~/и, равна, следовательно, вероятности того, что Уу > у — г для всех 1 < у < и, Это легко выразить в терминах и-мерных интегралов: )а по)а, 1 ря г '''/о1 г101 где а = шах(т' — г, 0).
(24) Знаменатель здесь вычисляется моментально; он равен и "/пб Это выражение имеет смысл, так как гиперкуб всех векторов (ум уз,..., ря), таких, что 0 < ру < и, имеет объем и" и может быть разделен на п1 равных частей, каждая из которых соответствует одному из возможных способов упорядочения рь Найти интеграл, стоящий в числителе, немного труднее. Но его можно вычислить методом, предложенным в упр.
17, и получить общую формулу: 2. [80] Пусть две игральные кости "устроены" так, что на одной нз них 1 будет выпадать вдвое чаще, чем любое другое значение, а на другой 6 будет выпадать вдвое чащее, чем любое другое значение. Найдите вероятность р, того, что сумма показаний на двух игральных костях равна точно з, 2 < з < 12, 3. [83] Игральные кости устроены так, как описано в предыдущем упражнении, Они были брошены 144 раза, н получилясь следующие значения, Значеннез= 2 3 4 5 6 7 8 9 10 П 12 Число наблюдений г', = 2 6 10 16 18 32 20 13 16 9 2 Примените к~-критерий к этим значениям, используя вероятности из (1) и считая, что игральные кости на самом деле не поддельные.
Определит ли дз-критерий, что кости плохие? Если нет, объясните, почему. 4. [83] На самом деле автор получил данные эксперимента 1 нз (9), моделируя игральные кости, одна нз которых была нормальна, а другая всегда давала только значения 1 или 6. (Причем обозначения появлялись с равными вероятиостямя.) Подсчитайте вероятности, которыми можно заменить (1) в этом случае, и, используя у -критерий, решите, соответ- 2 ствуют ли результаты эксперимента такому устройству игральных костей.
5. [88] Пусть Г(х) — равномерное распределение (см, рис. 3, (Ь)). Найдите Кзе и Кзе для следующих 20 наблюдений: 0.414, 0.732, 0.236, 0.162, 0,259, 0.442, 0.189, 0.693, 0,098, 0.302, 0.442, 0.434, 0.141, 0.017, 0.318, 0.669, 0,772, 0.678, 0.354, 0.718. Проверьте, будут ли наблюдения значимо отличаться от ожядаемого поведения по отношению к каждой из двух проверок, 6. [М80] Пусть 5"„(х) задано формулой (10) для фиксированного:г. Чему равна вероят- ность, что Е„(х) ж в/и, для заданного целого з? Чему равно среднее значение гх(х)? Чему равно стандартное отклонение? 7. [МЛ] Покажите, что К„+ и К„никогда не могут быть отрицательными. Какое наиболее возможное значение может иметь К„'? 8.
[00] В разделе описывается эксперимент, в котором 20 значений статистики К~+о были получены при изучении случайной последовательности. Эти значения были нанесены на график, чтобы получить рис. 4. КС-статистика была подсчитана с помощью этого графика. Почему для изучения полученной статистики вместо таблицы прн и = 10 использовались табличные значения для и = 20? 9. [80) Описанный в разделе эксперимент состоит в том, что 20 значений К~~о, вычис- ленных с помощью критерия "максимум-5", который применялся к различным частям случайной последовательности, наносятся на график.
Мы подсчиталя также соответству- кицие 20 значений К~~, поскольку К,е так же распределены, как и К~ц. Теперь можно объединить 40 значений, полученных таким образом (т. е. 20 значений К,"е и 20 значений К,е), опять применить КС-критеряй и получить новые значения К~4е н Кар. Обсудите ценность этой идеи. ь 10. [80] предположим, что кз-статистика подсчитана по результатам и наблкщений, т. е. получено значение Ъ', Повторим подсчет статистики, исполъзуя те же и наблюдений (кояечно, получится такой же резулътат). Затем суммируем данные обоих испытаний, рассматриваа их как единственный гз-критерий с 2н наблюдениями.
(Эта процедура нарушает требование независимости всех наблюдений, которое было выдвинуто в разделе: асе наблюденяя должны быть независимыми.) Какова соотношение между этими двумя значениями Ъ'? 11. [10] Выполните упр. 10, заменив Хь-критерий КС-критерием. 13. [М22) Пусть подсчет Хз-крятериа основан на множестве, состоящем из и наблюдений, в предположении, что р, — вероятность того, что каждое яаблюдение соответствует категории ь. Предположим, что на самом деле вероятность отнесения наблюдения к категории ь равна д«Ф р«(см, упр. 3). Хотелось бм, конечно, чтобы Зс~-критерий обнаружил тот факт, что предположения р«неверны. Покажите, что это прааьайдеш, если и достаточно велико. Докажите аналогичный результат и для КС-критерия.
13. [М24] Докажите, что равенства (13) эквивалентны равенствам (1Ц. ь 14. [НМ2б] Пусть Е, задано равенством (18). Покажите, непосредственно используя формулу Стирлннга, что палиномиальные вероитнасти '«Р" ~Р!«~..«!= щ7Л~ У ' " 0 +«( "'» если Нн Яь,..., Я» ограничены при и -» оо. (Эта идея ведет к обоснованию 1»-критерия; она ближе к "основным прннпнпам«н требует меньше усилий, чем доказательство, приведенное в разделе.) 18. [НМ2»'] Полярные июрдинаты в двумерном пространстве определяются равенствами х = г саь В и 0 = г ьт В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
