возможными размещениями %дут 12312, 13213, 21321, 23123, 31231, 32132. В каждом разбиении мы получаем одинаковое число размещений с А = к.

С другой стороны, если у нас больше информации, то распределение вероятностей изменится. Например, при п = 3 и m = 2 рассматриваются шесть возможностей: 122, 212, 221, 211, 121, 112 (см. рассуждения из предыдущего абзаца). Если же нам известно, что имеются две двойки и одна единица, то следует рассмотреть только первые три из приведенных шести возможностей. Но такая интерпретация не согласуется с постановкой задачи.

8. М-/М". Чем больше значение М, тем данная вероятность ближе к единице.

9. Пусть qnm-вероятность того, что имеется ровно т различных значений; тогда из рекуррентного соотношения

М - т + 1 т

Чпгп -

получим, что

д„т = ЛЛ.[}/(М-т)!М".

См. также упр. 1.2.6-64.

10. Нужно просуммировать qnmPmk по всем т. Получим М"" Х)т (т) {ml L+i] • Формула для среднего, которое меньше, чем

m=l к=\

далеко не проста.

11. Так как это произведение, семиинварианты складываются. Если H{z) - г", Я(е) = е", то «1 = п, а все остальные семиинварианты равны нулю. Следовательно, mean(F) = n + mean(G), а все остальные семиинварианты остаются без изменений. (Этим объясняется название "семиинвариант"*.)

12. Первое тождество очевидно, если записать функцию е* в виде степенного ряда. Чтобы

получить второе тождество, положим и = 1 + Mit + Mitjll Н----. При t = О имеем и = 1 и

0\и = Мк- Кроме того, i?i(lnu) = (-l)-~(j-l)!/u-. Согласно упр. 11 такие же формулы применимы и для центральных моментов, если отбросить все члены, для которых fci > 0; таким образом, «2 = тач, кз = та, К4 = 7714 - Зтг.

«-« = S = 45R5f(-;)"(-°<"-))-rf9lC*°<"-»-

Zn = е*"". При 71 00 и фиксированном ( имеем г„ -> 1. Следовательно, Г(2„ + 1) -> 1 и

Gnizn) = lim exp (+ (е"/"" - 1)1п7г)

п-юо \ (Тп /

f-t4nn / 1

= lim exp ----h О ,- =

Замечание. Это теорема Гончарова [Изв. АН СССР. Сер. Мат. 8 (1944), 3-48]. Ф. Флажоле (Р. Flajolet) и М. Сориа (М. Soria) [Disc. Math. 114 (1993), 159-180] провели дополнительные исследования и показали, что распределение с производящей функцией G„(z) и большое семейство близких к нему распределений не только являются приближенно нормальными

* "Полунеизменный". - Прим. перев.

вероятность

> X

вблизи средних значений кроме того, хвосты данных распределений равномерно мажорируются экспонентой, т. е.

/ Хп - ц„

\ On

для некоторой положительной константы о и для всех п и х.

14. e-"P"v(g + pe-/v)" = {qe-p/ + ре/)". Разложив экспоненциальные функции в степенные ряды, получим (1 - t/2n + 0(п~*))" = ехр(п1п(1 - tl2n + 0{п-1))) = exp(-tV2 + 0{п-")) -л ехр{-ф).

15- (а) Ек>ое"(/г)*Д! = е"""!. (Ь) Ine""-! = (е* - 1), поэтому все семиинварианты равны . (cexpC-rtrip/v) ехр(пр(й/\/йр+-*72"Р+0(п"*))) = ехр(-*72+0(п~)).

16. g{z) - J2kPk9k{z), mean(y) = EitP* niean(yt) и var(y) = Ej, P*аг(ук) + Ej<*:PjPit(niean(5j) - теап(?*,))

17. (a) Коэффициенты разложений f{z) и g(z) неотрицательны и /(1) = д{1) = 1. Очевидно, что h(z) имеет такие же свойства, поскольку h{l) = g{f{l)), а коэффициенты разложения h являются многочленами от неотрицательных коэффициентов fug. (b) Пусть f{) = Ер***; Рк-это вероятность того, что случайная величина Х/, соответствующая f{z), принимает значение к, рк = РХ/=к. Пусть g{z) = JQkz; Qk-вероятность того, что случайная величина Хд, соответствующая (г), принимает значение к. Тогда h{z) = Е"** соответствует случайной величине Xh такого вида: Xh = - g-fkt где Xfk-независимые одинаково распределенные случайные величины, каждая из которых распределена так же, как Х/, и все они не зависят от Хд. (Это легко показать, если заметить, что /(г)* = stz, где st - вероятность того, что сумма к независимых случайных величин A/j равна t.) Пример. Если / дает вероятности того, что мужчина имеет к потомков мужского пола, а д - вероятности того, что в п-м поколении к мужчин, то h порождает вероятности того, что в (п + 1)-м поколении будет к мужчин (при условии независимости), (с) mean(/i) = mean(y) mean(/); var(/i) = vax(y) mean(/) -i-mean(y) var(/).

18. Рассмотрим выбор величин A[l],..., A[n] как процесс, в котором мы сначала размещаем все числа п, затем среди них размещаем все (п-1),... и наконец среди всего остального размещаем единицы. Когда мы размещаем числа г среди чисел г -f 1,..., п, число локальных максимумов при движении справа налево возрастает на единицу тогда и только тогда, когда мы помещаем число г в крайнюю позицию справа. Вероятность этого события равна кг/{кг + kr+i -1----+ к„).

