Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 34
Текст из файла (страница 34)
раздел В.4) с вероятностью успеха 1/Ь, где успех состоит в том, что шар попадает в заданную корзину. Эта модель может оказаться особенно полезной в ходе анализа хеширования (см, главу 11), и мы можем ответить на ряд интересных вопросов о процессе наполнения корзин шарами (в задаче В.1 вы встретитесь и с другими вопросами о шарах и корзинах). Сколько шаров попадает в определенную корзину? Количество шаров, попавших в определенную корзину, подчиняется биномиальному распределению Ь(Ь; и, 1/Ь). Если всего в корзины было опущено и шаров, то согласно уравнению (В.37) математическое ожидание количества шаров в корзине равно и/Ь.
Сколько в среднем требуется шаров для того, чтобы в данной корзине оказался один шар? Количество шаров, которое требуется для того, чтобы в данной корзине оказался шар, подчиняется геометрическому распределению с вероятностью 1/Ь и согласно уравнению (В.32) математическое ожидание количества шаров, которое следует опустить в корзины, равно 1/(1/Ь) = Ь. Сколько шаров нужно опустить в корзины для того, чтобы в каждой из них оказалось хотя бы по одному шару? Назовем "попаданием" опускание шара в пустую корзину. Нужно определить математическое ожидание количества опусканий п, необходимых для Ь попаданий.
С помощью попаданий и опусканий можно разбить на этапы. Этап под номером 1 длится от (1 — 1)-го попадания до 1-го попадания. Первый этап состоит из одного (первого) опускания, поскольку если все корзины пусты, то мы с необходимостью получим попадание. На 1-м этапе имеется 1 — 1 корзин с шарами и Ь вЂ” з + 1 пустых корзин.
Таким образом, при каждом опускании шара на 1-м этапе вероятность попадания равна (Ь вЂ” з + 1)/Ь. Пусть кч — количество опусканий на з-м этапе. Тогда количество шаров, необходимых для попадания в Ь корзин, равно п = 2 ь з пь Все случайные зна- !б1 Глана 5. Веролтноетныя анализ и рандаиюироеанные алгоритмы чения гн подчиняются геометрическому распределению с вероятностью успеха (6 — 1'+ 1)/6, и в соответствии с уравнением (В.32) мы имеем Е[и,] = 6 Пользуясь линейностью математического ожидания, получаем ь Е[и] = Е ~и, 1=1 ь Е [иь] ма 1 ь Ь ~Ь,+1 ь Ь~ т 1 1=1 Ь(1п Ь + 0(1)) (согласно (А.7)) .
Таким образом, после примерно 61п6 опусканий шаров в корзины можно ожидать, что шар будет в каждой корзине. Эта задача известна также как задача сборщика кулонов, которая говорит о том, что человек, пытающийся собрать все 6 различных купонов, для успеха своего предприятия должен собрать около 6!п 6 случайно находящихся купонов.
5.4.3. Последовательности выпадения орлов Предположим, что правильная (т.е. выпадение орла и решки равновероятны) монета подбрасывается и раз. Какого юличества последовательных выпадений орла можно ожидать? Как покажет последующий анализ, эта величина ведет себя как 9(18 и).
Докажем сначала, что математнчесюе ожидание длины наибольшей последовательности орлов представляет собой О(18 и). Вероятность того, что при очередном подбрасывании выпадет орел, равна 1/2. Пусть А,ь — событие, когда последовательность выпадений орлов длиной не менее й начинается с з-го подбрасывания, нли, более строго, Агь — событие, когда при 12 последовательных подбрасываниях монеты з, з + 1,..., з + 12 — 1 (где 1 < Ь < и и 1 < 1 < и — Ь + 1) будут выпадать одни орлы. Поскольку подбрасывания монеты осуществляются независимо, для каждого данного события Азь вероятность того, что во всех Ь подбрасываниях выпадут одни орлы, определяется следующим образом: Рг(А12) = 1/2" .
(5. 8) 6 ЭаМ, 6726 1б2 Часть 2 Основы д )с = 2 [1к 221 Рг (А1,211яи) ) = 1/2 < 1/22'яи 1/ г так что вероятность того, что последовательность повторных выпадений орлов длиной не менее 2 [1кгь~ начинается с 1-го подбрасывания, довольно невелика. Имеется не более гь — 2 [1я12[ + 1 подбрасываний, с которых может начаться указанная последовательность орлов.
Таким образом, вероятность того, что последовательность повторных выпадений орлов длиной не менее 2 [1я п~ начинается при произвольном подбрасывании, равна и — 2 (1а и).1-1 и-211я и)+1 0 А*, (1.-1 — Е 1=1 1=1 2 ь=1 = 1/и (5.9) Справедливость этого соотношения следует из неравенства Буля (В.19), согласно которому вероятность объединения событий не превышает сумму вероятностей отдельных событий.
(Заметим, что неравенство Буля выполняется даже для тех событий, которые не являются независимыми.) Теперь воспользуемся неравенством (5.9) для ограничения длины самой длинной последовательности выпадения орлов. Пусть Б (2 = О, 1, 2,..., гь) — событие, когда длина самой длинной последовательности выпадения орлов равна 1. В соответствии с определением математического ожидания мы имеем и Е[.Ц = ) 1Рг(ХЗ) з=с (5.10) Можно попытаться оценить эту сумму с помощью верхних границ каждой из величин Рг(Ц), аналогично тому, как это было сделано в неравенстве (5.9). К сожалению, этот метод не может обеспечить хороших оценок. Однако достаточно точную оценку можно получить с помощью некоторых интуитивных рассуждений, которые вытекают из проведенного выше анализа.
Присмотревшись внимательнее, можно заметить, что в сумме (5.10) нет ни одного слагаемого, в котором оба множителя ? и Рг(Ь ) были бы большими. Почему? При 1 > 2 [1я и[ величина Рг(Ц) очень мала, а при у' < 2 [1я п~ оказывается невелико само значение ?. Выражаясь более формально, можно заметить„что события Ь, для 2 = 0,1,..., и несовместимы, поэтому вероятность того, что непрерывная последовательность выпадения орлов длиной не менее 2 [1яп[ начинается с любого подбрасывания монеты, равна 2 ".
2(1 и) Рг(Ь1). Согласно неравен- Глава 5. Веролтноотный анализ и рандамнзированные алгоритмы ствУ (5.9) имеем 2 " 211 и1 Рг(лу) < 1/и. КРоме того, из 2 " С Рг (Ц) = 1 вытекает 2 ." ко Рг (Ь ) < 1. Таким образом, получаем и Е[2! = Е5 Рг(л 5) 5=О 2 Г1к и1 — 1 и — 5'Рг(Ь ) + ~~) 5'Рг(Ц) 1=О 5=211Ки1 2(1ки~-1 и < ~~1 (2 [1бп!)Рг(Тз) + ~~1 пРг(Ц) 5=с 5=211к и1 20ки)-1 и = 2 [1Кп! ~~1 Рг(Ц) + п ~~~ Рг(Ц) у=с 5 =20К и1 < 2 [оп) 1+ и. (1/и) = 0(1кп) . Вероятность того, что длина последовательности непрерывных выпадений орла превысит величину г [1к и !, быстро убывает с ростом г.
Для г ) 1 вероятность того, что последовательность как минимум г [1кп! выпадений орлов начнется с г-го подбрасывания, равна Рг(А1,11 „1) = 1/2'Г'к"~ < 1/и'. Таким образом, вероятность образования непрерывной цепочки из последовательных выпадений орла, имеющей длину не менее г (1бп), не превышает и/п' = 1/пе 1. Это утверждение эквивалентно утверждению, что длина такой цепочки меньше величины г [1к и! с вероятностью не менее чем 1 — 1/п' 1. В качестве примера рассмотрим серию из п = 1000 подбрасываний монеты. Вероятность того, что в этой серии орел последовательно выпадет не менее 2 [1к и) = 20 раз, не превышает 1/и = 1/1000.
Вероятность непрерывного выпадения орла более 3 [1к и) = 30 раз не превышает 1/ив = 1/1 000 000. Теперь давайте рассмотрим дополняющую нижнюю границу и докажем, что математическое ожидание длины самой длинной непрерывной последовательности выпадений орлов в серии из и подбрасываний равно Й(1к и), Чтобы доказать справедливость этого утверждения, разобьем серию из и подбрасываний приблизительно на и/к групп по к подбрасываний в каждой.
Если выбрать в = [(1кп)/2), то можно показать, что с большой вероятностью по крайней мере в одной из этих групп окажутся все орлы, т.е, самая длинная последовательность выпадения орлов имеет длину как минимум к = Й(1к и). Затем мы покажем, что математическое ожидание длины такой последовательности равно Й(1к п). Часть / Основы Разобьем серию из п испытаний на несколько (не менее [п/ [(18 и)/2~ ~) групп из [(18п)/2) последовательных подбрасываний.
Оценим вероятность того, что в каждой из групп выпадет хотя бы по одной решке. Согласно уравнению (5.8) вероятность того, что в группе, которая начинается с 1-го подбрасывания, выпадут все орлы, равна Рг (А, 1(1 п)/2) ) = 1/21((аи)/2) > 1//сп. с — )(п/((1аи)/2)) (1 / / — )п/((1кп)/2)-1 < (1 — 1/,Г )'и'"и ' — (2и/(яп-1)/ь/п е = 0(е 1ки) = 0(1/п) . В приведенной выше цепочке соотношений были использованы неравенство (3.!2), 1+ х < е*, и тот факт, что при достаточно больших п справедливо соотношение (2п/18 п — 1)/з/п > 18 п (при желании вы можете в этом убедиться самостоятельно).
Таким образом, вероятность того, что длина самой большой последовательности выпадений орлов превосходит величину [(18 п)/2), равна Рг(Ь5) > 1 — О(1/п) . 2=1(1ки)/2) (5.11) Теперь можно вычислить нижнюю границу математического ожидания длины са- мой длинной последовательности орлов. Воспользовавшись в качестве отправной точки уравнением (5.10) и выполнив преобразования, аналогичные проведенным в ходе анализа верхней границы, получаем Е[Ц = ~~Рг(Т/) 5=0 1(1я и)/2) — 1 и ~ Рг(Ь2) + ~ )'Рг(Ь/) /=о у=В!ап)/2) Таким образом, вероятность того, что последовательность непрерывного выпадения орлов длиной не менее [(18 п)/2[ не начинается с 1-го подбрасывания, не превышает величину 1 — 1/,/и.
Поскольку [п/ [(18п)/2))' групп образуются из взаимно исключающих независимых подбрасываний, вероятность того, что каждая такая группа не будет последовательностью выпадений орлов длиной [(18 п)/2), не превышает величину !б5 Глава 5. Вероятноетныа аналоя и рандоиигированные алгоритиы К(я о)/21 — 1 и ) ~ ~О. Рг(Ь/) + ) [(1кп)/2) Рг(Х/) б=о 5=Ц1я п)/2) 1рян)/21-1 и = О ~~1 Рг(Ь/) + [(1йп)/2[ ~ Рг(Ь1) у=о 1=(йяо)/2) ) О + [(1я и)/2) (1 — О(1/и)) (согласно (5.11)) = П()в и) Как и в случае парадокса дней рождений, более простой, но менее точный анализ можно провести с помощью индикаторных случайных величин. Пусть Хрн = 1(АГя) — индикаторная случайная величина, связанная с последовательным выпадением ие менее /с орлов, начиная с 1-го подбрасывания монеты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
