Д. Кнут - Искусство программирования том 1 (1119450), страница 29
Текст из файла (страница 29)
Распределение, соответствующее произведению двух таких производящих функций, называется сверткой двух соответствующих распределений и представляет собой распределение суммы двух независимых случайных величин, имеющих распределения, соответствующие перемножаемым производящим функциям. Среднее значение случайной величины Х часто называют ее математическим оогсиданием и обозначают через Е Х. Тогда дисперсия случайной величины Х равна ЕХ2 — (ЕХ)г. В этих обозначениях производящая функция, соответствующая распределению случайной величины Х, имеет вид С(г) = Егх, т.
е. представляет собой математическое ожидание случайной величины г~, если Х принимает только целые неотрицательные значения. Аналогично, если Х вЂ” утверждение, которое либо истинно, либо ложно, вероятность того, что Х истинно, равна Рг(Х) = Е(Х) согласно обозначению Айверсона (см. 1.2.3-(16)). Среднее и дисперсия — это просто два так называемых семиинварианта или кумуяянта, введенных Тиеле (ТЬ!е1е) в 1903 году. Семиинварианты кы кг, кг,...
определяются правилом в частности, е'С'(е') ~ С(е') $ с=с так как С(1) = ~ г р1 = 1, и ег~Св( ~) с~С~(е~) ггС|(е~)г С(е') С(е') С(е')т !а=с Поскольку семиинварианты определяются с помощью логарифма производящей функции, теорема А очевидна; фактически ее можно обобщить, распространив на все семнинварианты. Нормальное распределение — зто такое распределение, для которого все семи- инварианты, за исключением среднего и дисперсии, равны нулю Для нормального распределения можно значительно улучшигь неравенство Чебышева, вероятность того, что разница между значением нормально распределенной случайной величины и средним меньше среднего квадратичного отклонения, равна вз — е ~ ~!е, Рг(Х < г) < х "С(х) Рг(Х > г) < х "С(х) дляО<х<1; для х > 1.
(24) (25) Доказать эти формулы несложно. Если С(г) = ре+ р1г+ рггз +, то Рг(Х < г) = рс+р1 + +р!,! < х "рс+х1 "р1 + ° +х!"! 'р!и! < х "С(х) приО<х<1и Рг(Х>г)=р!1+р;„1ч.1+ ° .<х(1 р1„1+х!")ч1 "р!1 1+ <х "С(х) при х > 1. Выбирая такие значения х, которые минимизируют или приближенно минимизируют правые части неравенств (24) и (25), можно получить оценки сверху, достаточно близкие к истинным значениям вероятностей слева.
В упр. 21-23 неравенства (24) и (25) проиллюстрирован(я для нескольких важных случаев. Эти неравенства являются частными случаямй более общего закона, на который указал А. Н. Колмогоров (А. 7з. Ко!шойогог) в и4зиге Стиле)ЬеуНе с(ег Кайгесйе!и!!с)1)се7сегесйпип8 (Бргшйег, 1933): если ! (!) > е > 0 для всех ! > г, то т. е. приблизительно 0.68268949213709. Вероятность, что эта разница меньше удвоенного среднего квадратичного отклонения, приблизительно равна 0.95449973610364, и вероятность того, что опа меньше, чем утроенное среднее квадратичное отклонение, примерно равна 0 99730020393674. Распределения, заданные соотношениями (8) и (18), приблизительно нормальны при больших значениях и (см.
упр. 13 и 14), Часто возникает необходимость убедиться в том, что вероятность большого отклонения случайной величины от ее среднего достаточно мала. Удобные оценки таких вероятностей дают две чрезвычайно простые, но очень важные формулы, которые называются неравенсшвами длл хвостов распределений. Если С(г) — вероятностная производящая функция случайной величины Х, то Рг(Х > т) < з ' Е7(Х) при условии, что существует Еу(Х) Неравенство (25) можно получить для у(1) = х' и з = х" УПРАЖНЕНИЯ 1.
[10) Найдите значение р„о из соотношений (4) и (5) и дайте интерпретацию этой вероятности в свете алгоритма М 2. [НМ1 б] Выведите (13) из (10). 3. [М!5] Чему будут равны минимум, максимум, среднее и среднее квадратичное отклонение для числа выполнений шага М4, если для нахождения максимума среди 1 000 случайно упорядоченных различных величин воспользоваться алгоритмом М ' (Дайте ответ в виде десятичных дробей.) 4.
[М10] Дайте в явном виде формулу для р„з из задачи о бросании монеты (см. соотношение (17)) б. [М?Э] Чему равны среднее и среднее квадратичное отклонение для распределения, показанного на рис 11о 6. (НМ37] Мы вычислили среднее и дисперсию для важных распределений вероятностей (8), (18), (20). Чему равен треской семиинвариант, кз, в каждом нз этих случаев? ° 7.
[МЙ7] Анализируя алгоритм М, мы предполагали, что все Х[(е] были различны. Теперь сделаем более слабое предположение, а именно — что среди Х(1], Х(2], . Х[п) содержится ровно т различных значений; в других отношениях эти величины случайны. Каким будет распределение вероятностей для А в этом случае? ° 8. [М80] Предположим, что каждое Х[Ц выбирается наугад из множества М различных элементов, так что все М" возможных вариантов выбора элементов Х(1], Х[2],...,Х[п] считаются равновероятными.
Чему равна вероятность того, что все Х[5] будут различны? 9. [Мйб] Обобщите результат предыдущего упражнения и найдите формулу для вероятности того, что среди Х[5] окажется ровно т различных величин. Выразите эту вероятность с помощью чисел Стирлинга 10. [МЙО] С помощью результатов трех предыдущих упражнений выведите формулу для вероятности того, что А = )е, при условии, что каждое Х[?с] выбирается наугэд из М- элементного множества. ° 11.
[М?5] Что произойдет с семиинвариантами распределения, если заменить функцию сЗ(з) функцией Р'(х) = з" С(з)? 12. [НМ81] Если С(з) = ро+рзз+рзз~+ ° соответствует некоторому распределению вероятностей, то величины М„= 2' ,?с"рз и т„ю 2 „(?с — Мз)"рз называются и-м моментом и п-м центральным моментом соответственно, покажите, что б(е') = 1+ мз с+ ма с~/2'+ С помощью формулы Арбогаста (см. упр, 1.2.5-21) докажите, что ( — 1)ь'Яззь эз" ~п! (?сз + йз+ + йо — 1)) з, ь )ез! 1ич?сз(2Вз...?с„[п!з счдз,,з йо зз "езьзо о В частности, к, ю Мн кз = Мз — Мз (как мы уже знаем), кз = Мз — ЗМ~Мз + 2М, и к4 = М4 — 4МзМз+12МззМз — ЗМзз — 5Мзз Найдите аналогичное выражение для к„через центральные моменты тз, тз,, где и > 2 13. [НМЭЭ] Говорят, что последовательность распределений вероятностей, соответствующих производящим функциям Со(з) со средними до и средними квадратичными отклонениями с„, стремится к нормальному распределению, если — !» /»„й ( г/» ) -!г/г ~0 для всех действительных значений й Пусть С (е) задается формулой (8).
Покажите, что распределение, соответствующее С (г), стремится к нормальному распределению. Замечание. Можно показать, что данное здесь определение стремления к нормютьному распределению эквивалентно следующей формуле: /Х. — р» ! 1 /* Н/, !гш вероятность ~ < х/! ю — / е / 81, -!»» — !,2л/ „ где Л» — случайная величина, распределение вероятностей которой задается с помощью С„(г). Это частный случай важной "теоремы непрерывности" П. Леви (Р.
Ъбчу), которая является одним из основных результатов математической теории вероятностей. Доказательство теоремы Леви выходит за рамки данной книги, хотя оно не такое уж сложное [см., например, книгу Б. В. Гнеденко и А. Н. Колмогорова, Предельные распределения для сумм независимых случайных величин (Мс Гостехиздат, 1949)]. 14. [НМ80] (А. де Муавр.) Пользуясь обозначениями из предыдущего упражнения, покажите, что биномиальное распределение С»(е), заданное формулой (18), стремится к нормальному распределению. 18. [НМЯ8] Если вероятность того, что некоторая случайная величина принимает значение /г, равна е»(р~//г!)», то говорят, что она имеет распределение Пуассона со средним р. а) Найдите производящую функцию для этого распределения вероятностей, Ъ) Найдите значения семиинвариантов.
с) Покажите.что при и †! со распределение Пуассона со средним пр стремится к нормальному распределению в смысле упр. 13. 18. [Мдд] Пусть распределение случайной величины Х является смесью распределений, порожденных функциями дг(г), дг(с),, д,(г), в том смысле, что распределение Х с вероятностью ре совпадает с распределением случайной величины, соответствующей производящей функции де(г), где р!+рг л- +р. = 1. Найдите производящую функцию для Х Выразите среднее н дисперсию Х через средние и дисперсии дг, дг, ..., д„. ь 17.
[М87] Пусть /(г) и д(г) — производящие функции, которые соответствуют некоторым вероятностным распределениям. а) Покажите, что /г(г) = д(/(г)) — тоже производящая функция, соответствующая некоторому вероятностному распределению. Ъ) Дайте интерпретацию /г(г) в терминах /(г) и д(г). (Каков смысл вероятностей, заданных коэффициентами разложения Цг)?) с) Выразите среднее и дисперсию Ь через средние и дисперсии / и д. 18.
[М88] Предположим, что величины, которые мы обозначили через Л [1], Х[2],..., Х[п] в описании алгоритма М, содержат ровно 8! единиц, йг двоек, ..., 8» чисел и, расположенных в случайном порядке. (Здесь /г! + /гг + ' ' ' + л» = п. В тексте предполагалось, что /г! = йг = = й = 1.) Покажите, что в этой более общей ситуации производящая функция (8) будет иметь вид если принять, что О/О = 1.
* и > 0 -- Прим. ред. 19. (МИ] Если аэ > аз для 1 < 1 < Ь, будем говорить, что ໠— это максимум слева направо последовательности а~ аэ .. а . Предположим, что а~ а» ... а„— это перестановка чисел (1,2,, и), и 6, 6» ... ܄— обратная перестановка, так что а» = ! тогда и только тогда, когда 6| = Ь, Покажите, что а» является максимумом слева направо последовательности а~ аэ .. а„тогда и только тогда, когда й — это максимум справа налево последовательности Ь» Ьэ ... 6„. ь 20. (М28] Предположим, нужно вычислитыпах((а~ — Ь»(,(໠— Ьэ(,...,(а„— 6„(), где 6» < 6» «6„. Покажите, что достаточно вычислитыпах(т», тя), где ть = шах(໠— 6» ( ໠— максимум справа налево последовательности ап а» ., ан], тя = шах(6» — а» ( ໠— минимум справа налево посйедовательности аи аэ ..
а„) . (Таким образом, если а» расположены в случайном порядке, то число таких Ь, для которых необходимо выполнить вычитание, приблизительно равно 2 )п и.] ь 21. [НМ21] Пусть монета бросается наудачу и раз и Х вЂ” число выпадений "орла" в этой серии испытаний. Распределению вероятностей для Х соответствует производящая функция (18), Воспользуйтесь (25) для доказательства того, что Рг(Х > п(р+ е)) < е где е > О, и получите аналогичную оценку для Рг(Х < п(р — е))*. ь 22. (НМ22] Предположим, что Х имеет производящую функцию (д»+р~э)(д»+р») (д + р е), тле р» + д» = 1 для 1 < Ь < и.
Пусть р = Е Х = р» + рэ + + р„. (а) Докажите, что Рг(Х < рг) < (г "е" )", когда О < г < 1, Рг(Х > рг) < (г 'е' )", когла г > 1. (Ь) Выразите правые части этих оценок в более удобном виде, когда г 1 (с) Покажите, что если г достаточно большое, то имеем Рг(Х > рг) < 2 23. [НМйз] Укажите неравенства для хвостов распределений для случайной величины, имеющей втрииательное биномиальнов распределение, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
