Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 32
Текст из файла (страница 32)
Вероятность того, что при очередном подбрасывании выпадет орел, равна 1/2. Пусть Агь — событие, когда последовательность выпадений орлов длиной не менее Й начинается с г-го подбрасывания, или, более строго, Агь — событие, когда при й послеловательных подбрасываниях монеты г, г + 1,...,1+ 1с — 1 (1 < )т < п и 1 < г < п — 1г+ 1) будут выпадать одни орлы. Поскольку подбрасывания монеты осуществляются независимо, для каждого данного события А;ъ вероятность того, что во всех к подбрасываниях выпадут одни орлы, определяется следующим образом: Рг(Аьь) = 1/2~. (5.9) Для )г = 2 ~18 п1 можно записать Рг ( 41 з Ок п) ) = 1/2 Рк "1 ~< 1/2 1Я" = 1/и так что вероятность того, что последовательность повторных выпадений орлов длиной не менее 2 ~18п1 начинается с 1-го подбрасывания, довольно невелика. Имеется не более и — 2 ~18 и ~ + 1 подбрасываний, с которых может начаться указанная последовательность орлов.
Таким образом, вероятность того, что последовательность повторных выпадений орлов длиной не менее 2 ~18п1 начинается при любом подбрасывании, равна и — 2 Ок и) +1 е-2 Ок и) -)-1 д Д Аггрк) < Е „г<Х 1=1 1=1 =1 Справедливость этого соотношения следует из неравенства Буля (В.!8), согласно которому вероятность объединения событий не превышает сумму вероятностей отдельных событий.
(Заметим, что неравенство Буля выполняется даже для тех событий, которые не являются независимыми.) Теперь воспользуемся неравенством (5.10) для ограничения длины самой длинной последовательности выпадения орлов. Пусть Б (т' = О, 1, 2,..., и) — событие, Часть 1. Основы 162 когда длина самой длинной последовательности выпадения орлов равна 21 В со- ответствии с определением математического ожидания п Е [Ь] = ,'1 у Рг1Ь ). у=о 15.1 1) Можно попытаться оценить эту сумму с помощью верхних границ каждой из величин Рг1Х, ) аналогично тому, как это было сделано в неравенстве 15.10). К сожалению, этот метод не может обеспечить хороших оценок. Однако достаточно точную оценку можно получить с помощью некоторых интуитивных рассуждений„которые вытекают из проведенного выше анализа.
Присмотревшись внимательнее, можно заметить, что в сумме 15.11) нет ни одного слагаемого, в котором оба множителя — ? и Рг11,5) — были бы большими. Почему? При ,з > 2 [1к п~[ величина Рг(Ту) очень мала, а при 2 < 2 [1ки[ оказывается невелико само значение ~. Выражаясь более формально, можно заметить, что события Ц, з = О, 1,..., п несовместимые, поэтому вероятность того, что непрерывная последовательность выпадения орлов длиной не менее 2 ~1бт1[ начинается с любого подбрасывания монеты, равна ~;," 11 „1 Рг(Ту). Согласно неравенству 15.10), мы имеем ~"" 211 и) Рг (Ьу) < 1/и. Кроме того, из 2 " „Рг (Ту) = 1 вытекает Рг (Ьу) < 1.
Таким образом, мы получаем: п 2 11я и)-1 и Е[Ц = ~ З'Рг(Ц) = ~~1 уРг(Ьу)+ ~ ~Рг(Ц) < у=о у=о 2=211яп) 211я п1-1 и < ~~1, [2 ~1бгг'[) Рг(Е)) + ~ пРг(Ц) = у=о 5=2йяи1 211я и)-1 и = 2 [1й1з[ ~~1 Рг115) +т1 ~~1 Рг(Е)) < у=о 5=211яп) < 2 [1к п~ 1+ п [1/гг) = О [1й т1) . Рг (А1. Пяи1) = 1/2т11кп1 < 1/и". Таким образом, вероятность образования непрерывной цепочки из последователь- ных выпадений орла, имеющей длину не менее т ~1дп[, не превышает и/и" = = 1/пт 1.
Это утверждение эквивалентно утверждению, что длина такой цепочки меньше величины т [1кп[ с вероятностью не менее чем 1 — 1/пт 1. Шансы на то, что длина последовательности непрерывных выпадений орла превысит величину т [1яп'[, быстро убывает с ростом т. Для т > 1 вероятность того, что последовательность т [1я п~ начнется с г-го подбрасывания, равна Глава 5.
Вероятностный анализ и рандомизированные алгоритмы 163 1 1 1 йй1яп)/2!.г = 21(!кл)/2) ~ я Таким образом, вероятность того, что последовательность непрерывного выпадения орлов длиной не менее ((1бп)/2) не начинается с 1-го подбрасывания, не превышает величину 1 — 1/т/й. Поскольку все 1и/'1(1бп)/2Д~ групп образуются из взаимно исключающих независимых подбрасываний, вероятность того, что каждая такая группа не будет последовательностью выпадений орлов длиной ((13 и)/2), не превышает величину / /-) (л/Ц1ал)/2Д) ( /-)и/Ц1кл)/2)-1 < (1 ~/~-)2п/1ап-1 < Е-!А/!яи-1)/~'л = О (Е ~я") = О (1/П) В приведенной выше цепочке соотношений было использовано неравенство (3.11), 1+ я < е*, и тот факт, что при достаточно больших п справедливо соотношение (2п/1я п — 1)/тЯ ) 1я г! (при желании вы можете в этом убедиться самостоятельно).
Таким образом, вероятность того, что длина самой большой последовательности выпадений орлов превосходит величину ~(!б п)/2~, равна Рг(Ц) > 1 — О(1/и). 5=0!я Уг)-1-1 (5.12) В качестве примера рассмотрим серию из и = 1000 подбрасываний монеты. Вероятность того, что в этой серии орел последовательно выпадет не менее 2 (1б и'! = 20 раз, не превышает 1/и = 1/1000. Вероятность непрерывного выпадения орла более 3 (1б и"! = 30 раз не превышает 1/п2 = 1/1000000.
Теперь давайте рассмотрим дополняющую нижнюю границу и докажем, что математическое ожидание длины самой длинной непрерывной последовательности выпадений орлов в серии из и подбрасываний равно Й (1я и). Чтобы доказать справедливость этого утверждения, разобьем серию из и подбрасываний приблизительно на п/з групп по з подбрасываний в каждой. Если выбрать з = ~(1б п)/2), то можно показать, что с большой вероятностью по крайней мере в одной из этих групп окажутся все орлы, т.е, самая длинная последовательность выпадения орлов имеет длину как минимум з = Й (1кп).
Затем мы покажем„что математическое ожидание длины такой последовательности равно Й (1я п). Итак, разобьем серию из и испытаний на несколько групп. Количество групп должно быть не менее 1г!/'1(13 и)/21); их длина не превышает Ц1б и)/2) подбрасываний. Оценим вероятность того, что в каждой из групп выпадет хотя бы по одной решке. Согласно уравнению (5.9), вероятность того, что в группе, которая начинается с 1-го подбрасывания, выпадут все орлы, определяется как Часть 1. Основн 164 Теперь можно вычислить нижнюю границу математического ожидания длины самой длинной последовательности орлов. Воспользовавшись в качестве отправной точки уравнением (5.11) и выполнив преобразования, аналогичные проведенным при анализе верхней границы, с учетом неравенства (5.12), получим: и 1(!к и)/2) и Е[Ь] = ~~1,)'Рг(Ь ) = ~~! ) Рг(Ц)+ ) )'Рг(Ц) > з=л з=л 1=1(!К и)/2)+! 1(!а и) /2) и > ~ О Рг(Еу)+ ~~! [(1яп)/2]Рг(Ь ) = у=о 1=Ц1яп)/2)+1 1Оя и)/21 п = О ~~! Рг(Х1) + [(1яп)/2] ~~! Рг(й ) > у=о 1=1(1яп)/2)-1-1 > О+ [(1яп)/2] (1 — 0(1/и)) = П(1кп).
Как в предыдущем примере, более простой, но менее точный анализ можно провести с помощью индикаторных случайных величин. Пусть Хьь = 1(А1ь)— индикаторная случайная величина, связанная с последовательным выпадением не менее й орлов, начиная с 1-го подбрасывания монеты. Чтобы подсчитать количество таких последовательностей, определим: п-Ь+! х= ~ ~х,.
ип1 Вычисляя от обеих частей этого равенства математическое ожидание, получим: и-й+! и-Ь-!-1 Е[Х] =Е ~~! Х1 = ~~! Е[Хь] = п-Ь+! и-Ь+1 Рг(Ась) = 1=1 1=1 Подставляя в полученное соотношение различные значения /с, можно определить математическое ожидание количества последовательностей длины й. Если это число окажется большим (намного превышающим единицу), то последовательности выпадения орлов, имеющие длину й, встречаются с большой вероятностью. Если же это число намного меньше единицы, то встретить такую последовательность в серии испытаний маловероятно. Если )с = с1кп для некоторой положительной константы с, то мы получим: и — с1бп+ 1 п — с1яп+ 1 1 (с1яп — 1)/и / 1 2'!ки пс 11с-1 1зс-1 ~11с — 1 / ' Глава 5. Вероятностный анализ и рандомизированные алгоритмы 165 Если число с достаточно большое, математическое ожидание количества непрерывных выпадений орла длиной с!ли очень мало, из чего можно заключить, что это событие маловероятно.
С другой стороны, если с < 1/2, то мы получаем, что Е [Х] = 9 (1/п1~з 1) = 9 (п1~з), и можно ожидать, что будет немало последовательностей орлов длины (1/2) 1я п. Поэтому вероятность того, что встретится хотя бы одна такая последовательность, достаточно велика.
Исходя лишь из этих грубых оценок, можно заключить, что ожидаемая длина самой длинной последовательности орлов равна О (1б и). 5.4.4 Задача о найме сотрудника в оперативном режиме В качестве последнего примера рассмотрим одну из разновидностей задачи о найме сотрудника. Предположим, что в целях выбора наиболее подходящего кандидата мы не будем проводить собеседование со всеми претендентами. Мы не хотим повторять процедуру оформления на работу нового сотрудника и увольнения старого в поисках наиболее подходящей кандидатуры. Вместо этого мы попытаемся подыскать такого кандидата, который максимально приблизится к наивысшей степени соответствия должности. При этом необходимо соблюдать одно условие: после каждого интервью претенденту нужно либо сразу предложить должность, либо сообшить ему об отказе.
Как достичь компромисса между количеством проведенных интервью и квалификацией взятого на работу кандидата? Смоделнруем эту задачу таким образом. После встречи с очередным кандидатом каждому из них можно дать оценку. Обозначим оценку г-го кандидата как зсоге (1) и предположим, что всем претендентам выставлены разные оценки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
