Алгоритмы - построение и анализ (1021735), страница 258
Текст из файла (страница 258)
Комбинаторика н теория вероятности 1249 * В.4-8. Рассмотрим и испытаний Бернулли, где р; — вероятность успеха в 1-м испытании, а Х вЂ” случайная величина, равная общему количеству успехов. Пусть р > р, для всех 1 = 1, 2,..., п. Докажите, что для 1 < /с < и Рг(Х < Ц > ,'~ Ь(г;п,р). * В.4-9. Пусть Х вЂ” случайная величина, равная общему количеству успехов в множестве А из и испытаний Бернулли, а р; — вероятность успеха в 1-м испытании.
Пусть Х' — аналогичная случайная величина, равная общему количеству успехов в множестве А' из и испытаний Бернулли, где р', > р; — вероятность успеха в 1-м испытании. Докажите, что для 0<Ь<п Рг(Х' > Ц > Рг(Х > й) . (Указание: покажите, как получить результаты испьпаний Бернулли А' из эксперимента, включающего испытания А, а затем воспользуйтесь результатом упражнения В.3-7.) * В.5 Хвосты биномиального распределения Во многих задачах требуется определить не вероятность того, что в и испытаниях Бернулли будет получено ровно к успешных исходов, а вероятность того, что будет получено не более (или не менее) й успешных исходов.
В этом разделе мы рассмотрим хвостом (1айз) биномиального распределения, т.е. области распределения Ь (к; и, р), далекие от среднего значения пр, и найдем некоторые важные оценки для них. Здесь мы будем рассматривать правый хвост распределения Ь ()с; и, р); левый хвост получается при простой взаимной замене успешных исходов на неудачи. Теорема В.2.
Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов. Тогда для 0 < й < п вероятность того, что будет получено как минимум к успешных исходов, равна и Рг(Х > Ц = ~Ь(г;п,р) < Ир~. 1,/с/ з=ь Доказаюиельство. Для множества Я С (1, 2,..., и) обозначим через Ая событие, которое заключается в том, что 1-я попытка успешна для всех 1 Е Я. Понятно, что 1250 Часть ЧН1.
Приложения: математические основы если (Я( = 1<, то Рг (Ал) = р". Таким образом, Рг (Х > к) = Рг (Существует Я С (1,2,..., п): Д = )т и Ал) = где использованное неравенство вытекает из неравенства Буля (В.18). Приведенное далее следствие просто переформулирует эту теорему для левого хвоста биномиального распределения.
Все доказательства переформулированных таким образом (для противоположного хвоста) теорем далее в этом приложении предлагаются читателю в качестве самостоятельного упражнения. Следствие В.З. Рассмотрим последовательность из п испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов.
Тогда для 0 < й < п вероятность того, что будет получено не более 1< успешных исходов, равна г.~х<н-Т ь|<,р~< ( )(1-рг '= ( )(1-и" '. <=0 И Следующая рассматриваемая оценка относится к левому хвосту биномиального распределения. Теорема В.4. Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, и вероятностью неудачи, равной о = 1 — р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов.
Тогда для 0 < 1«пр вероятность того, что будет получено менее Й успешных исходов, равна ь-1 Рг(Х < Ц = ,'> Ь(т';п,р) < ЬЯ;п,р). )сд <=о Доказательство. Ограничим ряд ~„"~ с Ь(г;п,р) геометрическим рядом с ис- пользованием методики из раздела А.2. Для г = 1, 2,..., к из (В.40) получим: Ь(г — 1; п, р) то йу lсд Ь(г;п,р) (и — г'+ 1)р (и — г) р (и — lс) р Приложение В. Комбинаторика и теория вероятности 1251 Вводя обозначение Ьо Ь~ Ь х— < — — <1 (п — гс) р (п — пр) р пс1р пр получим, что 6(1 — 1;п,р) < хЬ(г;п,р) для О < 1 < Ь. Применяя это неравенство итеративно /с — 1 раз, мы получим Ь(г;п,р) < х~ 'Ь(/с;п,р) для О <1< й и, следовательно, ,'~ Ь(г;п,р) < ~х~ зЬ(lс;п,р) < с=о '=о < Ь (и; п, р) ~~> х' = с=1 х = — Ь(1с;п,р) = 1 — х Ь(к;п,р).
Ь Следствие В.5. Рассмотрим последовательность из п испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, и вероятностью неудачи, равной д = 1 — р. Тогда для О < 1с < пр/2 вероятность того, что будет получено менее lс успешных исходов, составляет менее половины от вероятности получения менее /с + 1 успешного исхода. Доказательство. Посюльку Ь < пр/2, мы имеем Ьд (пр/2) д (пр/2) о пр — /с пр — (пр/2) пр/2 посюльку д < 1. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов. Из теоремы В.4 следует, что вероятность получить менее /с успешных исходов равна Рг (Х < Ц = ~ Ь (ь'; п, р) < Ь (й; и, р) .
Таким образом, Рг(Х < Ь1 Я*=о Ь(1'п Р) Е'=о Ь(1;п Р) Рг(Х < /с+ 1) Е =о Ь(1'п р) Ба=о Ь(1'п р) + Ь(й'п р) поскольку ~;:о 6(1;п,р) < Ь(Ь;п,р). Часть ЧПЕ Приложения: математические основы 1252 Оценка для правого хвоста выполняется аналогично. Ее доказательство оставлено читателю в качестве упражнения В.5-2. Следствие В.б. Рассмотрим последовательность из п испытаний Бернулли с ве- роятностью успешного исхода каждого испытания, равной р.
Пусть Х вЂ” случай- ная величина, равная общему количеству успешных исходов. Тогда для пр < Й < < п вероятность более чем к успешных исходов равна Рг(Х > Ь) = ,'~ Ь(т";п,р) < Ь(Й;п,р). (и — Й) р з=ь+1 Следствие В.7. Рассмотрим последовательность из п испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, и вероятностью неудачи, равной 1 = 1 — р. Тогда для (пр+ п)/2 < и < п вероятность более чем )с успешных исходов не превышает половины вероятности более чем /с — 1 успешных исходов. и В следующей теореме рассматриваются и испытаний Бернулли; вероятность успеха в г-м испытании составляет р,.
Как видно из следствия из данной теоремы, ее можно использовать для оценки правого хвоста биномиального распределения, положив р; = р для всех испытаний. Теорема В.8. Рассмотрим последовательность из п испытаний Бернулли, в кото- рой в 1-м испытании (г = 1, 2,..., п) вероятность успеха равна р;, а неудачи— Ри = 1 — р;. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов, а д = Е [Х]. Тогда для г >,и Рг(Х вЂ” д>г) < ( — ) Рг (Х вЂ” д > г) = Рг (еь(х ") > е' ), где значение а будет определено позже. Используя неравенство Маркова (В.29), мы получим Рг (еа(х — и) > еат )~ < Е [еа(х-Я)~ е-ьг (В.42) Теперь нам надо оценить величину Е [еь(~ и)] и найти подходящее значение а для уравнения (В.42). Начнем с вычисления Е (еь(~ ")).
Используя обозначения, принятые в разделе 5.2, мы можем записать Х; = 1 (Исход 1-го испытания Бернулли успешен) Доказательсиюво. Поскольку при любом а > 0 функция е * — строго возрастающая, (В.41) Приложение В. Комбинаторика и теория вероятности 1253 для г = 1, 2,..., и; т.е. Х; — случайная величина, принимающая значение 1 в слу- чае успеха и Π— в случае неудачи.
Таким образом, и х=) х; и, вследствие линейности математического ожидания, и и и р = Е]х] = Е ~~1 Х; = 1 Е]Х1] = ~) р;, 1=1 1=1 (=1 откуда следует, что Е [еа(Х вЂ” р)~ = Е [еа~ ~" 1(Х<-р<) ] = Е Пса(Х,— р;) = П Е [еа(Х;-р,)~ 1=1 1=1 что следует из (В.23), поскольку случайные величины Х, являются независимыми в совокупности, что влечет независимость в совокупности случайных величин е (х' Р') (см. упражнение В.3-5). Из определения математического ожидания Е [Еа(Х<-р;)] Еа(1-р;) ( Е(0-р;) — асн+ ! аР < < р;е + 1 < ехр (р;е ), (В.43) где ехр (х) обозначает экспоненциальную функцию: ехр (х) = е*.
(Неравенство (В.43) следует из того, что о ) О, д! < 1, еаги < еа и е '""' < 1, а последний переход в (В.43) выполнен в соответствии с неравенством (3.11).) Следовательно, и и Е [еа(Х ") ] = П Е [еа(Х' Р*')] < Пехр(р;еа) = 1=1 1=1 = ехр ~~> р;е = ехр (,иеа), 1=1 (В.44) поскольку (з = 2,'," 1 р;. Таким образом, из (В.41), (В.42) и (В.44) мы получаем, что Рг (Х вЂ”,и ) г) < ехр (ре — о г) .
(В.45) Для вычисления выражения Е (еа(х ")] подставим в него полученную формулу для Х вЂ” )1 и получим: Часть Ч!11. Приложения: математические основы 1254 Выбирая о = 1п(т(р) (см. упражнение В.5-7), мы получим: Рг (Х вЂ” р > т) < ехр (ре~"('~л) — т !и (т/р)) = ехр(т — т1п(т(р)) = (т/р)т ( т ) Применяя эту теорему к последовательности п испытаний Бернулли с равной вероятностью успеха, мы получим оценку для правого хвоста биномиального распределения.
Следствие В.9. Рассмотрим последовательность п испытаний Бернулли с равной вероятностью успеха р и неудачи о = 1 — р в каждом испытании. Тогда для т > пр п Рг(Х вЂ” пр > т) = ~~~ 6(1с;и,р) < ( — ) ~=(е+ 1 Доказательство. В соответствии с (В.36), р = Е [Х] = пр. Упражнения * В.5-1.
Что менее вероятно: при бросании симметричной монеты п раз не получить ни одного орла или получить менее п орлов при бросании монеты 4п раз? * В.5-2. Докажите следствия В.б и В.7. * В.5-3. Покажите, что ь-1 т (") '<[,~-с" ь[й;,,л,~-ц) =о для всех а > О и всех О < й < п. * В.5-4. Докажите, что если О < к < пр, где О < р < 1 и д = 1 — р, то * В.5-5.
Покажите, что из условий теоремы В.З следует, что Рг(р — Х >т) < ~ /(п — р) е'1 т а из условий следствия В.9— Рг(пр — Х > >т) < ( — ) т Приложение В. Комбинаторика и теория вероятности 1255 * В.5-6. Рассмотрим последовательность и испытаний Бернулли, в которой в 1-м испытании (г = 1,2,..., и) вероятность успеха равна ро а неудачи— д; = 1 — рь Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов, а и = Е [Х]. Покажите, что для г > О Рг(Х вЂ” и ) г) < е ' /2". аз 2 (указаниьс докажите, что р;еае+ще а~*' < е" /2, а затем следуйте схеме доказательства теоремы В.8, используя это неравенство вместо (В.43).) * В.5-7. Покажите, что правая сторона неравенства (В.45) при выборе гз = 1п (г/р) принимает минимальное значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
