Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 31
Текст из файла (страница 31)
Затем покажите, что алгоритм профессора ошибочен в том смысле, что полученные в результате его выполнения перестановки не будут распределены равномерно. * 5.3-5. Докажите, что в результате выполнения процедуры Рикмен Ву Яойтпчп вероятность отсутствия одинаковых элементов в массиве Р не меньше величины 1 — 1/и. 5.3-6. Объясните, как следует реализовать алгоритм Рнймитн Ву бойтпчп в случае, когда два или более приоритета идентичны.
Другими словами, алгоритм должен выдавать случайные равномерно распределенные перестановки даже в случае, когда два или большее количество приоритетов имеют одинаковые значения. * 5.4 Вероятностный анализ и дальнейшее применение индикаторных случайных величин В этом разделе повышенной сложности на четырех примерах иллюстрируется дальнейшее применение вероятностного анализа.
В первом примере вычисляется вероятность того, что двое из Й человек родились в один и тот же день года. Во втором примере рассматривается процесс случайного наполнения урн шарами, в третьем — исследуется событие, при котором в процессе бросания монеты несколько раз подряд выпадает орел. В последнем примере анализируется разновидность задачи о найме сотрудника, в которой решение о найме принимается без проведения собеседования со всеми кандидатами. Глава 5.
Вероятностный анализ и рандомизированные алгоритмы 157 5.4.1 Парадокс дней рождения Первым будет рассмотрен иарадокс дней рождения. Сколько людей нужно собрать в одной комнате, чтобы вероятность совпадения даты рождения у двух из них достигла 50%? Полученное в результате решения этой задачи число на удивление мало. Парадокс в том, что это число намного меньше, чем количество дней в году. Чтобы решить задачу, присвоим всем, кто находится в комнате, номера от 1 до Ь, где й — количество людей в комнате.
Наличие високосных годов проигнорируем и предположим, что в каждом году п = 365 дней. Пусть Ь, — дата, на которую приходится день рождения 1-й персоны (1 = 1,2,..., й, 1 < Ь, < и). Предположим также, что дни рождения равномерно распределены по всему году, так что Рг (Ь; = г) = 1/и для всех г = 1, 2,..., й и т = 1, 2,..., и.
Вероятность того, что даты рождения двух человек г и з совпадают, зависит от того, является ли случайный выбор этих дат независимым. В дальнейшем предполагается, что дни рождения независимы, поэтому вероятность того, что г-й и з-й посетители комнаты родились в день г, можно вычислить следующим образом: Рг(Ь; = т и Ьу — — и'1= Рг(Ь; = г1 Рг(6- = г'1= 1/и . Таким образом, вероятность того, что эти люди родились в один и тот же день, равна Рг (Ь; = ЬД = ~~1 Рг (Ь = г и Ьу — — г~) = ) — = — (5.7) 1 1 т=1 г=1 Интуитивно легче понять такое утверждение: если день рождения человека Ь; зафиксирован, то вероятность того, что день рождения человека 6 выпадет на эту же дату, равна 1/и. Таким образом, вероятность того, что даты рождения двух человек г и у совпадают, равна вероятности того, что день рождения одного из них выпадет на заданную дату.
Однако обратите внимание, что это совпадение основано на предположении о независимости дней рождения. Теперь можно проанализировать вероятность того, что хотя бы двое из й людей родились в один и тот же день, рассматривая дополняющее событие. Вероятность совпадения хотя бы двух дней рождения равна 1, уменьшенной на величину вероятности того, что все дни рождения различаются. Событие, при котором все дни рождения различаются, можно представить так: п Вь=ИА;, где А; — событие, состоящее в том, что день рождения 1-го человека отличается от дня рождения у-го человека для всех г < 1. Поскольку мы можем записать Часть Е Основы 158 Вь = Аь П Вь и из уравнения (В.16) мы получим следующее рекуррентное соотношение: Рг (Вь) = Рг (Вь 1) Рг (Аь ~ Вь 1), (5.8) начальное условие которого — Рг(В1) = Рг(А1) = 1. Другими словами, вероятность того, что дни рождения ЬмЬг,...,Ьь различны, равна произведению вероятности того, что различны дни рождения Ьм Ьг,..., Ьь ы на вероятность того, что Ьь ф Ь; для1 = 1,2,...,/с — 1 при условии, что Ьм Ьг,..., Ьь 1 различны.
Если Ьы Ьг,..., Ьь 1 различны, то условная вероятность того, что Ь| ф Ь, для 1 = 1, 2,..., й — 1, равна Рг (Аь~ Вь 1) = (и — й + 1)/и, поскольку из и дней незанятыми остались только и — (й — 1). Итеративно применяя рекуррентное соотношение (5.8), получим: Рг(Вь) = Рг(Вь з) Рг(Аь ! Вь 1) = = Рг(Вь г) Рг(Аь 1 ! Вь г) Рг(Аь ! Вь 1) = = Рг (В1) Рг(Аг ~ В1) Рг (Аз ~ Вг)... Рг (Аь ~ Вь г) = Неравенство (3.11), 1 + х < е*, дает нам следующее соотношение: Рг (В ) < е г/" г/" 0' з)/" = — г.",. -,' /и -ь(ь-з)/г. < 1 г2 г \ итгорое справедливо при — /с (й — 1)/2и < 1п (1/2). Итак, вероятность того, что все й дней рождения различаются, не меньше величины 1/2 при условии, что й(й — 1) > 2и!п2.
Решая квадратное уравнение относительно й, получим, что У р Й > (1 ~- Л ~- 8 1 2)!2, р = 365 д условие й > 23. Таким образом, если в комнате не менее 23 человек, вероятность того, что хотя бы двое из них родились в один и тот же день, не меньше 1/2. А, например, на Марсе год длится 669 дней, поэтому для того, чтобы добиться того же эффекта исходя из продолжительности марсианского года, понадобилось бы собрать не менее 31 марсианина. Анализ с помощью индикаторных случайных величин Индикаторные случайные величины дают возможность проведения простого (хотя и приближенного) анализа парадокса дней рождения. Определим для каждой Глава 5.
Вероятностный анализ и рандомизированные алгоритмы 159 пары (г, З) находящихся в комнате й людей индикаторную случайную величину Х," (1 < 1 < 1 < 1с) следующим образом: Х; = 1(Днн рождения г и т' совпадают) = 1 если дни рождения 1 и з совпадают, 0 в противном случае. Согласно уравнению (5.7) вероятность того, что дни рождения двух людей совпа- дают, равна 1/и, поэтому, в соответствии с леммой 5.1, получаем: Е (Х;д] = Рг (Днн рождения 1 и у совпадают) = 1/и. Полагая Х случайной величиной, которая представляет собой количество пар людей, дни рождения которых совпадают, получим: Применяя к обеим частям этого равенства операцию вычисления математического ожидания и воспользовавшись свойством ее линейности, получаем: Е1Х) = Е Поэтому если 1с (1с — 1) > 2п, математическое ожидание количества пар людей, родившихся в один и тот же день, не меньше 1.
Таким образом, если в юмнате как минимум ~/2т~ + 1 людей, то можно ожидать, что хотя бы у двух из них дни рождения совпадают. При п = 365 и к = 28 математическое ожидание юличества пар, родившихся в один и тот же день, равно (27 28)/(2 365) = 1.0356. Таким образом, если в комнате находится 28 человек, то следует ожидать, что хотя бы у двух из них день рождения совпадет. На Марсе, где год длится 669 дней, для того, чтобы добиться того же эффекта, понадобилось бы собрать не менее 38 марсиан. В первом анализе, в котором использовались только вероятности, определялось, сюлько людей нужно собрать, чтобы вероятность существования пары с совпадающими днями рождения превысила 1/2.
В ходе второго анализа, в котором использовались индикаторные случайные величины, определялось количество людей, при котором математическое ожидание числа пар с одним днем рождения на двоих равно 1. Несмотря на то, что в этих двух ситуациях точное количество людей различается, в асимптотическом пределе оно одинаково: 6 (~/й). Часть !. Основы 160 5.4.2 Шары и урны Рассмотрим процесс случайного наполнения Ь урн одинаковыми шарами, пронумерованными натуральными числами от 1 до Ь. Шары опускаются в урны независимо друг от друга, и вероятность того, что шар окажется в некоторой из урн, одинакова для всех урн и равна 1/6.
Таким образом, процесс заполнения урн шарами представляет собой последовательность испытаний по схеме Бернулли (см. приложение В) с вероятностью успеха 1/Ь, где успех состоит в том, что шар попадает в заданную урну. В частности, эта модель может оказаться полезной при анализе хеширования (см. главу 11). Сколько шаров окажется в заданной урне? Количество шаров, попавших в определенную урну, подчиняется биномиальному распределению Ь()ьп,1/6). Если всего в урны было опущено и шаров, то, согласно уравнению (В.Зб), математическое ожидание количества шаров в урне равно п/Ь. Сколько в среднем требуется шаров для того, чтобы в данной урне оказался один шар? Количество шаров, которое требуется для того, чтобы в данной урне оказался шар, подчиняется геометрическому распределению с вероятностью 1/Ь и, согласно уравнению (В.31), математическое ожидание количества шаров, которое следует опустить в урны, равно 1/ (1/6) = Ь.
Сколько шаров нужно онустить в урны для того, чтобы в каждой из них оказалось хотя бы ло однаму шару? Назовем "попаданием" опускание шара в пустую урну. Нам надо определить математическое ожидание количества опусканий п, необходимых для Ь попаданий. С помощью попаданий, п опусканий можно разбить на этапы. Этап под номером з' длится от 1 — 1-го попадания до 1-го попадания. Первый этап состоит из одного (первого) опускания, поскольку если все урны пусты, то мы с необходимостью получим попадание.
На 1-м этапе имеется з — 1 корзина с шарами и Ь вЂ” з'+ 1 пустых корзин. Таким образом, при каждом опускании шара на 1-м этапе вероятность попадания равна (Ь вЂ” 1 + 1)/Ь. Пусть гн — количество опусканий на 1-м этапе. Тогда количество шаров, необходимых для попадания в 6 урн, равно п = ~„~ и;. Все случайные значения и; подчиняются геометрическому распределению с вероятностью успеха (6 — з' + 1)/Ь, и, в соответствии с уравнением (В.З!), Е !п,'! = Ь Пользуясь линейностью математического ожидания, получаем: ь ь ь 6 ь Е!п) = Е ~~~ и; = ~~> Е(п;~ = ~~>, = 6~> —, = Ь(!пЬ+ 0(1)).
1=1 1=1 ю=1 ~=1 Глава 5. Вероятностный анализ н рандомнзированные алгоритмы 161 Последняя строка этой цепочки следует из границы (А.7) конечного гармонического ряда. Таким образом, прежде чем в каждой урне окажется хотя бы по одному шару, понадобится приблизительно б 1п б шаров. 5.4.3 Последовательности выпадения орлов Предположим, что монета подбрасывается т1 раз. Какое количество последовательных выпадений орла можно ожидать? Как покажет последующий анализ, эта величина ведет себя как 9 (18 тт). Докажем сначала, что математическое ожидание длины наибольшей последовательности орлов представляет собой О (18п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
