Алгоритмы - построение и анализ (1021735), страница 255
Текст из файла (страница 255)
Мы определим вероятность с помощью пространства событий (зашр1е зрасе) Я, которое представляет собой множество элементарных событий (е!ешепга~у ечеп!з). Каждое элементарное событие может рассматриваться как возможный исход некоторого эксперимента. Например, в случае эксперимента, состоящего в подбрасывании двух различимых монеток пространство событий состоит из всех возможных 2-строк над множеством (О,Р) (где о обозначает выпадение орла, а р-решкн: Я = (ОО,ОР,РО,РР).
Событие (ечепг) представляет собой подмножество пространства событий Б. Например, в эксперименте с бросанием двух монет событием может быть выпадение одного орла и одной решки: (ОР, РО). Событие Я называется достоверным событием (сенаш ечеп1), а событие И вЂ” невохионсным (пн11 ечепг). Мы говорим, что два события А и В являются взаимоисключающими (пшшайу ехс1пз(че), если А О В = 9. Каждое элементарное событие в е Я также будет рассматриваться нами как событие (в). Все элементарные события по определению являются взаимоисключающими. Аксиомы вероятности Распределение вероятностей (ргоЬаЬ!11!у д(зпзЬщ(оп) Рг () на пространстве событий Я отображает события на действительные числа, удовлетворяя при этом аксиомам вероятности: !.
Для любого события А Рг (А) > О. 2. Рг(Я) = 1. 3. Для любых двух взаимоисключающих событий А и В Рг(АОВ) = Рг(А)+ + Рг(В). В общем случае для любой (конечной нлн бесконечной счетной) последовательности попарно взаимоисключающих событий Аы Аз,... Рг Ц А; = ~> Рг (Аз). Мы называем Рг(А) вероятностью (ргоЬаЬ1!1гу) события А. Заметим, что аксиома 2 выполняет нормализующее действие: нет никаких фундаментальных оснований в выборе в качестве вероятности достоверного события именно 1; просто такое значение наиболее естественное и удобное.
Приложение В. Комбинаторика и теория вероятности 1233 Некоторые результаты следуют непосредственно из приведенных аксиом и основ теории множеств (см. раздел Б.1). Невозможное событие имеет вероятность Рг (9) = О. Если А С В, то Рг (А) < Рг (В). Используя запись А для обозначения события Я вЂ” А (дополнения (сошр!ешепг) А), получим Рг (А) = 1 — Рг (А). Для любых двух событий А и В Рг(АОВ) = Рг(А)+Рг(В) — Рг(АПВ) < < Рг (А) + Рг (В) (В.12) (В.13) Предположим, что в нашем примере с бросанием монет вероятность каждого из четырех элементарных событий равна 1/4.
Тогда вероятность получить как минимум одного орла равна Рг(ОО,ОР, РО) =- Рг(00) + Рг(ОР) + Рг(РО) =- 3/4. Другой способ получить эту вероятность — это заметить, что единственный способ получить при броске меньше одного орла — это выпадение двух решек, вероятность чего равна Рг (РР) = 1/4, так что вероятность получить по крайней мере одного орла равна 1 — 1/4 = 3/4. Дискретные распределения вероятностей Рг (А) = ,'> Рг (з), зеА поскольку элементарные события, составляющие А, являются взаимоисключающими. Если Я конечно и каждое элементарное событие з е Я имеет вероятность Рг(з) = 1/!5), то мы имеем дело с равномерным распределением веронгнностей (нп!гопп ргоЬ- аЬ11!гу г!1зп!Ьш!оп) на Я.
В таком случае эксперимент часто описывается словами "выберем случайным образом элемент Я". В качестве примера рассмотрим бросание симмегнричной монеты ((а!г сош), для которой вероятность выпадения орла равна вероятности выпадения решки и составляет 1/2. Если мы бросаем монету и раз, то получим равномерное распределение вероятностей на пространстве событий Я = (О,Р)" (которое представляет собой множество размером 2"). Каждое элементарное событие Я может Распределение вероятностей называется дискрегнным (йзсгеге), если оно определено на конечном или бесконечном счетном пространстве событий. Пусть 5— пространство событий, Тогда для любого события А Часть ЧП!. Приложения: математические основы 1234 быть представлено строкой длиной п на множестве (О,Р), и вероятность каждого элементарного события равна 1/2".
Событие А = (Выпало ровно )с орлов и и — й решек) представляет собой подмножество Я размером ]А[ = (ь), поскольку имеется ровно (",) строк длиной и на множестве (О,Р), содержащих lс О. Вероятность события А, таким образом, равна ("„)/2". Непрерывное равномерное распределение вероятности Непрерывное равномерное распределение вероятности представляет собой пример распределения вероятности, в котором не все подмножества пространства событий рассматриваются как события. Непрерывное равномерное распределение вероятности определено на закрытом отрезке [а, 6] действительных чисел (а < 6). Интуитивно все точки отрезка [а, 6] рассматриваются как "равновероятные".
Имеется несчетное множество точек, так что мы не можем назначить каждой точке свою конечную положительную вероятность, так как мы не сможем одновременно удовлетворить аксиомы 2 и 3. По этой причине мы должны связывать вероятность толью с некоторыми из подмножеств Я, чтобы удовлетворить аксиомы вероятности для этих событий. Для любого закрытого отрезка [с, с(], где а < с < с( < Ь, непрерывное равномерное раслределвние вероятности (сопбпиопз ппКопп ргоЪаЬ1!Иу йзпзЬаюп) определяет вероятность события [с, и] как с( — с Рг([с, Н]) =— Обратите внимание, что для произвольной отдельной точки х = [х, х] вероятность х равна О. Если мы удалим конечные точки отрезка [с, д], то получим открытый интервал (с, с().
Поскольку [с, с(] = [с, с] 0 (с, с() О [д, о], в соответствии с аксиомой 3 Рг ([с, с(]) = Рг ((с, Н)). Вообще говоря, множество событий для непрерывного равномерного распределения вероятности представляет собой любое подмножество пространства событий [а, 6], которое может быть получено юнечным (нли бесконечным счетным) объединением открытых и закрытых интервалов. Условная вероятность и независимость Иногда мы располагаем частичной информацией о результате эксперимента. Например, пусть нам известно, что в результате бросания двух симметричных монет по крайней мере на одной из них выпал орел. Чему в таком случае равна вероятность того, что обе монеты выпали орлом? Имеющаяся информация позволяет исключить выпадение двух решек, а три оставшихся элементарных события Приложение В.
Комбинаторика и теория вероятности 1235 имеют равную вероятность 1/3, так что именно такой и будет интересующая нас вероятность выпадения двух орлов. Изложенная идея формализуется в определении условной вероятности (сопгййопа! ргоЬаЬ!1!гу) события А при условии осуществления события В: Р (АПВ) Рг(В) (В.14) (при этом Рг (В) ф О).
Интуитивно формула легко объяснима. Вероятность того, что произойдет как событие А, так и событие В (т.е. Рг(А П В)), равна вероятности того, что произойдет событие В (Рг (В)), умноженной на вероятность того, что при условии осуществления события В произойдет еще и событие А (Рг (А ! В)), т.е. Рг (А П В) = Рг(В) Рг (А ) В).
В приведенном выше примере эксперимента событие А заключается в том, что обе монеты выпали орлами, а  — что как минимум одна монета выпала орлом. Таким образом, Рг(А ! В) = (1/4)/(3/4) = 1/3. Два события называются независимыми (!пдерепдепг), если Рг(АПВ) = Рг(А)Рг(В), (В.15) Рг(А; П Ау) = Рг (Аз) Рг(А ) . Мы говорим, что эти события нвзавипииы в совокупности (шпша!! у шдерепдеп!), если для любого й-подмножества А;„А;„..., А;„исходного множества, где 2 < lс < п и 1 < гг < (з « (ь < и, выполняется равенство Рг(А,, ПА,, Г!...
Г1А;„) = Рг(А;,) Рг(А;,) . Рг(А;„). что при Рг (В) ~ О эквивалентно условию Рг (А ! В) = Рг (А) В нашем примере с бросанием двух монет результаты отбельных бросков независимы, так что вероятность выпадения двух орлов равна (1/2) (1/2) = 1/4. Предположим теперь, что одно событие состоит в том, что первая монета выпала орлом, а второе — что монеты выпали по-разному. Каждое из этих событий имеет вероятность 1/2, а вероятность осуществления обоих — 1/4. В соответствии с определением, эти события независимы, несмотря на то, что на первый взгляд это не очевидно. И наконец, представим, что монеты спаяны вместе, так что они либо обе выпадают орлами, либо обе выпадают решками (вероятности этих выпадений равны). Итак, вероятность выпадения каждой монеты орлом — 1/2, но и вероятность того, что обе монеты выпадуг орлом, — тоже 1/2, а так как 1/2 ~ ф (1/2) (1/2), следовательно, события "первая монета выпала орлом" и "вторая монета выпала орлом" в данном случае не являются независимыми.
События Аы Аз,..., А„называются попарно независимыми (ра!гчл!зе !пдерепдеп1), если для всех 1 < 1 < з < и выполняется равенство Часть Ч!П. Приложения: математические основы 1236 Например, предположим, что мы бросили две симметричные монеты. Пусть Ад — событие, заключающееся в выпадении первой монеты орлом, Аг — событие, заключающееся в выпадении орлом второй монеты, а Аз — что монеты выпали по-разному. Мьд имеем Поскольку для 1 < 4 < 3' < 3 Рг (А; П Аг) = Рг (А;) Рг (А ) = 1/4, события Ап Аг и Аз попарно независимы, однако не являются независимыми в совокупности, так как Рг(Ад ПАг гд Аз) = О, а Рг(Ад) Рг(Аг) Рг(Аз) = 1/8 ~ О. Теорема Байееа Из определения условной вероятности (В.14) и коммутативности А П В = В П П А следует, что для двух событий А и В с ненулевыми вероятностями Рг(АПВ) = Рг(В)Рг(А ~ В) = Рг(А)Рг(В ) А).
(В.16) Разрешая уравнение относительно Рг (А ~ В), получим формулу Рг (А) Рг (В ) А) Рг (В) дВ.17) известную как вдеореиа Байеса (Вауез'з д)деогеш). Знаменатель Рг (В) представ- ляет собой нормализующий член, который можно выразить иначе. Поскольку В = (В ПА) 0 (В ПА), а В ПА и ВША — взаимоисключающие события, Рг(В) = Рг(В ПА)+Рг(В ПА) = Рг(А)Рг(В ~ А)+Рг(А) Рг(В ! А). Подставляя полученное выражение в (В.17), получим эквивалентный вид форму- лы Байеса Рг (А) Рг (В ! А) Рг (А) Рг(В ~ А) + Рг (А) Рг (В ( А) Теорема Байеса может упростить вычисление условной вероятности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
