Алгоритмы - построение и анализ (1021735), страница 256
Текст из файла (страница 256)
Предположим, например, что у нас есть симметричная монета и монета, которая всегда Рг (Ад) Рг (Аг) Рг (Аз) Рг (Ад П Аг) Рг (Ад П Аз) Рг(Аг П Аз) Рг (Ад гд Аг й Аз) = 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? Обоснуйте свой ответ. В.З Дискретные случайные величины Дискретная случайная величина гг))всгесе гапбош чаг)аЬ)е) Х вЂ” это функция, отображающая конечное или бесконечное счетное пространство событий Я на множество действительных чисел. Она связывает с каждым возможным исходом эксперимента действительное число, что позволяет нам работать с распределением вероятностей на множестве значений данной функции.
Случайные величины могут быть определены и для несчетных бесконечных пространств событий, но при этом возникают технические проблемы, которых лучше избежать. Нам не придется работать с несчетными бесконечными пространствами событий, так что далее везде предполагается, что случайные величины дискретны. Для случайной величины Х и действительного числа х определим событие Х = х как (в Е Я: Х (в) = х); таким образом, Функция /(х) = Рг(Х = х) называется функцией плотности вероятности гргоЬаЬ)))гу г)елв!гу йлсг)оп) случайной величины Х.
Из аксиом вероятности следует, что Рг (Х = х) > О и 2,' Рг (Х = х) = 1. Приложение В. Комбинаторика и теория вероятности 1239 В качестве примера рассмотрим эксперимент, состоящий в бросании пары игральных костей. В пространстве событий имеется 36 элементарных событий. Будем считать, что все они равновероятны, т.е. для кахслого элементарного события в е Я его вероятность Рг(в) = 1/Зб. Определим случайную величину Х как максимальное количество очков, выпавшее при броске на одной из костей. Тогда, например, Рг(Х = 3) = 3/5, так как Х равно 3 в 5 из 36 возможных элементарных событий, а именно при выпадении (1,3), (2,3), (3,3), (3,2) или (3, 1). Как правило, на одном пространстве событий определяются несколько случайных величин.
Если Х и У вЂ” случайные величины, то функция г" (х, у) = Рг(Х = х и У = у) называется совместной функцией алотностн вероятности (~о[пг ргоЬаЬг!йу депкйу бшсйоп) Х и У. Для фиксированного значения у Рг(У = у) =,з Рг(Х = х и У = у), и, аналогично, для фиксированного значения х Рг(Х = х) = ,'г Рг(Х = х и У = у). р Используя определение условной вероятности (В.14), мы имеем Рг (Х = х и У = у) Рг(У = у) Две случайные величины Х и У являются независимьгмн, если для всех х и у события Х = х и У = у независимы, т.е. для всех х и у выполняется Рг(Х = х и У = у) = Рг(Х = х) Рг(У = у). Для данного множества случайных величин, определенных на одном и том же пространстве событий, можно определить новую случайную величину как сумму, произведение или другую функцию имеющихся случайных величин. Математическое ожидание случайной величины Простейшая и наиболее часто используемая характеристика случайной величины — ее среднее значение (шеап), или математическое олгсидание (ехрес1ед ча!ие, ехресгабоп), которое определяется для дискретной случайной величины следующим образом: Е !Х] = ~~г хРг(Х = х).з (В.19) Н отечестаенной математической литературе для математического ожидания принято обозначение М [Х[.
— Прим. ред. Часть ЧП1. Приложения: математические основы 1240 Зто значение вполне определено в случае конечного или бесконечного абсолютно сходящегося ряда. Иногда математическое ожидание Х обозначают как пх или, если случайная величина очевидна из контекста, просто д. Рассмотрим игру, в которой бросается пара симметричных монет. Вы выигрываете 3 доллара при выпадении орла, и проигрываете 2 доллара при выпадении решки. Математическое ожидание случайной величины Х, равной вашему выигрышу, равно Е [Х] = 6 Рг (2 орла) + 1 Рг (1 орел, одна решка) — 4 Рг (2 решки) = = 6 ° (1/4) + 1 (1/2) — 4 (1/4) = 1. Математическое ожидание суммы двух случайных величин равно сумме их математических ожиданий: Е [Х + У] = Е [Х] + Е [У], (В.20) Е[д(Х)] = ~~) д(х) Рг(Х = х).
Пусть д (х) = ах. Тогда для произвольной константы а Е[аХ] = аЕ[Х]. (В.21) Таким образом, математическое ожидание представляет собой линейную функ- цию: для двух произвольных случайных величин Х и У и произвольной констан- ты а Е [аХ + У] = аЕ [Х] + Е [У] . (В.22) если значения Е [Х] и Е [У] определены. Зто свойство называется линейностью математического ожидания (11пеапту оГ ехрес1а11ол), причем оно справедливо даже тогда, когда случайные величины Х и У не являются независимыми.
Зто правило распространяется и на конечные, и на абсолютно сходящиеся бесконечные суммы математических ожиданий. Линейность математического ожидания является ключевым свойством, обеспечивающим возможность проведения вероятностного анализа с использованием индикаторной случайной величины (см. раздел 5.2). Если Х вЂ” произвольная случайная величина, то любая функция д (х) определяет новую случайную величину д (Х).
Если математическое ожидание этой величины определено, то Приложение В. Комбинаторика и теория вероятности 1241 Если случайные величины Х и У независимы и каждая имеет определенное математическое ожидание, то Е [ХУ] = ~~~ ~~) ху Рг (Х = х и У = у) = хуРг(Х = х) Рг(У = у) = ) хРг(Х = х) ~~~ уРг(У = у) = Е [Х] Е [У] .
В общем случае, если у нас имеется п независимых в совокупности случайных величин Хз, Хз,..., Х„, то Е[ХгХз..Х„] =Е[Хг]Е[Хз]. Е[Х„]. (В.23) Если случайная величина Х принимает значения из множества неотрицательных целых чисел, то для ее математичесюго ожидания имеется красивая формула: Е [Х] = ~~~ 1Рг (Х = 1) = а=о = ) 1(Рг(Х > 1) — Рг(Х > 1+ 1)) =о = ~~> Рг(Х >1), (В.24) Е [ г" (Х)] > г" (Е [Х]) (В.25) (в случае, югда математическое ожидание существует и конечно). Функция г' (х) называется выпуклой вниз (соптех), если для всех х и у и всех 0 < Л < 1 выполняется неравенство г" (Лх+ (1 — Л) у) < Лг'(х) + (1 — Л) )'(у).
поскольку каждый член Рг (Х > 1) присутствует в сумме со знаком плюс 1 раз, и 1 — 1 раз — со знаком минус (кроме члена Рг (Х > 0), который в сумме отсутствует). При применении выпуклой вниз функции г" (х) к случайной величине Х неравенснгво Йенсена (1епзеп'з )пег)ца11гу) гласит, что Часть Чй]. Приложения: математические основы 1242 Дисперсия и стандартное отклонение Математическое ожидание случайной величины не говорит нам о том, насколько сильно "разбросаны" ее значения.
Например, если у нас есть случайные величины Х и У, такие что Рг (Х = 1/4) = Рг (Х = 3/4) = 1/2 и Рг (У = О) = = Рг (У = 1) = 1/2, то их математические ожидания равны 1/2, однако реальные значения У находятся дальше от математического ожидания этой случайной величины, чем в случае Х. Дислерсия (уапапсе) случайной величины Х с математическим ожиданием Е [Х] определяется какз Чаг [Х] = Е [(Х вЂ” Е [Х])~] = = Е [Хз — 2ХЕ [Х] + Ез [Х]] = Е [Х'] — Е'[Х].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
