Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 279
Текст из файла (страница 279)
Тогда Х принимает значения из диа- Ь(Ь; 15, 1/3) А 0.25 -~ 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 Рис. В.2. Бииомиааьное распределение Ь(Ь; 15, 11'3), получаемое дда и = 15 испытаний Бериудди, в аажаом из которых вероетность успта составаает р = 1/3. Математическое оиидание данного распредеденив равно пр = 5. назона (0,1,...,п) и для гс = 0,1,...,п Рг (Х = Ц = р~д" ь, (В.34) посюльку имеется („) способов выбрать )с успешных испытаний из и, и вероят- ность каждого составляет р"0" ".
Распределение вероятностей (В.34) называетсл бииомиильньем распределением (Ьшоппа! гйзнтЬп1гоп). Для удобства для биноми- ального распределения используется запись 6(гс;п,р) = рь(1 — р)" ь . (В.35) Пример биномиального распределения показан на рис.В.2. Название "биномиаль- ное" связано с тем, что правая часть формулы (В.34) описывает гс-й член в разло- жении (р + д) . Следовательно, поскольку р + 4 = 1, ~'6(й;,р) =1 ь=о (В.Зб) как того требует вторая аксиома вероятностей. Вычислить математическое ожидание случайной величины, имеющей биномиальное распределение, можно с использованием формул (В.8) и (В.Зб). Пусть Х— случайная величина с биномиальным распределением 6(гс; и, р) и пусть ц = 1 — р. 0.20— 0.15 ) Часть Р1П.
11риеажеиия: матеиатичестге аснаем Лрияожение В. Комбинаторика и теория веааятности !157 Из определения математичесюго ожидания и ~ к Рг(Х = к) а=с ~й ь(й;,р) а=о Е ©'.- .Ф'-')'" н-1 еК[ )е'я'" ' ' а=о а-1 при~к 6(й;п — 1,р) Ьмо Е[Х] = (согласно (В.З)) (согласно (В.36)) .
(В.37) Е[Х] = Е ~Х, н Е [Х;] 1=1 1=1 = пр (В.зй) Тот же подход можно применить и для вычисления дисперсии распределения. Используя уравнение (В.27), получаем Ъах [Хя] = Е [Хз] — Ез [Хе]. Поскольку Х, может принимать только значения О или 1, имеем Кз = Х„откуда Е [Ха] = Е [Х;] = р. Следовательно, Ъаг[Х1] = р — рз = р(1 — р) = ра. (В.39) Используя линейность математического ожидания, можно получить тот же результат с существенно меньшим юличеством выкладок. Пусть Х; — случайная величина, описывающая количество успешных случаев в г-м испытании.
Тогда Е [Х;] = р 1+ о О = р и согласно линейности математического ожидания (уравнение (В.21)) математичесюе ожидание числа успешных испытаний из общего количества п равно Часть еШ. Пртоэкении математические осноеи 115о Для вычисления дисперсии Х воспользуемся независимостью всех и попыток. Тогда в соответствии с (В.2Я) н Чэх[Х] = Чах ") Х, с=1 Чаг (Х,] 1=1 н = ч;рч (В.40) = про Как видно из рис. В.2, функция биномиального распределения 6((с; и, р) растет с ростом 1с до тех пор, пока (с не достигает значения пр, после чего начинает уменьшаться. Мы можем доказать, что биномиальное распределение всегда ведет себя подобным образом, рассматривая отношение двух последовательных членов: ( й п р ) ( ь ) р ~ ч ь 6(ь 1 и р) ( )рь-1 -м~з п)(/с — 1)1(п — й + 1)!р И(п — й))и)д (и — lс + 1)р Ьу = 1+ (и+1)р — й (се (В.4! ) Лемма В.1 Пусть п > О, 0 < р < 1, д = 1 — р и 0 < й < п.
Тогда 6(1с;и,р) < ( — ) ( ) Это отношение больше единицы толью тогда, когда (и + 1)р — й положительно. Следовательно, 6()с; п, р) > Ь(й — 1; п, р) при й < (п + 1)р (функция распределения возрастает) и 6(й;п,р) < 6(И вЂ” 1;п,р) при й > (и + 1)р (функция распределения убывает). Если й = (п + 1)р — целое число, то 6()с;п,р) = 6((с — 1;п,р), так что функция распределения имеет два максимальных значения — при 1с = (и + 1)р и при й — 1 = (и + 1)р — 1 = пр — д.
В противном случае она принимает максимальное значение при единственном целом значении 1с в диапазоне пр — а < й < (п + 1)р. Следующая лемма дает верхнюю оценку биномиального распределения. принижение и Ноибинаторино и теорие вероятности 1259 Доказательсввве. Используя уравнение (В.б), получаем Упражнении В.4.1 Убедитесь в выполнении аксиомы 2 для геометрического распределения. В.4.2 Сколько раз в среднем нужно бросить шесть симметричных монет для получения трех орлов и трех решек? В.4.3 Покажите, что 6(к; и, р) = 6(п — к; и, д), где д = 1 — р. В.4.4 Покажите, что значение максимума функции биномиального распределения 6(к; и, р) приближенно равно 1/~(2хпущ, где д = 1 — р.
В.4.5 * Покажите, что вероятность не получить ни одного успешного исхода в серии из и испытаний Бернулли с вероятностью успеха р = 1/и составляет приблизительно 1/е. Покажите также, что вероятность получения ровно одного успешного исхода также составляет примерно 1/е. В.4.6 * Профессора Однокаменяк и Айнштайн бросают симметричную монету и раз. Покажите, что вероятность того, что они получат одинаковое количество орлов, равна (~„")/4". (Указание: считайте успехом выпадение орла у профессора Однокаменякя„и выпадение решки у профессора Айнштайна.) Воспользуйтесь своей аргументацией для проверки тождества В.4. 7 * Покажите, что для 0 < к < и, Ц5с, и 1/2) < 2лН(Ь/л) — л где Н(з) — энтропийная функция (В.7). !2аО Часть еШ.
Приеаскенине математические аснаеы В.4.8 * Рассмотрим и испытаний Бернулли, где р, — вероятность успеха в (-м испытании для ь = 1, 2,..., и, а Х вЂ” случайная величина, равная общему количеству успехов. Пусть р > р; для всех ( = 1, 2,..., и. Докажите, что для 1 < (с < п /с-1 Рг(Х < (с) > ~~ь Ь(ь;п,р) . В.4.9 * Пусть Х вЂ” случайная величина, равная обшему количеству успехов в множестве А из и испытаний Бернулли, а р, — вероятность успеха в (-м испытании.
Пусть Х' — аналогичная случайная величина, равная общему количеству успехов в множестве А' из и испытаний Бернулли, где р', > р, — вероятность успеха в 1-м испытании. Докажите, что для О < lс < и Рг (Х > Iс) > Рг (Х > Iс) (Укаэаниее покажите, как получить результаты испытаний Бернулли А' из эксперимента, включающего испытания А, а затем воспользуйтесь результатом упр. В.З.7.) * В.б. Хвосты биномнялъного распределения Зачастую во многих задачах требуется определить не вероятность того, что в и испытаниях Бернулли будет получено ровно )с успешных исходов, а вероятность того, что будет получено не более (или не менее) (с успешных исходов.
В этом разделе мы рассмотрим хвасаем (лайз) биномиального распределения, т.е, области распределения Ь((с; и, р), далекие от среднего значения пр, и найдем некоторые важные оценки для них. Мы рассмотрим правый хвост распределения Ь((с; п,р); левый хвост получается при простой взаимной замене успешных исходов неудачами. Теорема В.2 Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов.
Тогда для О < Ь < и вероятность того, что будет получено как минимум Iс успешных исходов, равна !26! Прияояееиие В. Каибииаториеа и теория вероятиоети Доказательство. Для множества Я С (1,2,...,и) обозначим через АВ событие, которое заключается в том, что (-я попытка успешна для всех ( б Я. Понятно, что если (Я~ = (е, то Рг (АВ! = рь. Имеем Рг (Х > Ц = Рг (существуег Я С (1, 2,..., п): !Я/ = )е и АВ) =Рг Ц АВ1 т Вс(кгб..,и):д=ь ! Рг (АВ! (согласно (В.19)) ВС(дг,,иЦВ~=Ь Приведенное далее следствие просто переформулирует эту теорему для левого хвоста бнномиального распределения.
Все доказательства переформулированных таким образом (для противоположного хвоста) теорем далее в этом приложении предлагаются читателю в качестве самостоятельного упражнения. Следствие В.З Рассмотрим последовательность из п испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов.
Тогда для О < к < п вероятность того, что будет получено не более к успешных исходов, равна Рг(Х < Ц = ~~ Ь(е;п,р) =а < "„(1-р)и-ь =("„)~ -.)' Следующая рассматриваемая оценка относится к левому хвосту биномиального распределения. Следствие из нее демонстрирует, что вдалеке от среднего значения левый хвост уменьшается экспоненциально. Теорема В.4 Рассмотрим последовательность из п испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, н вероятностью неудачи, равной д = 1 — р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов. Тогда для О < к < пр вероятность того, что будет получено менее (е Часть И11. Лрипоенение; математичесене основы 1сбс успешных исходов, равна Рг(Х < Ц = ~~~ 6(ъ';п,р) с=с < В 6(гс;п,р) .
йд пр — й 6(1 — 1; п, р) (и — 1 + 1)р ЗО (и — 1)р ~Ч (и — гс)р 6(ь'; и, р) Если положим (и — Й)р ЬЧ (и — пр)р ЬЧ пдр й пр 1, то получим Ь(1 — 1;п,р) < хЬ(г;п,р) для 0 < 1 < /с. Итеративно применив зто неравенство й — г' раз, получим 6(1;п,р) < х~ '6(й;п,р) для 0 < 1 < й, а следовательно, < ~~ х '6(й;п,р) Г=О < 6(/с,п,р) Ь х Ь(ь; и, р) Г=О Декаэавгевьсвгео. Ограничим ряд 2,',, О 6(г';п,р) геометрическим рядом с ней †пользованием методики из раздела А.2, с. 1204. Для 1 = 1,2,...,Й из уравнения (В.41) имеем 33б3 Прияоааение В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
