6.5-2* Покажите, что

к-1

£ С>8 < <° + па-к(а+1)Ь а/(а + 1)}

8 = 0V

при а>0и0</г<га.

6.5-3* Докажите, что при 0 < к < rap, где 0 < р < 1 и g = 1 - р, выполнено неравенство

f-пр - к \ к J \п - к J

6.5-4* Покажите, что в условиях теоремы 6.6 выполнено неравенство

Р{,-л->гк(<)",

а в условиях следствия 6.7 выполнено неравенство Р{пр - X г}

6.5-5* Рассмотрим серию из га независимых испытаний; вероятность успеха в г-м из них обозначим pi (вероятность неудачи (ц равна 1 - pi). Пусть случайная величина X есть число успехов в серии, и пусть fj, = М[Х]. Докажите, что при г 0 выполнено неравенство

Р{Х - ц > г} <с е~г212п.

6.5-6* Покажите, что при выбранном значении а = In (г /) правая часть неравенства (6.45) достигает минимума.

6.6. Вероятностный анализ

В этом разделе мы приведём три примера применения разобранных методов оценки вероятностей. Примеры эти таковы: совпадение дней рождений у двух человек среди данных к человек, распределение шаров по урнам и участки повторяющихся исходов при бросании монеты.

6.6.1. Парадокс дня рождения

Парадокс дня рождения (birthday paradox) связан с таким вопросом: сколько человек должно быть в комнате, чтобы с большой

вероятностью среди них оказались двое родившихся в один день? Парадокс состоит в том, что ответ значительно меньше числа дней в году, что кажется странным.

Мы считаем, что в году 365 дней и что дни рождения к человек выбираются случайно и независимо друг от друга. Оценим вероятность того, что все дни рождения окажутся различными. Пусть день рождения первого уже выбран; ясно, что день рождения второго совпадёт с ним с вероятностью 1/365. При выбранных (и различных) днях рождения первого и второго вероятность, что у третьего день рождения совпадёт с одним из уже имеющихся, будет 2/365 и так далее. В итоге вероятность того, что у к человек будут различные дни рождения, есть

365 У V 365 У " V1 365

Более формально, пусть га - число дней в году, и пусть Аг- - событие «день рождения (г + 1)-го человека не совпадает с днями рождения предыдущих г человек». Тогда пересечение В{ = А\ П А2 П ... П Аг- 1 будет событием «у первых г человек дни рождения различны».

Поскольку Bk = Ak-i П Bk-i, то из формулы (6.20) получаем соотношение

Р{Вк} = PiBk-rtPiAk-ilBk-!}.(6.46)

Начальное условие: P{ Bi} = 1.

Условная вероятность P{A i B i} равна (га - к + 1)/га, так как среди га дней имеется га - (к - 1) свободных (по условию все предыдущие дни рождения различны). Поэтому

Р{Вк} = Р{,В1}Р{А11}Р{А2,В2} • • -PiAkBk-!} ,п-1\(п-2\ (п-к + 1"

га / \ га / \ га

i..i-iUi-V. <

п I \ п I \га

Теперь из неравенства 1 + х ех (2.7) следует, что

Р{Вк} е-11пе-21пе-(к-1п

-(1 + 2+3+..

-к(к-1)/2п

e-(l + 2+3+... + (fc-l))/rx

= е 1/2,

если -к(к - 1)/2га /га(1/2). Вероятность того, что все к дней рождений различны, не превосходит 1/2 при к(к - 1) 2га In 2. Решая

это квадратное неравенство, получаем к (1 + д/l + (8 In 2)га)/2. Для га = 365, имеем к 23. Итак, если в комнате находится не менее 23 человек, то с вероятностью не менее 1/2 какие-то двое из них родились в один и тот же день. На Марсе, где год состоит из 669 марсианских суток, в комнате должно быть не менее 31 марсианина.

Другой метод анализа

Есть другой, более простой способ получить оценку для родственной задачи. Для каждой пары людейнаходящихся в комнате, рассмотрим случайную величину Xij

{1, если г и j родились в один день, О, в противном случае.

Вероятность того, что дни рождения двух данных людей совпадают, равна 1/га, поэтому по определению математического ожидания (6.23)

M[Xij] = 1 • (1/га) + 0 • (1 - 1/га) = 1/га

при г ф к.

Сумма всех Xij по всем парам 1 г < j к имеет математическое ожидание, равное сумме ожиданий для каждой пары; всего пар С = к (к - 1)/2, так что эта сумма равна к (к - 1)/2га. Поэтому нужно примерно \/2п человек, чтобы математическое ожидание числа пар людей с совпадающими днями рождения сравнялось с 1. Например, при га = 365 и к = 28 ожидаемое число пар людей, родившихся в один день, равно (28 • 27)/(2 • 365) ~ 1,0356. На Марсе для этого требуется 38 марсиан.

Заметим, что мы оценивали две разные вещи: (1) при каком к вероятность события X = z~2-ij > 0 больше 1/2, и (2) при каком к математическое ожидание X больше 1. Формально это разные вопросы (можно заметить лишь, что если вероятность Р{Х > 0} > 1/2, то М[Х] > 1/2, так как величина X принимает целые значения). Однако и в том, и в другом случае ответ имеет асимптотику 0(л/й)-

6.6.2. Шары и урны

Пусть имеется 6 урн, пронумерованных от 1 до 6. Мы опускаем в них шары: каждый шар с равной вероятностью помещается в одну из урн независимо от предыдущих. Таким образом, с точки зрения любой из урн происходит последовательность испытаний по схеме Бернулли с вероятностью успеха 1/6 (успех - попадание шара в