Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 277
Текст из файла (страница 277)
Часть Улг Приложения: математические основы ! с46 в совокупности, поскольку Рг (Ад Гд Аз и Аз) = О н Рг (Ад) Рг(Аз) Рг (Аз) = 1/8 ~ О. Теорема Байеса Из определения условной вероятности (В.14) и коммутативности АПВ = ВПА следует, что для событий А и В с ненулевыми вероятностями Рг(АП В) = Рг(В) Рг(А ( В) = Рг(А) Рг(В ( А) . (В.16) Решая уравнение относительно Рг (А ~ В), получаем формулу Рг (А) Рг (В ) А) Рг (В) (В.17) известную как лдеорема Байеса (Вауез'з д)деогеш).
Знаменатель Рг (В) представ- ляет собой нормирующую константу, которую можно записать иначе. Поскольку В = (ВгдА)дд(ВША) и поскольку ВПА и ВПА являются взаимоисключающими событиями, Рг(В) = Рг(ВПА)+Рг(ВПА) = Рг(А) Рг(В ~ А) +Рг(А) Рг(В ~ А) Подставив полученное выражение в (В.17), получим эквивалентный вид формулы Байеса: Рг (А) Рг (В / А) Рг(А) Рг(В / А) + Рг(А) Рг (В ! А) (В.!8) (1/2) 1 (1/2) 1 + (1/2) (1/4) = 4/5 . Теорема Байеса может упростить вычисление условной вероятности.
Предположим, например, что есть симметричная монета и монета, которая всегда выпадает орлом. Наш эксперимент состоит из трех событий: мы случайным образом выбираем монету и два раза ее подбрасываем. Предположим, что оба раза выпал орел. Канэва вероятность того, что мы выбрали несимметричную монету? Эта задача легко решается с помощью формулы Байеса. Пусть А — событие, состоящее в том, что выбрана несимметричная монета, а  — выпадение двух орлов. Необходимо найти вероятность Рг (А ~ В). Мы имеем Рг (А) = 1/2, Рг (В ~ А) = 1, Рг (А) = 1/2 и Рг (В ( А) = 1/4; следовательно, ггег Приеонеение В. Комбинаторика и теорие вероетноети Упражнения В.г.! Профессор Ванстоун бросает симметричную монету один раз, а профессор Унопетри — два раза.
Чему равна вероятность того, что профессор Ванстоун получит больше выпавших орлов, чем профессор Унопетри? в.г.г Докажите неравенсеиво Буля: для любой конечной или бесконечной счетной последовательности событий Ап Аз,... справедливо следующее неравенство: Рг(А1 О Аз О . ) < Рг (Аг) + Рг (Аз) + (В.19) в.г.з Имеется тщательно перегасованная колода из десяти карт, пронумерованных числами от ! до 1О. Из колоды последовательно вынимаются три карты.
Какова вероятность того, что эти карты будут находиться в порядке возрастания их достоинства? В.2.4 Докажите, что Рг(А ( В) + Рг(А ! В) = 1. в.г.у Докажите, что для любого набора событий Ам Аз, ., А„ Рг(Аз ПАз П ..ПА„) = Рг[Аг) Рг(Аз ( Аз) Рг(Аз ~ Аг Г1Аз) ..
Рг (А„) Аз П Аз П .. П А„г) . В.г.б * Разработайте процедуру, которая получает в качестве входных параметров два целых числа, а и Ь (О < а < Ь), и, используя симметричную монету, имитирует бросание несимметричной монеты с появлением орла с вероятностью а/Ь и решки — с вероятностью (Ь вЂ” а)/Ь. Оцените математическое оясидание количества бросков монеты (которое должно быть 0(1)).
(Указание: используйте бинарное представление числа а/Ь.) В.2. 7 * Покажите, как построить множество из п попарно независимых событий так, чтобы никакое его подмножество из более чем двух элементов не являлось независимым в совокупности. в.г.в * Два события, А и В, являются условно независимыми относительно события С, если Рг(АПВ / С) = Рг(А / С) Рг(В / С) . !24о Часть Егг!. Приложении: математические основы Приведите нетривиальный пример двух событий, которые не являются независимыми, но при этом условно независимы относительно некоторого третьего события.
В.2.9 * Вы участвуете в игровом шоу, в котором приз спрятан за одним из трех занавесов. Вы выигрываете приз, если угадываете, где он находится. После того как вы выбираете занавес, ведущий открывает один из оставшихся. Если за ним приза нет, вы можете изменить свой выбор, указав на третий занавес. Как изменятся ваши шансы на выигрыш, если вы сделаете это? В.2.10 * Один из трех заключенных, Х, г' и Я, будет освобожден, а остальные будут отбывать наказание.
Кто именно — знает охранник, но ему запрещено сообщать заключенным об их судьбе. Заключенный Х просит охранника сообщить, кто из У и е останется в тюрьме, мотивируя это тем, что он и так знает, что один из них будет отбывать наказание, так что из ответа охранника ои ничего не узнает о собственной судьбе.
Охранник сообшает, что г' освобожден не будет. После этого Х полагает, что его шансы на свободу, которые составляли 1/3, возрастают до 1/2, так как он знает, что освобожден будет только либо он, либо Е. Прав ли он или его шансы на свободу остаются равными 1/3? Обоснуйте свой ответ. В.З. Дискретные случайные величины Дискретная случайная величина (гйасгеге гаврош чапаЫе) Х вЂ” это функция, отображающая конечное или бесконечное счетное пространство выборок В иа множество действительных чисел.
Она связывает с каждым возможным исходом эксперимента действительное число, что позволяет работать с распределением вероятностей на множестве значений данной функции. Случайные величины могут быть определены и для несчетных бесконечных пространств выборок, но при этом возникают технические проблемы, которых лучше избежать. Нам не придется работать с несчетными бесконечными пространствами выборок, так что далее везде предполагается, что случайные величины дискретиы. Для случайной величины Х и действительного числа х определим событие Х = х как (е Е Я; Х(е) = х); таким образом, Рг(Х = х) = 2 Рг(е) вяз:Х(в)=е Функция /(х) = Рг (Х = х) гг4Р Приложение д Комбинаторика и теория вероятности ('(х, у) = Рг (Х = х н У = у) называется совместной функцией плотности вероятности Цо1пг ргоЬаЬ|11гу депз(гу бшсг(оп) Х и У.
Для фиксированного значения у Рг(У = у) = ~~~ Рг(Х = х и У = у), и аналогично для фиксированного значения х Рг(Х = х) = ~~~ Рг(Х = х и У = у) Используя определение условной вероятности (В.14), имеем Р (Х (у у) Р (Х= 1'=У) Рг(У = у) Определим две случайные величины, Х и У, как независимые, если для всех х и у события Х = х и У = у независимы, или, что то же самое, если для всех х и у мы имеем Рг (Х = х и У = у) = Рг (Х = х) Рг (У = у). Для заданного множества случайных величин, определенных на одном и том же пространстве выборок, можно определить новую случайную величину как сумму, произведение или другую функцию имеющихся случайных величин. Математическое ожидание случайной величины Простейшая и наиболее часто используемая характеристика случайной величины — ее "среднее" значение.
Ожидаемое значение (или математическое ожидание (ехресгед ча1пе), или среднее (шеап)) дискретной случайной величины Х представляет собой Е [Х] = ~~~ х. Рг(Х = х), к (В.20) 40 зяк 37Ю5 является функцией плотности вероятности (ргоЬаЬ(1йу депгйгу бшсг1оп) случайной величины Х. Из аксиом вероятности следует, что Рг(Х = х) ) 0 и 2 ', Рг(Х = х) = 1. В качестве примера рассмотрим эксперимент, состоящий в бросании пары игральных костей. В пространстве выборок имеется Зб элементарных событий.
Будем считать, что все они равновероятны, т.е. для каждого элементарного события в Е Я его вероятность Рг(в) = 1/36. Определим случайную величину Х как максимальное количество очков, выпавшее при броске на одной из костей. Тогда, например, Рг (Х = 3) = 5/36, так как Х равно 3 в 5 из 36 возможных элементарных событий, а именно — при выпадении (1,3), (2,3), (3,3), (3,2) и (3,1). Зачастую на одном пространстве выборок определяется несколько случайных величин. Если Х и У вЂ” случайные величины, то функция 1с50 Часть ШП, Лриложемиль математические осиояы которое является вполне определенным, если сумма конечна или абсолютно сходящаяся4. Иногда математическое ожидание Х обозначают как 5ах или, если случайная величина очевидна из контекста, просто как 5а. Рассмотрим игру, в юторой бросается пара симметричных монет.
Вы выигрываете три доллара при выпадении орла и проигрываете два доллара при выпадении решки. Математическое ожидание случайной величины Х, равной вашему выигрышу, равно Е[Х] = 6 Рг(2 о) +1 Рг(1 о, 1 р) — 4 Рг(2 р) = 6(1/4) + Ц1/2) — 4(1/4) =1. Математическое ожидание суммы двух случайных величин равно сумме их математических ожиданий: Е [Х + У] = Е [Х] + Е [У], (В.21) если значения Е [Х] и Е [У] определены.
Это свойство называется линейносиаью математического ожидания (1(пеап1у оТ ехрес1абоп), причем оно справедливо даже тогда, когда случайные величины Х и У не являются независимыми. Это правило распространяется и на конечные, и на абсолютно сходящиеся бесконечные суммы математических ожиданий. Линейность математического ожидания является ключевым свойством, обеспечивающим возможность проведения вероятностного анализа с использованием индикаторных случайных величин (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
