Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 258
Текст из файла (страница 258)
Докажите неравенство Маркова Рг(Х > й) < Е[Х]/1 для всехг> О. (В.29) * В.З-?. Пусть Я вЂ” пространство событий, а Х и Х' — случайные величины, такие что Х (в) > Х' (в) для всех в Е Я. Докажите, что для произвольной действительной юнстанты г Рг (Х > г) > Рг (Х' > г). В.3-8. Что больше — математическое ожидание квадрата случайной величины или квадрат ее математичесюго ожидания? В.3-9. Покажите, что для любой случайной величины Х, которая принимает только значения 0 и 1, справедливо соотношение Чаг[Х] = Е[Х] Е[1 — Х] . В.3-10.
Докажите, используя определение дисперсии (В.26), что Чаг[аХ] = аз Чаг [Х]. В.4 Геометрическое и биномиальное распределения Бросание симметричной монеты — пример испытания Бернулли (Ветлой!1 пта1), которое определяется как эксперимент с двумя возможными исходами— 1244 успехам с вероятностью р и неудачей с вероятностью д = 1 — р. Когда мы говорим об испытаниях Бернулли, то подразумевается, что испытания независимы в совокупности и (если явно не оговорено иное) что вероятность успеха в каждом испытании равна р. С испытаниями Бернулли связаны два важных распределения вероятностей: геометрическое и биномиальное. Геометрическое распределение Предположим, что у нас есть последовательность испытаний Бернулли, вероятность успеха в каждом из юторых равна р, а неудачи — о = 1 — р.
Сюлько испытаний будет проведено до того, как будет достигнут успех? Пусть случайная величина Х равна количеству испытаний, необходимых для достижения успеха. Тогда Х принимает значения 11, 2,...) и для к > 1 Рг (Х = Ц = д~ 1р, (В.ЗО) поскольку перед наступлением одного успешного испытания было выполнено к — 1 неуспешных. Распределение вероятности, удовлетворяющее уравнению (В.ЗО), называется геометрическим распределением (яеоте!г(с йзпзЬп!(оп).
На рис. В.! показан пример такого распределения. г ь 7 ~ з 'О н ~ н н !' Рис. В.1. Геометрическое распределение с р = 1/3 ) ои -~ 1 ;.,~ О Часть Ч!!!. Приложения: математические основы Приложение В. Комбинаторика и теория вероятности 1245 Полагая, что д < 1,можно найти математическое ожидание геометрического распределения, воспользовавшись тождеством (А.8): Е [Х[ = ,') йд~ 'р = — ,') )сд" = — = †.
(В.31) ~ а=о ~ (1 ч) Таким образом, в среднем нужно выполнить 1/р испытаний до получения успеха (что интуитивно представляется вполне естественным). Дисперсия вычисляется аналогично, с использованием результата упражнения А.1-3, и равна Чаг [Х) = д/рз. (В.32) В качестве примера рассмотрим бросание двух кубиков до тех пор, пока мы не получим 7 или 11 очков. Из Зб возможных исходов бросания б дают нам семь очков, и 2 — одиннадцать. Таким образом, вероятность успеха равна р = 8/36 = = 2/9, так что в среднем нам надо выбросить кости 1/р = 9/2 = 4.5 раза для того, чтобы выпало 7 или 11 очков. Биномиальное распределение Какое количество из и испытаний Бернулли завершится успешно, если вероятность успеха равна р, а неудачи — д = 1 — р7 Определим случайную величину Х как количество успехов в и испытаниях. Тогда Х принимает значения 10, 1,..., и) и для О < й < и Рг(Х = Ц = р о (В.ЗЗ) поскольку существует [ь) способов выбрать й успешных испытаний из и, и вероятность каждого составляет р" д" ь.
Распределение вероятностей (В.ЗЗ) называется биномиальным раснределением (Ь(полна! сйзгг1Ьшюп). Для удобства для биномиального распределения используется запись 6(й;п,р) = р (1 — р) (В.34) Пример биномиального распределения показан на рис. В.2. Название "биномиальное" связано с тем, что формула (В.ЗЗ) описывает й-й член в разложении (р + д)". Следовательно, поскольку р+ д = 1, (В.35) как того требует вторая аксиома вероятностей. Часть ЧП!. Приложения: математические основы 1246 ! Ы.!5,ЬЛ 4 В 15 К' -1 1~' гзв -] Взл -] 5 Ф 5 6 ",* З З !0 П П И И И Рис. В.2. Биномивльное распределение Ь (к; 15, 1/3) Вычислить математическое ожидание случайной величины, имеющей биномиальное распределение, можно с использованием формул (В.8) и (В.35).
Пусть Х вЂ” случайная величина с биномиальным распределением Ь()е;п,р), и пусть д = 1 — р. По определению математического ожидания, 1е Рг (Х = Ц = в=о и Ейьяп,р) = в=о т ~(");- = .Ф:-') "'= и-1 ч К( )~ю'" " в=о и-1 пр ~1 Ь (Iс; т1 — 1, р) = пр в=о Е[Х] = (В.Зб) Используя линейность математического ожидания, мы можем получить тот же результат с существенно меньшим количеством выкладок.
Пусть Х; — случайная величина, описывающая количество успешных случаев в т-м испытании. Тогда Приложение В. Комбинаторика н теория вероятности 1247 Е [Х,] = р. 1+ д 0 = р и, согласно линейности математического ожидания (урав- нение (В.20)), математическое ожидание числа успешных испытаний из общего количества н равно и и в Е[Х] = Е ~~~ Х; = ~~~ Е[Х;] = ~р= пр. в=1 1=1 1=1 (В.37) Такой же подход можно применить и для вычисления дисперсии распределения. Используя уравнение (В.26), получаем Чаг [Х;] = Е [Х8] — Ез [Х;]. Поскольку Х; может принимать только значения 0 или 1, имеем Е [Х8] = Е [Х;] = р, следовательно Чаг [Х;] = р — рз = рд.
(В.38) Для вычисления дисперсии Х воспользуемся независимостью всех и попыток. Таким образом, в соответствии с (В.28), и п и Уаг [Х] = тат '~ Х; = ~~ 'тат [Х,] = Ярд = пру. (В.39) 1=1 1=1 1=1 Как видно из рис. В.2, функция биномиального распределения Ь (1с; п, р) растет с ростом /с до тех пор, пока Й не достигает значения пр, после чего начинает уменьшаться. Мы можем доказать, что биномиальное распределение всегда ведет себя подобным образом, рассматривая отношение двух последовательных членов: Ь (Й; и, р) (ь)р д" Ь(~„- 1,п р) ( ~~ )рь-1ди — ь+1 ей ()с — 1)! (и — к + 1)! р Й! (и — Й)Ыд (и — к+ 1) р кд (и+ 1) р — к =1+ йй (В.40) Это отношение больше 1 тогда и только тогда„когда (и + 1) р — к положительно. Следовательно, Ь(к;п,р) > Ь(к — 1;п,р) при /с < (и+ 1) р (функция распределения возрастает) и Ь(к;п,р) < Ь(lс — 1; п,р) при /с > (и+ 1) р(функция распределения убывает).
Если к = (и + 1) р — целое число, то Ь (к; п, р) = Ь (Ь вЂ” 1; п, р) и функция распределения имеет два максимальных значения — при Й = (и+ 1) р и при к — 1 = (и + 1) р — 1 = пр — д. В противном случае она приминает максимальное значение при единственном целом значении Й в диапазоне пр — д < й < < (о+1) р. Следующая лемма дает верхнюю оценку биномиального распределения.
Часть Ч111. Приложения: математические основы 1248 Лемма В 1. Пусть и ) О, О < р < 1, д = 1 — р и О < Й < и. Тогда Доказательство. Используя уравнение (В.б), получаем: Упражнения В.4-1. В.4-2. В.4-3. В.4-4. * В.4-5. * В.4-6. * В.4-7. Покажите, что при О < й < и 1/2) < 2ьНО/ь1-и где Н (х) — энтропийная функция (В.7). Убедитесь в выполнении аксиомы 2 для геометрического распределения. Сколько раз в среднем надо бросить б симметричных монет для получе- ния трех орлов и трех решек? Покажите, что Ь (?с; и, р) = Ь (и — й; и, д), где д = 1 — р. Покажите, что максимальное значение функции биномиального распре- деления Ь (Й; 7т, р) приближенно равно 1/т/7япрд, где д = 1 — р. Покажите, что вероятность не получить ни одного успешного исхода в се- рии из и испытаний Бернулли с вероятностью успеха р = 1/тт составляет приблизительно 1/е. Покажите также, что вероятность получения ровно одного успешного исхода также составляет примерно 1/е.
Профессора Ванстоун и Унопетри бросают симметричную монету п раз. Покажите, что вероятность того, что они получат одинаковое количе- ство орлов, равна (~„")/4". (Указание: считайте успехом выпадение орла у профессора Ванстоуна, а у профессора Унопетри — выпадение решки.) Воспользуйтесь вашей аргументацией для проверки тождества Приложение В. Комбинаторика н теория вероятности 1249 * В.4-8. Рассмотрим и испытаний Бернулли, где р; — вероятность успеха в 1-м испытании, а Х вЂ” случайная величина, равная общему количеству успехов.
Пусть р > р, для всех 1 = 1, 2,..., п. Докажите, что для 1 < /с < и Рг(Х < Ц > ,'~ Ь(г;п,р). * В.4-9. Пусть Х вЂ” случайная величина, равная общему количеству успехов в множестве А из и испытаний Бернулли, а р; — вероятность успеха в 1-м испытании. Пусть Х' — аналогичная случайная величина, равная общему количеству успехов в множестве А' из и испытаний Бернулли, где р', > р; — вероятность успеха в 1-м испытании. Докажите, что для 0<Ь<п Рг(Х' > Ц > Рг(Х > й) . (Указание: покажите, как получить результаты испьпаний Бернулли А' из эксперимента, включающего испытания А, а затем воспользуйтесь результатом упражнения В.3-7.) * В.5 Хвосты биномиального распределения Во многих задачах требуется определить не вероятность того, что в и испытаниях Бернулли будет получено ровно к успешных исходов, а вероятность того, что будет получено не более (или не менее) й успешных исходов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
