AOP_Tom1 (1021736), страница 29
Текст из файла (страница 29)
С Рой(ег) и А. Стюартом (А 6(пег(), Х Воу. Я!ай Бог. В16 (1954), 1.-22.] Аналогично можно вычислить величину дисперсии )'„. Но сначала сформулируем теорему, позволяющую упростить нашу задачу. Теорема А. Пусть С и Н вЂ” две производящие функции, такие, что С(1) = Н(1) = 1, а величины теап(С) и тат(С) определяются формулами (12) и (13). Тогда справедливы равенства шеап(СН) = т пап(С) + теап(Н); уаг(СН) = цаг(С) + ъвт(Н) (15) Данная теорема говорит о том, что среднее (дисперсия) произведения производящих функций равно сумме средних (дисперсий) производящих функций*.
Мы докажем ее несколько позже. Полагая сэ„(д) = (д + и — 1)/и, имеем с',)'„(1) = 1/и, с',1'„'(1) = О. Отсюда 1 1 1 шеап(Я„) = —, иагЯ„) = — — —. в' п пз И наконец, так как Си(з) = П„из Яй(д), следовательно, и и шеап(Си) = ~ шеппса) = ~ — = Ни — 1, ймт ймт " /1 тат(Си) = ~~ тагйй) = ~ ( — — ~,з ) = Ни — Ни" й=з йий Подытожив полученные результаты, получим искомые статистические характеристики величины А: А=( О, -я„-1, — 1, е ° т'я„— яг). (16) Такая форма записи, как в (16), будет использоваться для описания статистических характеристик вероятностных величин на протяжении всей книги.
Итак, мы закончили анализ алгоритма М; новой особенностью этого анализа явилось применение основ теории вероятностей. Для большинства приложений, рассматриваемых в данной книге, вполне достаточно элементарных сведений по теории вероятностей. Определения и простые методы вычисления среднего, дисперсии и среднего квадратичного отклонения, которые мы уже рассмотрели, позволят найти ответы на большинство поставленных вопросов. Более сложные алгоритмы помогут развить способность свосюдно пользоваться инструментами теории вероятностей.
Давайте рассмотрим несколько простых вероятносгных задач, чтобы немно1о попрактиковаться в использовании этих методов. В связи с теорией вероятностей первое, что приходит в голову, †э задача о бросании монеты Предположим,мы подбросили монету и раз и вероятность выпадения "орла" равна р.
Сколько раз в среднем выпадет "орел"? Чему равно среднее квадратичное отклонениео Рассмотрим случай несимметричной монеты, т. е. такой, для которой выпадения "орла" и "решки' не равновероятны. Таким образом, мы не считаем, что р = 1. Это делает задачу более интересной; к тому же любая реальная монета несимметрична (иначе мы не могли бы отличить одну сторону от другой). * Автор имеет в виду, что среднее (дисперсия) случайной величины, соответствующей производящей функции СП (сумме двух независимых случайных величин, соответствующих производящим функциям С и и), равно сумме средних 1дисперсий) случайных величин, соответствующих производящим функциям С и Н вЂ” Прим.
реп Теперь продолжим рассуждения. Пусть рпь — вероятность того, что "орел" выпал Й раз, и пусть С„(х) — соответствующая производящая функция Очевидно, что Р ь =РР< -ц« — ц+ЯР1 -ць (уу) где о = 1 — р — вероятность выпадения ' решки". Как и раньше. из (17) получаем, что С„(х) = (д+ Рх)С„1(х), и в силу очевидного начального условия С~ (х) = о+ Рх имеем С„(х) = (д+рх) (18) Отсюда по теореме А получаем шеап(С„) = п шеап(С1) =Рп; тат(СП) = п тах(С1) = (р — р )п = рдп. Таким образом для числа выпадений "орла" получаем следующие характеристики: (ппп О. аге Рп, шах п, бег ~Яй). (19) На рис.
11 показаны значения р„ь при р = з, п = 12. Если среднее квадратичное отклонение пропорционально Чгп и разность между максимумом и минимумом пропорциональна и, можно считать, что ситуация "устойчива" относительно среднего. 0 1 2 3 4 5 6 7 В 9 10 11 12 Рис. 11. Распределение вероятностей для задачи о бросании монеты: 12 независимых испытаний с вероятностью успеха, равной 3/5 в каждом испытании. Давайте решим еще одну простую задачу.
Предположим, при выполнении некоторого процесса существуют Равноееролтпнме возможности получения значений 1,2,...,и. Производящая функция в этом случае имеет вид 2 1 я С(х) ' х+ хз+...+ вя (20) п и п п в-1 После достаточно трудоемких выкладок находим, что 71хэе1 (п + 1)зп + 1 п(. — ) п(п — 1)х"+' — 2(п+ 1)(п — 1)х" + п(п+ 1)х" ' — 2 Сп(х)- п(х цз Теперь, чтобы найти среднее и дисперсию, нужно вычислить С'(1) и С" (1); но если просто подставить значение х = 1 в формулы, то получится выражение вида О/О. Поэтому возникает необходимость найти предел при з, стремящемся к единице, но это нетривиальная задача.
К счастью, существует гораздо более простой способ дальнейшего решения задачи. По теореме Тейлора (Тау!ог) имеем С(1 + ) С(1) + Ст(1) + 2 + (1) 2 1 (1+ ) 1 и+ 1 (и+ 1)(п — 1) С(1+ з) =— = 1+ — з+ з + тт з 2 6 Следовательно, С'(1) = -'(и + 1), Со(1) = -'(и + 1)(п — 1). В результате получаем следующие статистические характеристики для равномерного распределения: и+1 (и+ 1)(п — 1) ! пнп 1, а»е —, тпах и, с)еч 2 12 В таком случае среднее квадратичное отклонение, равное приблизительно 0.289п, указывает на явно неустпойчивую ситуацию.
В завершение этого раздела докажем теорему А и обоснуем введенные нами понятия с точки зрения классической теории вероятностей. Пусть Х вЂ” случайная величина, которая принимает только неотрицательные целые значения и Х = тт с вероятностью рь для любого к. Тогда б(з) = ро + рта + рзза + называется производящей функт!ией вероятностной для Х, а С(ен) = ро + р,е'т + ртезн + харакптеристпической функцией этого распределения. Распределение, соответствующее произведению двух таких производящих функций, называется свертпкой двух соответствующих распределений и представляет собой распределение суммы двух независимых случайных величин, имеющих распределения, соответствующие перемножаемым производящим функциям.
Среднее значение случайной величины Х часто называют ее матпематпическим ожиданием и обозначают через Е Х. Тогда дисперсия случайной величины Х равна ЕХз — (ЕХ)з. В этих обозначениях производящая функция, соответствующая распределению случайной величины Л, имеет вид С(з) = Езх, т. е. представляет собой математическое ожидание случайной величины з.», если Х принимает только целые неотрицательные значения. Аналогично, если Х вЂ” утверждение, которое либо истинно, либо ложно, вероятность того, что Л истинно, равна Рг(Л") = Е(Х) согласно обозначению Айверсона (см.
1.2.3-(16)). Среднее и дисперсия — это просто два так называемых семиинварианпта или кумулянтпа., введенных Тиеле (Т)т!е!е) в 1903 году. Семиинварианты кт,кз,кз,... оп редел яются правилом кт1 ко1з кз1з — + — + — + = 1пС(ет), 1! 2! 3! (23) Имеем (в к„= — „1и С(ет) ~ Таким образом, нужно просто заменить в формуле (20) г на з + 1 и найти коэффи- циенты: в частности, е»С'(е») к» =, / =С(1), так как С(1) = 2,» р» = 1, и 26СО(»)»СР(е») ег»СГ(е»)2 кг С( ») + С( ~) С( г)г / = С ( ) + С (1) С (1) Поскольку семнинварианты определяются с помощью логарифма производящей функции, теорема А очевидна; фактически ее можно обобщить, распространив на все семиинварианты.
Нормальпое распределение — это такое распределение, для которого все семи- инварианты, за исключением среднего и дисперсии, равны нулю Для нормального распределения можно значительно улучшить неравенство Чебышева. вероятность того, что разница между значением нормально распределенной случайной величины и средним меныпе среднего квадратичного отклонения, равна с+1 — / е '!~гЫ, т/2тя Рг(Х < г) < х "С(х) Рг(Л > г) < х С(х) для 0 < х < 1; для х > 1.
(24) (25) Доказать эти формулы несложно. Если С(г) = ре + ргг+ рггг + °, то Рг(Х <г) =ре+р»+ . +рр0 <х "ре+х~ "р»+ +х!"! "рЬО <х "С(х) при 0 < х < 1 и Рг(Х >г) — р! ) +р( .»~ +''' <х( ~ р( ) +х( 1ы р(г)+1+''' <х С(х) при х > 1. Выбирая такие значения х, которые минимизируют или приближенно минимизируют правые части неравенств (24) и (25), можно получить оценки сверху, достаточно близкие к истинным значениям вероятностей слева. В упр. 21 — 23 неравенства (24) и (25) проиллюстрирован(я для нескольких важных случаев. Эти неравенства являются частными случаями более общего закона, на который указал А, Н. Колмогоров (А.
К. Ко1шойогон) в крисе Сгип»(Ье8г!(Ге с(ег КаЬгэсИе!и!Ы»)ге(гэгесйпип8 (Брг1пйег, 1933): если у(!) > э > 0 для всех ! > г, то т. е. приблизительно 0.68268949213709, Вероятность, что эта разница меньше удвоенного среднего квадратичного отклонения, приблизительно равна 0.95449973610364, и вероятность того, что опа меньше, чем утроенное среднее квадратичное отклонение, примерно равна 0 99730020393674. Распределения, заданные соотношениями (8) и (18), приблизительно нормальны прн больших значениях и (см.
упр. 13 и 14). Часто возникает необходимость убедиться в том, что вероятность большого отклонения случайной величины от ее среднего достаточно мала. Удобные оценки таких вероятностей дают две чрезвычайно простые, но очень важные формулы, которые называются неравенстпеами для хвоспюе распределений. Если С(г) — вероятностная производящая функция случайной величины Х, то Рг(Х > г) < з ' Ег'(Х) при условии, что существует Е1(Х) Неравенство (25) можно получить для у(1) = х' и з = х" УПРАЖНЕНИЯ 1.
[10) Найдите значение рис из соотношений (4) и (5) к дайте интерпретацию этой вероятности в свете алгоритма М 2. [НМ16) Выведите (13) из (10). 3. [М15] Чему будут равны минимум, максимум, среднее и среднее квадратичное отклонение для числа выполнений шага М4, если для нахождения максимума среди 1 000 случайно упорядоченных различных величин воспользоваться алгоритмом Му (Дайте ответ в виде десятичных дробей.) 4.
[М10) Дайте в явном виде формулу для р„з из задачи а бросании монеты (см. соотношение (17)) б. [М19] Чему равны среднее к среднее квадратичное отклонение для распределения, показанного на рнс 112 6. [НМ37] Мы вычислили среднее и дисперсию для важных распределений вероятностей (8), (18), (20). Чему равен третий семнинвариант, кз, в каждом нз этих случаев? 7. [М37] Анализируя алгоритм М, мы предполагали, что все Х[?4] были различны, Теперь сделаем более слабое предположение, а именно — что среди Х [1], Х[2],, Х[и] содержится ровно гп различных значений; в других отношениях этн величины случайны. Каким будет распределение вероятностей для А в этом случае? 8.
[М30) Предположим, что каждое Х[й] выбирается наугад из множества М различных элементов, так что все М" возможных вариантов выбора элементов Х[1], Х[2),...,Х[п] считаются равновероятными. Чему равна вероятность тога, что все Х[3] будут различны? 9. [М39] Обобщите результат предыдущего упражнения и найдите формулу для вероятности того, что среди Х[й) окажется ровна т различных величин.
Выразите зту вероятность с помощью чисел Стнрлинга 10. [МЙО] С помощью результатов трех предыдузцих упражнений выведите формулу для вероятности того, что А = й, при условии, что каждое Х[й] выбирается наугад нз М- элементного множества. ь 11. [М15) Что произойдет с семииивариантами распределения, если заменить функцию С(х) функцией Р(2) ж 2" С(2)? 12.
[нм31] если с(2) = ро+ р1 2+рзее+ . соответствует некоторому распределению вероятностей, то величины Ми ж 2 „' ?с"рз и ти ж 2 ',„(к — М1 )" рз называются и-м моментом и и м центральным моментом соответственно. Покажите, чтоб(е') = 1+М12+Мзг /21+ С помощью формулы Арбогаста (см.
упр. 1.2.3-21) докажите, что )' Мз' М~з Мз" й ! 1!41 3 12! "2... 12 ! и!ь" 1 2™и 1«2 «и ° 41т222+ и В частности, к1 = М1, кз ы Мз — М12 (как мы уже знаем), кз = Мз — ЗМ1 Мз + 2М1 н К4 = М4 — 4М1Мз+12М1 Мз — ЗМ2 — бМ, Найдите аналогичное выражение для к„через 2 4 центральные моменты тз, тз,, где и ) 2 13. [НМ98] Говорят,что последовательность распределений вероятностей, соответствую- ЩИХ ПРОИЗВОДЯЩИМ ФУНКЦИЯМ 1УИ(2) Са СРЕДНИМИ Ри И СРЕДНИМИ КВЭЛРатНЧНЫМИ ОТКЛОНЕ- ннямн а„стремится х нормальному распределению, если — пя /э П ( и/я ) — Р/э л-««а для всех действительных значений й Пусть С„(х) задается формулой (8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
