Рт{Х > г) < s Ef{X) при условии, что существует Ef{X) Неравенство (25) можно получить для f{t) - х н s = х

УПРАЖНЕНИЯ

1. [10] Найдите значение рпо из соотношений (4) и (5) и дайте интерпретацию этой вероятности в свете алгоритма М

2. [НМ16] Выведите (13) из (10).

3. [М15] Чему будут равны минимум, максимум, среднее и среднее квадратичное отклонение для числа выполнений шага М4, если для нахождения максимума среди 1 ООО случайно упорядоченных различных величин воспользоваться алгоритмом М (Дайте ответ в виде десятичных дробей.)

4. [М10] Дайте в явном виде формулу для рпк из задачи о бросании монеты (см. соотношение (17))

5. [М13] Чему равны среднее и среднее квадратичное отклонение для распределения, показанного на рис 11

6. [НМ27] Мы вычислили среднее и дисперсию для важных распределений вероятностей (8), (18), (20). Чему равен третий семиинвариант, кз, в каждом из этих случаев?

► 7. [М27] Анализируя алгоритм М, мы предполагали, что все Х[к] были различны. Теперь сделаем более слабое предположение, а именно - что среди .Y[l], Х[2], , Х[п] содержится ровно тп различных значений; в других отношениях эти величины случайны. Каким будет распределение вероятностей для А в этом случае?

► 8. [М20] Предположим, что каждое Х[к] выбирается наугад из множества М различных элементов, так что все М" возможных вариантов выбора элементов [1], [2],..., А[гг] считаются равновероятными. Чему равна вероятность того, что все Х[к] будут различны?

9. [М25] Обобщите результат предыдущего упражнения и найдите формулу для вероятности того, что среди Х[к] окажется ровно m различных величин. Выразите эту вероятность с помощью чисел Стирлинга

10. [М20] С помощью результатов трех предыдущих упражнений выведите формулу для вероятности того, что А = к, при условии, что каждое Х[к] выбирается наугад из М-элементного множества.

► 11. [М15] Что произойдет с семиинвариантами распределения, если заменить функцию G{z) функцией Fiz) = г"С(г)?

12. [НМ21] Если G(z) = po+piz+p2Z -\----соответствует некоторому распределению вероятностей, то величины М„ = k"pk иШп =к(- Mi)"pk называются п-м моментом и п-м центральным моментом соответственно. Покажите, что G(e) = l+Mit+M2t/2+-

С помощью формулы Арбогаста (см. упр. 1.2.5-21) докажите, что

« - Т (-1)*++ +-п! {кг+к2 + ---+кп-1)! к, jk, jk„

*l-l-2*3-l- =n

В частности, Ki = Mi, К2 = М2 - Mi (как мы уже знаем), кз = Мз - ЗМ\М2 + 2Aff и К4 = М4 - 4Mi Мз + 12М?Mj - ЗМ2 - бМ* Найдите аналогичное выражение для Кп через центральные моменты mj, тпз, , где п > 2

