Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.), страница 259

В этом разделе мы рассмотрим хвостом (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п (г/р) принимает минимальное значение. Задачи В-1. Шары и корзины В этой задаче мы рассмотрим размещение и шаров по б различным корзинам. а) Предположим, что все и шаров различны, а их порядок в корзине не имеет значения.

Докажите, что имеется о" способов разместить шары в корзинах. б) Предположим, что все п шаров различны, а их порядок в юрзине существенен. Докажите, что имеется ровно (б+ п — 1)!/(б — 1)! способов размещения шаров в корзинах. (Указанигс подсчитайте количество способов разместить в ряд и различных шаров и 6 — 1 неразличимых разделителей.) в) Предположим, что все шары идентичны, а следовательно, их порядок в корзине не имеет значения. Покажите, что количество способов, юторыми можно разместить шары в корзинах, равно ( +"„'). (Указанигс воспользуйтесь тем же способом, что и в части б, только теперь шары также неразличимы.) г) Покажите, что если шары идентичны, и ни в одной корзине не может находиться больше одного шара, то разместить шары в корзинах можно („) способами. д) Покажите, что если шары идентичны и ни одна корзина не должна остаться пустой, то разместить шары в корзинах можно (" ) способами.