Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 256
Текст из файла (страница 256)
Интуитивно все точки отрезка [а, 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), получим эквивалентный вид форму- лы Байеса Рг (А) Рг (В ! А) Рг (А) Рг(В ~ А) + Рг (А) Рг (В ( А) Теорема Байеса может упростить вычисление условной вероятности.
Предположим, например, что у нас есть симметричная монета и монета, которая всегда Рг (Ад) Рг (Аг) Рг (Аз) Рг (Ад П Аг) Рг (Ад П Аз) Рг(Аг П Аз) Рг (Ад гд Аг й Аз) = 1/2, = 1/2, = 1/2, = 1/4, = 1/4, = 1/4, = О. Приложение В. Комбинаторика и теория вероятности 1237 (1/2) . 1 4 (1/2) 1+ (1/2) (1/4) 5' Упражнения В.2-1. Докажите неравенство Буля: для любой конечной или бесконечной счетной последовательности событий АмАз,... справедливо следующее неравенство: Рг (А1 0 Аз О...) < Рг (А1) + Рг (Аз) +.... (В.18) В.2-2.
Профессор Ванстоун бросает симметричную монету один раз, а профессор Унопетри — два раза. Чему равна вероятность того, что профессор Ванстоун получит больше выпавших орлов, чем профессор Унопетри? Имеется тщательно перетасованная колода из десяти карт, пронумеро- ванных числами от 1 до 10. Из колоды последовательно вынимаются 3 карты. Какова вероятность того, что эти карты будут находиться в поряд- ке возрастания их достоинства? В.2-3. Разработайте процедуру, которая получает в качестве входных параметров два целых числа а и 6 10 < а < 6) и, используя симметричную монету, имитирует бросание несимметричной монеты с появлением орла с вероятностью а/6, и решки — с вероятностью (Ь вЂ” а)/6.
Оцените математическое ожидание количества бросков монеты (которое должно быть О 11). 1Указание: используйте бинарное представление числа а/6.) Докажите, что Рг (А ( В) + Рг (А ~ В) = 1. Докажите, что для любого множества событий Ам Аз,..., А„ * В.2-4.
В.2-5. В.2-б. Рг(Аг ПАз П...ОА„) = Рг(А1) Рг(Аз ( А1) Рг(Аз ) А1 ПАз) Рг(А„~ А1 П Аз О... О А„1) . * В.2-7. Покажите, как построить множество из и попарно независимых событий так, чтобы никакое его подмножество из более чем двух элементов ие являлось независимым в совокупности. выпадает орлом.
Мы случайным образом выбираем монету и два раза ее подбрасываем. Предположим, что оба раза выпал орел. Какова вероятность того, что мы выбрали несимметричную монету? Эта задача легко решается при помощи формулы Байеса. Пусть А — событие, состоящее в том, что выбрана несимметричная монета, а  — выпадение двух орлов. Нам надо найти вероятность Рг (А ( В) Так как Рг (А) = 1/2, Рг (В ! А) = = 1, Рг (А) = 1/2 и Рг (В ( А) = 1/4, получаем Часть Ч))!.
Приложения: математические основы 1238 *В.2-8. Два события А и В являются условно независимыми относительно события С, если Рг (А О В ! С) = Рг (А ~ С) Рг (В ~ С). Приведите нетривиальный пример двух событий, которые не являются независимыми, но при этом условно независимы относительно некоторого третьего события. * В.2-9. Вы участвуете в игровом шоу, где приз спрятан за одним из трех занавесов. Вы выигрываете приз, если угадываете, где он находится.
После того как вы выбираете занавес, ведущий открывает один из оставшихся. Если за ним приза нет, вы можете изменить свой выбор, указав на третий занавес. Как изменятся ваши шансы на выигрыш, если вы сделаете это? * В.2-! О. Один из трех заключенных Х, У и Е будет освобожден, а оставшиеся будут отбывать наказание. Кто именно — знает охранник, но ему запрещено сообщать заключенным об их судьбе. Заключенный Х просит охранника сообщить, кто из У и Я останется в тюрьме, мотивируя это тем, что он и так знает, что один из них будет отбывать наказание, так что нз ответа охранника он ничего не узнает о собственной судьбе.
Охранник сообщает, что У освобожден не будет. После этого Х полагает, что его шансы на свободу, которые составляли 1/3, возрастают до 1/2, так как он знает, что освобожден будет только либо он, либо У. Прав ли он, иля его шансы на свободу остаются равными 1/3? Обоснуйте свой ответ. В.З Дискретные случайные величины Дискретная случайная величина гг))всгесе гапбош чаг)аЬ)е) Х вЂ” это функция, отображающая конечное или бесконечное счетное пространство событий Я на множество действительных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