13. [НМ38] Говорят, что последовательность распределений вероятностей, соответствующих производящим функциям Gn{z) со средними рп и средними квадратичными отклонениями (Тп, стремится к нормальному распределению, если

lim e-*"""G„(e"/") = e-/

длявсех действительных значений t. Пусть С„(г) задается формулой (8). Покажите, что распределение, соответствующее С„(г), стремится к нормальному распределению.

Замечание. Можно показать, что данное здесь определение стремления к нормальному распределению эквивалентно следующей формуле:

lim вероятность ( - < а; 1 = -== / е at,

где Хп - случайная величина, распределение вероятностей которой задается с помощью G„{z). Это частный случай важной "теоремы непрерывности" П. Леви (Р. Levy), которая является одним из основных результатов математической теории вероятностей. Доказательство теоремы Леви выходит за рамки данной книги, хотя оно не такое уж сложное [см., например, книгу Б. В. Гнеденко и А. Н. Колмогорова, Предельные распределения для сумм независимых случайных величин (М.: Гостехиздат, 1949)].

14. [НМЗО] (А. де Муавр.) Пользуясь обозначениями из предыдущего упражнения, покажите, что биномиальное распределение G„{z), заданное формулой (18), стремится к нормальному распределению.

15. [НМ23] Если вероятность того, что некоторая случайная величина принимает значение к, равна е~{р/к)*, то говорят, что она имеет распределение Пуассона со средним р..

a) Найдите производящую функцию для этого распределения вероятностей.

b) Найдите значения семиинвариантов.

c) Покажите, что при п оо распределение Пуассона со средним пр стремится к нормальному распределению в смысле упр, 13.

16. [М25] Пусть распределение случайной величины X является смесью распределений, порожденных функциями gi{z), g2{z), .., gr{z), в том смысле, что распределение X с вероятностью рк совпадает с распределением случайной величины, соответствующей производящей функции gk{z), где pi +р2 + +Рт = 1. Найдите производящую функцию для X Выразите среднее и дисперсию X через средние и дисперсии gi, д2, , дг-

> 17. [М27] Пусть /(г)ир(г) - производящие функции, которые соответствуют некоторым вероятностным распределениям.

a) Покажите, что h{z) = g{f{z)) -тоже производящая функция, соответствующая некоторому вероятностному распределению.

b) Дайте интерпретацию h(z) в терминах f(z) и g{z). (Каков смысл вероятностей, заданных коэффициентами разложения h{z)7)

c) Выразите среднее и дисперсию h через средние и дисперсии / ид.

18. [М28] Предположим, что величины, которые мы обозначили через Afl], [2],..., Х[п] в описании алгоритма М, содержат ровно ki единиц, двоек, ..., кп чисел п, расположенных в случайном порядке. (Здесь

kl +к2-\-----\-кп =п.

В тексте предполагалось, что ki = к2 = = кп = i-) Покажите, что в этой более общей ситуации производящая функция (8) будет иметь вид

Пп-1г + кп\ Пп-2г + кп-1 +кп\ fkiz + к2 + +кп\ + кп-1 + кп J \ kl + к2 + "Ц- кп J

если принять, что О/О = 1. * > О - Прим. ред.

19. [М21] Если at > aj для I < j < к, будем говорить, что а/,-это максимум слева направо последовательности 0102 .. а„. Предположим, что 0102 ... о„ - это перестановка чисел {l,2,:v ,"}, и 6162 ... Ьп - обратная перестановка, так что Пк - I тогда и только тогда, когда 6/ = к. Покажите, что Uk является максимумом слева направо последовательности ai 02 ... On тогда и только тогда, когда к - это максимум справа налево последовательности ЪхЪг .Ьп-

► 20. [М22] Предположим, нужно вычислить max{ai -b\\, \а2 -Ьг!, • , ln - bn\], где b\ < bl < <bn- Покажите, что достаточно вычислить тах{тх,,тл}, где

ть = тах{аА; - Ьк \ Ок - максимум справа налево последовательности ai, 02 . , тл = max{bA; - од, ajt -минимум справа налево последовательности oi, 02 .. Оп} .

[Таким образом, если ак расположены в случайном порядке, то число таких А, для которых необходимо выполнить вычитание, приблизительно равно 2 In п.]

► 21. [НМ21] Пусть монета бросается наудачу п раз и -Y - число выпадений "орла" в этой серии испытаний. Распределению вероятностей для X соответствует производящая функция (18). Воспользуйтесь (25) для доказательства того, что

Рг(А>гг(р + е)) <e-"/f,

где е > О, и получите аналогичную оценку для Pr(.Y < п{р - б))*.

► 22. [НМ22] Предположим, что .Y имеет производящую функцию (iji-1-piг)(ij2-l:P2) (9п+ Pnz), где Pk+qk = 1 для 1 < А: < гг. Пусть = Е X = pi + Р2 + • • 4- Рп. (а) Докажите, что

Рг(Х < г) < [r-e-Y, когда О < г < 1,

Рг(А > г) < (ге)*", когда г > 1.

(Ь) Выразите правые части этих оценок в более удобном виде, когда г я 1 (с) Покажите, что если г достаточно большое, то имеем Pr(.Y > г) < 2"*".

23. [НМ23] Укажите неравенства для хвостов распределений для случайной величины, имеющей отрицательное биномиальное распределение, т. е. распределение, которому соответствует производящая функция (q - pz", где q - р + I.

*1.2.11. Асимптотические представления

Во многих any чаях для того, чтобы сравнить одну величину с другой, достаточно знать не точные, а приближенные их значения. Напри.мер, формула Стирлинга для п\-это удобное приближение подобного типа для больших п; мы пользовались также приближением Н„ и Inn -f- 7. При выводе подобных асимптотических формул обычно используются методы высшей математики, но в следующих разделах для получения нужных результатов мы не будем выходить за рамки элементарной математики.

*1.2.11.1. Символ О. Поль Бахман (Paul Bachmann) в книге .4na]ytiscAe Zahlen-theorie (1894 г.) ввел очень удобное обозначение для использования в приближенных формулах. Это символ О, который позволяет заменить знак знаком и количественно выразить степень точности, например

Я„ =1пп + 7 + 0().

Здесь р - вероятность того, что выпадет "орел", а ? = 1 - р. - Прим. ред.