19. Положим Ок = I. Тогда aj, - максимум слева направо последовательности oi ...вп

j < к влечет Oj < / Oj > / влечет j > к j > I влечет bj > к

к - минимум справа налево последовательности 6i ... Ьп.

20. Имеем ть = max{oi - bi,..., Оп - Ьп}. Доказательство. Предположим, что это не так. Пусть к - наименьший индекс, для которого ак - Ьк > ть- Тогда oj, не является максимумом слева направо и, значит, существует такое j < к, что Oj > ак- Но тогда - bj > ак - Ьк > ть, что противоречит минимальности к. Аналогично тя = max{bi -Ol,... ,6„-о„}.

21. При е >q результат тривиален, поэтому предположим, что е < д. Полагая х =

в (25), получим Рт{Х > п{р + е}) < {{:Г+{)~Т- Имеем {Г+ < 6"% так как

t < е~ для всех действительных t. И (д -б)1п = е - ~ Т2Ч~----< -

(Более подробный анализ дает несколько более сильную оценку ехр(-бп/(2рд)), где р>\; данее легко получить верхнюю грань ехр(-2бп) для всех р.) Поменяв местами роли "орла" и "решки", получим

Рх{Х < п(р - б)) = Рг(п -X>n{q + б)) < е-""".

22. (а) В (24) и (25) положим а; = г и заметим, что git + pit г = 1 + (г - 1)рц < е-">". [Си. Н. ChernofF, Annais of Math. Stat. 23 (1952), 493-507.]

(b) Положим г = 1 + где J < 1. Тогда re- = exp{--S + j-S----). Это

выражение < e~ при «5 < О и < е при J > О

(c) По мере того как г возрастает от 1 до оо, функция г~е" убывает от 1 до 0. Если г > 2, то значение функции < е < .825; если же г > 4.32, то значение функции < .

Интересно заметить, что неравенства для хвостов распределений при х = г дают точно такую же оценку (г~е"), если А из упр. 15 имеет распределение Пуассона.

23. Полагая в (24) х - Еф, получим Рт{Х < п{р - е)) < (()-()~)" < е-е=п/(2р,) Аналогично прих=Ц получим Рг(А > n{p + i)) < {{ГЧ-Т-УТ Положим /(б) = (д+е)1п(1+)-(р+б)1п(1 + ) и заметим, что /(е) = 1п(1 +§)-1п(1 + ). Отсюда следует, что /(б) < -€/{bpq), если О < б < р.

РАЗДЕЛ 1.2.11.1

1. Нулю.

2. Символы О могут представлять различные приближенные величины. Поскольку левой частью может быть /(п) - (-/(п)) = 2/(п), самое большее, что можно сказать,-это 0{f{n)) - 0{f{n)) = 0{f{n)) (следует из (6) и (7)). Чтобы доказать (7), нужно заметить, что если х„ < M\f{n)\ для п > по и х„ < M\f{n)\для п > по, то х„ ±х„ < x„ + xj, < {М + M)\f(n)\ для п > тах(по,По). (Подпись: Студент Квик*.)

3. n(lnn)+7n-(-0(i/nlnn).

4. Ino + (lno)V2n + {1па)Убп + Oin).

5. Если f{n) = и g{n) = 1, то n принадлежит множеству 0{f{n) + g{n)), но не множеству f{n) + 0{д{п)). Поэтому утверждение ложно.

6. Символов О переменное число, а именно - п. Их заменили единственным символом О, ошибочно полагая, что одного значения М будет достаточно для каждого неравенства \кп\ < Мп. Как мы знаем, на самом деле данная сумма равна G(n*). Последнее равенство, Е!ь=1 0{п) = 0{г?), совершенно справедливо.

7. Если рассмотреть степенной ряд 1.2.9-(22), то видно, что для положительных х выполняется неравенство > х"/{т + 1)! Отсюда следует, что отношение е/х"* нельзя ограничить ни одним М.

8. Сделаем замену п на е" и применим метод из предыдущего упражнения.

9. Если /(х) < МгГ для г < г, то е- < е" = 1 + гГ(М -Ь М2Г/2! + М3г2"/3! + ••)< 1 + гГ(М + MV"/2 + Мг/З! + •••)•

10. ln(l + 0(z")) = 0(г"), если то - положительное целое. Доказательство. Если/(г) = 0(г"), то существуют положительные числа г < 1, г < 1 и константа Л/, такие, что /(г) < М2" < г при \z\ < г. Тогда ln(l + f{z))\ < /(z) + \\f{z)\ + • • • < 2ГМ(1 + \r+ ).

11. Формулу (12) можно применить дтя то = 1 и г = \пп/п. Это справедливо, поскольку In п/п < г для любого заданного г > О, если п достаточно велико.

12. Пусть /(г) = (ze~/(e - 1)У. Если бы [ijlj ь1ло равно 0(п*), то из вспомогательного тождества следовало бы, что [z]f(z) = 0{п/(к - 1)), поэтому степенной ряд для /(г) сходился бы при z = 2тп. Но f(2m) = оо.

13. В определениях О и можно взять L = 1/М.

* В оригинале -j. Н. Quick. От англ. "quick" (здесь - "сообразительный"). - Яргм<. перев.