эту урну). Мы рассмотрим несколько задач, связанных с таким процессом.

Сколько шаров попадёт в данную урну? Количество шаров, попавших в данную урну, описывается биномиальным распределением b(k;n,l/b). Если всего бросается п шаров, то математическое ожидание числа попавших в урну шаров равно п/Ь.

Сколько в среднем шаров нужно бросить, пока в данную урну не попадёт шар? Количество бросков до первого попадания в заданную урну имеет геометрическое распределение с вероятностью 1/6, поэтому ожидаемое число бросков есть 1/(1/6) = 6.

Сколько шаров нужно бросить, чтобы каждая урна содержала по меньшей мере один шар? Будем следить за числом заполненных урн. Вначале оно равно нулю, а затем увеличивается, пока не достигнет 6. Обозначим через гц случайную величину, равную числу попыток, потребовавшихся, чтобы это число возросло от г - 1 до г. (Таким образом, если вторая и третья попытки пришлись на ту же урну, что первая, а четвёртая - на другую, то Ш = 1, п2 = 3.) Общее число попыток до заполнения всех урн равно п\ + П2 + ... + щ. Мы вычислим математическое ожидание этой суммы как сумму математических ожиданий. Когда мы ждём заполнения г-ж урны, заполнено г - 1 урн из 6 и вероятность попасть в незаполненную равна (6 - г + 1)/6. По свойству геометрического распределения математическое ожидание величины гц обратно этой вероятности и равно 6/(6 - г + 1). Сумма этих величин по всем г

равна 6(1/6+ 1/(6- 1) + ...+ 1/2+ 1) = 6(1п 6 + 0(1)). (См. форму-

Итак, требуется сделать в среднем примерно 6 In 6 бросков, прежде чем в каждой урне появится по шару.

6.6.3. Участки повторяющихся исходов

Пусть мы бросаем симметричную монету п раз. Какое максимальное число идущих подряд орлов мы ожидаем увидеть? Оказывается, ответ на этот вопрос - ©(lgra).

Сначала докажем, что ожидаемая длина наибольшего участка есть 0(lg га). Пусть событие А{к состоит в том, что имеется участок из к или более орлов, начинающийся с г-го бросания. Очевидно,

При к = 2[lgra] вероятность появления к орлов в данных позициях не превосходит 1/га2, а возможных мест (значений г) меньше чем га, так что вероятность появления к орлов подряд (где-нибудь) не больше 1/га. Теперь математическое ожидание максимального числа идущих подряд орлов оценивается так: это число никогда не превосходит га и почти всегда (с вероятностью 1 -1/га) не превосходит 2[lg га], поэтому ожидание не больше [2 lg га] +га-(1/га) = 0(lg га).

P{Aik} = 1/2к.

(6.47)

Вероятность образования участка орлов длины не менее г [lgra] быстро уменьшается с ростом г (для фиксированной позиции она не больше 2 rlgn = п~г, а для всех позиций в сумме она не превосходит га п~г = га~(г 1).) Например, для га = 1000 вероятность появления участка из по меньшей мере 2 [lg га] = 20 орлов не превосходит 1/га = 1/1000, а вероятность появления участка 3[lgra] = 30 орлов не больше 1/га2 = 10 6.

Теперь докажем оценку снизу: ожидаемая длина наибольшего участка есть S7(lgra). Для этого рассмотрим участки длины L(lgra)/2j. Согласно (6.47) вероятность появления такого участка в данной позиции не меньше 1 /2 L(1S"-)/2J 1 п, а вероятность его непоявления не больше 1 - 1 п. Разобьём всю последовательность бросаний на непересекающиеся группы, состоящие из [(lgra)/2j бросаний каждая. (Несколько членов окажутся вне групп, если при делении будет остаток.) Число групп не меньше 2ra/lgra - 1.

События в разных группах независимы, поэтому вероятность того, что ни одна из этих групп не состоит из одних орлов, не больше

(1 \ n)2nlln~l e-{2nln-l)IV

= 0(e"lgn) = 0(1/га)

Мы использовали тот факт, что 1 + х ех (2.7), а также то, что (2ra/lgra - 1)/лД lgra - 0(1).

Итак, с вероятностью не менее 1 - О (1/га) длина наибольшего участка подряд идущих орлов не меньше [lgra/2] = £7(lgra), поэтому математическое ожидание никак не меньше (1 - l/ra)£7(lgra) = П (lgra).

Упражнения

6.6-1 Шары бросают в Ь урн; все бросания независимы друг от друга, и каждый шар равновероятно попадает в любую из урн. Чему равно ожидаемое количество бросаний до момента, когда в одной из урн окажется два шара?

6.6-2* Существенно ли для приведённого нами анализа парадокса дня рождения то, что дни рождения независимы в совокупности, или было бы достаточно их попарной независимости? Объясните свой ответ.

6.6-3* Скольких гостей надо пригласить на вечеринку, чтобы скорее всего оказалось, что по меньшей мере трое из них родились в один день?

6.6-4* Какую долю составляют инъекции среди всех отображений /г-элементного множества в га-элементное? Как связан этот вопрос

с парадоксом дня рождения:

6.6-5* Пусть га шаров бросают в га урн, все бросания независимы, попадания каждого шара во все урны равновероятны. Чему равно ожидаемое количество пустых урн? А ожидаемое количество урн, в которые попало в точности по одному шару?

6.6-6* Улучшите нижнюю оценку для длин участков из одних орлов, показав, что при га бросаниях симметричной монеты участок длины lgra - 2 lg lg гг. найдётся с вероятностью не меньше 1 - 1/га.

6-1 Шары и урны

В этой задаче мы считаем число способов разложить га шаров в Ь различных урн.

а.Предположим, что все шары разные, их порядок внутри урны не учитывается. Докажите, что существует Ьп способов поместить шары в урны.

б.Предположим, что все шары разные и их порядок в урне существен. Докажите, что шары можно разложить по урнам (Ь + га - 1)1/(Ь - 1)1 способами. (Указание: подсчитайте число способов расставить га различных шаров и Ь - 1 одинаковых чёрточек в ряд.)

в.Предположим, что все шары одинаковы, и их порядок в урне не имеет значения. Покажите, что число способов раскладки шаров по урнам равняется Сьа+п 1. (Указание: используйте ту же идею, что в пункте (б).)

г.Покажите, что если шары одинаковые и в любую урну помещается не больше одного шара, то число способов равно С£.

д.Покажите, что если шары одинаковые и в любой урне должен оказаться по меньшей мере один шар, то число способов раскладки шаров равно CbnZ \.

6-2 Программа вычисления максимума

Рассмотрим такую программу поиска максимума в неупорядоченном массиве А[1. .га].

1 max <--оо

Задачи

2 for г

3

4 5

Мы хотим определить, сколько раз в среднем выполняется при-