Алгоритмы - построение и анализ (1021735), страница 257
Текст из файла (страница 257)
(В.2б) В процессе вывода использованы равенства Е [Ез [ХЦ = Ез [Х] и Е [ХЕ[Х]] = = Ез [Х], которые вполне корректны, поскольку математическое ожидание Е [Х] является просто действительным числом, а не случайной величиной, так что мы можем воспользоваться формулой (В.21). Уравнение (В.26) можно использовать для поиска математического ожидания квадрата случайной величины: Е [Хзз] = Чаг[Х]+ Е [Х]. (В.27) Дисперсия случайной величины Х связана с дисперсией случайной величины аХ следующим соотношением (см. упражнение В.3-10): Чаг[аХ] = а Чаг[Х]. Если Х и У вЂ” независимые случайные величины, то Чаг[Х+У] = Чаг[Х]+Чаг[У]. В общем случае, если тз случайных величин Х1, Хз,..., Х„попарно независимы, Чаг ) Х; = ~к Чаг [Х,]. 1=1 1=1 (В.28) В отечественной математической литературе для дисперсии принято обозначение 11 [Х].— Прим, ред.
Стандартным отклонением (агапе(ап1 беу]аг]оп) случайной величины Х называется неотрицательный квадратный корень дисперсии Х. Иногда стандартное отклонение Х обозначают как ох или, если случайная величина очевидна из контекста, просто ст. При использовании этого обозначения дисперсия Х записывается как сгз. Приложение В. Комбинаторика и теория вероятности 1243 Упражнения В.3-1. Бросаются две обычные шестигранные игральные кости. Чему равно математическое ожидание суммы выпавших очков? Чему равно математическое ожидание максимального из двух выпадающих чисел? В.3-2.
Массив А[1..п] содержит п различных чисел в произвольном порядке; все перестановки чисел равновероятны. Чему равно математичесюе ожидание индекса максимального элемента массива? Чему равно математическое ожидание индекса минимального элемента массива? В.З-З. Игрок ставит доллар на одно из чисел от 1 до 6 и выбрасывает одновременно три игральные юсти. Если указанное число не выпало ни на одной из костей, игрок теряет свой доллар; если же число выпало на Й костях, игрок сохраняет свой доллар и получает дополнительно к долларов.
Чему равно математическое ожидание выигрыша игрока в одной партии? В.3-4. Покажите, что если Х и г — неотрицательные случайные величины, то Е [пзах (Х, )')] < Е [Х] + Е [У]. * В.3-5. Пусть Х и г — независимые случайные величины. Докажите, что У (Х) и д (г ) независимы при любом выборе функций г" и д. * В.3-6. Пусть Х вЂ” неотрицательная случайная величина, и математическое ожидание Е [Х] вполне определено. Докажите неравенство Маркова Рг(Х > й) < Е[Х]/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 ;.,~ О 1 )'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 (В.37) Такой же подход можно применить и для вычисления дисперсии распределения. Используя уравнение (В.26), получаем Чаг [Х;] = Е [Х8] — Ез [Х;]. Поскольку Х; может принимать только значения 0 или 1, имеем Е [Х8] = Е [Х;] = р, следовательно Чаг [Х;] = р — рз = рд.
(В.38) Для вычисления дисперсии Х воспользуемся независимостью всех и попыток. Таким образом, в соответствии с (В.28), и п и Уаг [Х] = тат '~ Х; = ~~ 'тат [Х,] = Ярд = пру. (В.39) с=1 с=1 с=1 Как видно из рис. В.2, функция биномиального распределения Ь (!с; п, р) растет с ростом lс до тех пор, пока Й не достигает значения пр, после чего начинает уменьшаться.
Мы можем доказать, что биномиальное распределение всегда ведет себя подобным образом, рассматривая отношение двух последовательных членов: Ь (Й; и, р) (ь)р д" Ь(~„- 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". (Указание: считайте успехом выпадение орла у профессора Ванстоуна, а у профессора Унопетри — выпадение решки.) Воспользуйтесь вашей аргументацией для проверки тождества Приложение В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
