Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 278
Текст из файла (страница 278)
раздел 5.2). Если Х вЂ” произвольная случайная величина, то любая функция д(х) определяет новую случайную величину д(Х). Если математическое ожидание этой величины определено, то Е[д(Х)] = у д(х) Рг(Х = х) х Пусть д(х) = ах. Тогда для любой константы а Е[аХ] = аЕ[Х] (В.22) Следовательно, математическое ожидание представляет собой линейную функцию: для любых двух произвольных случайных величин Х и У и произвольной константы а Е[аХ+ У] = аЕ[Х]+Е[У] (В.23) "В стечсстаенной математической литературе Лля математического омннаянл принято обозначение М(Х) — Примеч ред. Припожение В.
Коибинаторина и теория вероятности 1151 Если случайные величины Х и У независимы и каждая имеет определенное математическое ожидание, то Е[ХУ] = ~~~ ~~~ ху Рг(Х = х и У = у) ~~) ху Рг(Х = х) Рг(У = у) х Рг(Х=х) ~ у Рг(У=у) = Е[Х]Е[У] В общем случае, если имеется и независимых в совокупности случайных величин Хг,хз,...,Хо, то е[х,х," х„] =е[х,]е[х,]" е[х„] . (В.24) Если случайная величина Х принимает значения из множества неотрицательных целых чисел Ы = (О, 1, 2,...), то для ее математического ожидания имеется красивая формула Е[Х] = ~ ~г Рг(Х =1) *=о ся,) г(Рг (Х > г) — Рг (Х > 1+ 1)) =о Рг(Х > г), 1=1 (В.25) поскольку каждый член Рг (Х > 1) присутствует в сумме со знаком "плюс" г раз и со знаком "минус" — г — 1 раз (за исключением члена Рг (Х > 0), отсутствующего в сумме).
При применении выпуклой вниз функции 1(х) к случайной величине Х неравенство еяенсона ()елзеп'а 1пецпа111у) гласит Е[/(Х)] > /(Е[Х]) (В.2б) в случае, когда математическое ожидание существует и конечно. Функция /(х) называется вынуклой аннз (солчех), если для всех х и у и всех 0 < Л < 1 выполняется неравенство /(Лх+ (1 — Л)у) < Л1 (х) + (1 — Л)1 (у).
Дисперсия и стандартное отклонение Математическое ожидание случайной величины ничего не говорит о том, насколько сильно "разбросаны" ее значения. Например, если есть случайные величины Х и У, такие, что Рг (Х = 1/4) = Рг (Х = 3/4) = 1/2 и Рг (У = 0) = Часть Л!1. Прмеомсениет математические основы 1151 Наг [Х] = Е [(Х вЂ” Е[Х])г| = Е [Х вЂ” 2ХЕ[Х]+ Е [Х]] = Е [Хг| — 2Е [ХЕ [Х]]+ Ег [Х] Е [Хг1 2Ег [Х] + Ег [Х] = Е [Хг] — Е' [Х] . (В.27) Чтобы пояснить равенство Е [Ег [Х]] = Ег [Х], заметим, что, поскольку Е [Х] является действительным числом, а не случайной переменной, это значение просто равно Ег [Х]. Равенство Е [ХЕ [Х]] = Ег [Х] следует из уравнения (В.22) при а = Е [Х]. Переписав уравнение (В.27), мы получим выражение математического ожидания квадрата случайной величины: Е [Х~~] = Наг [Х] + Ег [Х] (В.28) Дисперсия случайной величины Х связана с дисперсией случайной величины ах следующим соотношением (см.
упр, В.3.10); Ъ'ах [ах] = агЪ'ах [Х] Если Х и У вЂ” независимые случайные величины, то Ъ'аг [Х+ У] = Нах [Х]+ Ъ'ах [У] В общем случае, если п случайных величин Х1, Хг,..., Х„попарно независимы, то и п Ъ'аг у Х, = у Нах [Х,] т=1 т=1 (В.29) Стандартным отклонением (азапбагб бео)азюп) случайной величины Х называется неотрицательный квадратный корень дисперсии Х. Иногда стмщартное отклонение Х обозначают как ох или, если случайная величина очевидна из контекста, просто как о. При использовании этого обозначения дисперсия Х записывается как ог. В отечественной математической литературе для дисперсии принято обозначение Р1Х( — примеч. ред Рг (У = 1) = 1/2, то их математические ожидания равны 1/2, однако реальные значения У находятся дальше от математического ожидания этой случайной величины, чем в случае Х.
Понятие дисперсии случайной величины математически выражает отклонение значений случайной величины от среднего значения. Дисперсия случайной величины Х с математическим ожиданием Е [Х] определяется какб Принтмение В. Комбинаторика и теория вероятности 1253 Упражнении ВЗ.1 Предположим, что бросаются две обычные шестигранные игральные кости.
Чему равно математическое ожидание суммы выпавших очков? Чему равно математическое ожидание максимального из двух выпадающих чисел? В.3.2 Массив А[1 .. и[ содержит и различных чисел в произвольном порядке; все перестановки чисел равновероятны. Чему равно математическое ожидание индекса максимального элемента массива? Чему равно математическое ожидание индекса минимального элемента массива? В.З.З Игрок ставит доллар на одно из чисел от 1 до 6 и выбрасывает одновременно трн игральные кости.
Если указанное число не выпало ни на одной из костей, игрок теряет свой доллар; если же число выпало на к костях, игрок сохраняет свой доллар и получает дополнительно и долларов. Чему равно математическое вкидание выигрыша игрока в одной партии? В.Зс4 Докажите, что если Х и У вЂ” неотрицательные случайные величины, то Е [шах(Х,У)[ < Е[Х)+ Е[У[ . В.3.5 * Пусть Х и У вЂ” независимые случайные величины. Докажите, что 1(Х) и д(У) независимы прн любом выборе функций 3 и д.
ВЗ.6 * Пусть Х вЂ” неотрицательная случайная величина, и математическое ожидание Е [Х[ вполне определено. Докажите иеравелство Маркова Рг(Х > б) ( Е[Х[/~ (В.ЗО) для всех й > О. В.З. 7 * Пусть Я вЂ” пространство выборок, а Х и Х' — случайные величины, такие, что Х(в) > Х'(в) для всех в Е Я. Докажите, что для произвольной действительной константы 8 Рг(Х > б) > Рг(Х' > 1) В.З.8 Что больше — математическое ожидание квадрата случайной величины или квад- рат ее математического ожидания? 1е54 Часть рШ. Приаажеиик математические аскаем В.З.9 Покажите, что для любой случайной величины Х, которая принимает только значения О и 1, справедливо соотношение Ъ'ах[Х] = Е[Х] Е[1 — Х] В.ЗЛО Докажите, используя определение дисперсии (В.27), что Чвх [аХ] = а~Ъ'ах [Х] В.4. Геометрическое и биномиальное распределении Бросание симметричной монеты — пример пспьппапая Бернулли (Вепюп!!! пта!), которое определяется как эксперимент с двумя возможными исходами— успехам с вероятностью р и неудачей с вероятностью д = 1 — р.
Когда речь идет об испытаниях Бернулли, то подразумевается, что испытания независимы в совокупности и (если явно не оговорено иное) что вероятность успеха в каждом испытании равна р. С испытаниями Бернулли связаны два важных распределения вероятностей: геометрическое н биномиальное. Геометрическое распределение Предположим, что имеется последовательность испытаний Бернулли, вероятность успеха в каждом из которых равна р, а вероятность неудачи — д = 1 — р.
Сколько испытаний будет проведено до того, как будет достигнут успех? Пусть случайная величина Х равна количеству испытаний, необходимых для достижения успеха. Тогда Х принимает значения из диапазона (1, 2,... ! и для !с > 1 Рг (Х = Ц = д~ 'р, (В.31) поскольку перед наступлением одного успешного испытания было выполнено !с — 1 неудачных. Распределение вероятности, удовлетворяющее уравнению (В.31), называется геометрпческам распределением (йеошепзс 41з~пЪпг(оп). На рис.В.! показан пример такого распределения. Полагая, что д < 1, можно найти математическое ожидание геометрического распределения, воспользовавшись тождеством (А.8): Е[Х] = ~ ~ад~ 'р а=1 Р ~;" й ь ч а=о Привоэсвнив д Каиоиноморика и нмория вврсюяностн ©" '(~) О.З5— о.з5,,'с1;-, 045 -~";":-' ~4„.„, ".:::-:::::::::::!:::::::-:::::::::::'::::":::~~!':::тим.
тп, т т | | | | | 'Й | '|| й || || и ||— Рнс. В.1. Геометрическое распрсдслснис с вероятностью успоко р = 1/3 и вероятностью нсудачи Е = 1 — р, Математическое ониданнс распределения равно 1/р = 3. Р Я я (1 — а)з Р й я рз = 1/р. (В.З2) Таким образом, в среднем нужно выполнить 1/р испытаний до достижения успеха (что интуитивно представляется вполне естественным).
Дисперсия вычисляется аналогично, с использованием результата упр. А.1.3, и равна Уаг(Х] = и/р (В.ЗЗ) В качестве примера рассмотрим бросание двух кубитюв до тех пар, пока не будет получено 7 или 11 очков. Из 36 возможных исходов бросания 6 дают 7 очков, и 2 дают 11. Таким образом, вероятность успеха равна р = 8/Зб = 2/9, так что в среднем необходимо бросить кости 1/р = 9/2 = 4.6 раза для того, чтобы выпало 7 или 11 очков. Биномиальиое распределение Какое кпличеспю из и испытаний Бернулли завершится успешно, если вероятность успеха равна р, а неудачи — д = 1 — р7 Определим случайную величину Х как количество успехов в и испытаниях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
