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