Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 280
Текст из файла (страница 280)
Комбинаторика и теориа вероятности Ь(/с; и, р) 6(/с; и, р) 3сс3 Следствие В.5 Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, и вероятностью неудачи, равной с = 1 — р. Тогда для О < Ь < ир/2 вероятность того, что будет получено менее lс успешных исходов, составляет менее половины от вероятности получения менее Й + 1 успешного исхода. Доказательства. Поскольку й < пр/2, имеем /сс3 (пр/2)д ир — Й ир — (ир/2) (пр/2) с пр/2 (1, (В.42) так как д < 1. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов. Из теоремы В.4 и неравенства (В.42) следует, что вероятность получить менее 3с успешных исходов равна Рг(Х < Ц = ~ 6(с';и,р) < 6(lс;п,р) .
Таким образом, Р.(Х <Ь) У-,'—,'6(с;и,р) Рг(Х < к+ Ц Е'=о 6(г'п р) 2',, о 6(с;п,р) ~;с Ь(с';п,р) + Ь()с;п,р) ( 1/2, поскольку ь,1 6(с; п, р) < 6(к; и, р). Оценка для правого хвоста выполняется аналогично. Ее доказательство оставлено читателю в качестве упр. В.5.2.
Следствие В. б Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов. Тогда для пр < 3с < п вероятность Часть )сШ. Лривожениа: математические основы более чем Й успешных исходов равна Рг(Х ) Й) = ~ ~6(ь';и,р) с=а+1 < Ь(Й;и,р) . (и — Й)р Й вЂ” ир Следсшвие В.
7 Рассмотрим последовательность из и испытаний Бернулли с вероятностью успешного исхода каждого испытания, равной р, и вероятностью неудачи, равной д = 1 — р. Тогда для (ир+ и)/2 < Й < и вероятность более чем Й успешных исходов не превышает половины вероятности более чем Й вЂ” 1 успешных исходов. В следующей теореме рассматриваются и испытаний Бернулли; вероятность успеха в г-м испытании составляет рь Как видно из следствия из данной теоремы, ее можно использовать для оценки правого хвоста биномиального распределения, положив р, = р для всех испытаний. Теореме В.й Рассмотрим последовательность из и испытаний Бернулли, в которой в 1-м испытании (1 = 1,2,...,и) вероятность успеха равна р,, а неудачи — о; = 1 — р,. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов, а )с = Е [Х].
Тогда для т ) )с Рг(Х вЂ” )с > т) < ( — ) т Доказетельсшво. Поскольку при любом а ) О функция е * строго возрастающая по х, Рг(Х вЂ” )с > т) = Рг (еас» ") > е (В.43) где значение а будет определено позже. Использовав неравенство Маркова (В,ЗО), получим Рг (ео(Х-и) е еас) < Е [еас»-и)] е-ас (В.44) Теперь нужно оценить величину Е (е (» и)) н подставить подходящее значение а в неравенство (В.44). Начнем с вычисления Е )е (» и)).
Используя индикаторные случайные величины (см. раздел 5.2), положим Х, = 1(1-е испытание Бернулли успешно) при 1 = 1,2,..., и; т.е. Х; представляет собой случайную величину, которая равна 1, если 1-е испытание Бернулли успешно, и О, если оно неудачно. Таким образом, и х=~х,, Приеаяеение В. Комбинаторика и теория еероятноети )265 и согласно линейности математического ожидания п и а )екеЕ[Х]=Е ~~ Х, = ~~ Е[Х,) = ~~ р;, 1=1 1=1 1=1 откуда вытекает Чтобы вычислить Е [е (к Р)], подставим в это выражение найденное значение Х вЂ” )е и получим Е [еа(х-р)~ = Е [вам=,(х*-р,)') =Е Пе( ' Р) и = ПЕ [е (К' Р')) Е [еа(х,-Р~)~ еа(1-Р,) + еа(О-Р,) = Р;Еаж + дес аР' < р;еа + 1 < ехр(р;е ), (В.45) где ехр(х) обозначает экспоненциальную функцию: ехр(х) = е*. (Неравенство (В.45) следует из неравенств о ) О, щ < 1, е и < е н е "* < 1, а последняя строка — из неравенства (3.12).) Следовательно, п Е [еа(К Р)) = П Е [еа(»' Р')) 1=1 п < Пехр(р1е ) 1=1 = ехр ~ ~рее = ехр()ее ), (В.46) что следует из (В.24), поскольку случайные величины Х, являются независимыми в совокупности, что влечет независимость в совокупности случайных величин еа(к" Р') (см.
упр. В.3.5). Из определения математического ожидания !266 Часть И!1. Приеожеиия: мотеиимичесиие осиоеы поскольку !с = 1," рь Следовательно, из уравнения (В.43) и неравенств (В.44) и (В.4б) вытекает, что Рг(Х вЂ” 1е ) т) < ехр(!се — ат) (В.47) Выбрав а = М(т/!е) (см. упр. В.5.7), получим Рг (Х вЂ” !с ) т) < ехр(!сем("1и) — тЫ(т/а)) = ехр(т — т 1п(т/1с)) е" ( /п)" Применив теорему ВВ к последовательности п испытаний Бернулли с равной вероятностью успеха, получаем оценку для правого хвоста биномиального распределения.
Следсяевив В. Р Рассмотрим последовательность и испытаний Бернулли с равной вероятностью успеха р и неудачи о = 1 — р в каждом испытании. Тогда для т > пр Рг(Х вЂ” пр > т) = ~ Ь(!с;п,р) «м(ии+ ) — ( — ")' Доказательсявво. Согласно (В.37) получаем !с = Е [Х) = пр. Упражнения В.5.1 * Что менее вероятно: при бросании симметричной монеты п раз не получить нн одного орла или получить менее п орлов при бросании монеты 4п раз? В.5.1 * Докажите следствия В.б и В.7. В.5.5 * Покажите, что ь-1 /п'1, 1с )а' < (а+1)" Ь(!с;п,а/(а+1)) *=о для всех а ) О и всех )г, таких, что О < (с < па/(а + 1). 7267 Прияаженив В.
Каибинаторииа и теория вероятности В.5.4 * Докажите, что если О < 7г < пр, где О < р < 1 и д = 1 — р, то В.5.5 * Воспользуйтесь теоремой В.8, чтобы показать, что Рг(р — Х>т) < ~ ! (п — д)е 1 т для т > п — д. Аналогично воспользуйтесь следствием В.9, чтобы показать, что Рг (пр — Х > т) < ( — ) т для т > п — пр.
В.5.6 * Рассмотрим последовательность и испытаний Бернулли, в которой в г-м испытании (1 = 1,2,..., п) вероятность успеха равна ро а неудачи — ог = 1 — р;. Пусть Х вЂ” случайная величина, равная общему количеству успешных исходов, а д = Е (Х]. Покажите, что для т > О Рг (Х вЂ” д > т) < е " 7зн (УхаэалиЕ7 ДОКажнтс, ЧтО р,Е Он + рдЕ ж < Е 7З.
ЗатЕМ СЛЕдуйтЕ СХЕМЕ дОКаэательства теоремы В.8, используя это неравенство вместо неравенства (В.45).) В.5. 7 * Покажите, что выбор а = !п(т/7з) минимизирует величину правой стороны неравенства (В.47). Задачи В.1. Шары н корзины В этой задаче рассмотрим размещение п шаров по Ь различным корзинам. л.
Предположим, что все п шаров различны, а их порядок в корзине не имеет значения. Докажите, что имеется Ь" способов размещения шаров в корзинах. 6. Предположим, что все п шаров различны, а их порядок в корзине существенен. Докажите, что имеется ровно (Ь + п — 1)!/(Ь вЂ” 1)! способов размещения шаров в корзинах.
(Указпниег подсчитайте количество способов разместить в ряд п различных шаров и Ь вЂ” 1 неразличимых разделителей.) !268 Часть ргг!. Приложения: математнческне основы а Предположим, что все шары идентичны, а следовательно, их порядок в корзине не имеет значения. Покажите, что юличество способов, которыми можно разместить шары в корзинах, равно [~~„~) . (Указание! воспользуйтесь тем же способом, что и в части (б), только теперь шары также неразличимы.) г. Покажите, что если шары идентичны и ни в одной корзине не может находиться больше одного шара, то разместить шары в корзинах можно [„) способами.
ь д. Покажите, что если шары идентичны и ни одна корзина не должна остаться пустой, то разместить шары в корзинах можно ["ь ') способами в предположении, что п > Ь. Заключительные замечания Общие методы решения вероятностных задач впервые обсуждались в знаменитой переписке Б. Паскаля (В. Рааса)) и П. Ферма (Р. береппа1), начавшейся в 1654 году, и в книге Х. Гюйгенса (С.
Нцуйепа, 1657). Строгая теория вероятности началась с работ Я. Бернулли (Б Вегпон!И, 1713) и А. де Муавра (А. бе Мо(чге, 1730). Дальнейшее развитие теории вероятности связано с именами П. Лапласа (Р.Б. с!е 1.ар!асе), С.-Д. Пуассона (8.-13. Роизоп) и К.Ф. Гаусса (С.Р. Оаизз). Суммы случайных величин исследовались П.Л.
Чебышевым и А.А. Марковым. Аксиоматизация теории вероятности была выполнена А.Н. Колмогоровым в 1933 году. Оценки хвостов распределений приведены в работах Чернова (Озегпой) [65] и Хеффдинга (НоеФИВ8) [172]. Важные результаты о случайных юмбинаторных структурах принадлежат П. Эрдешу (Р. Еп160). Материалы по элементарной комбинаторике можно найти в книгах Кнута (Кпшй) [208]ь и Лю (1.ш) [236]; по теории вероятности — в книгах Биллингсли (ВИИпйа!еу) [45], Чанга (С1шп8) [66], Дрейка (1)та!се) [94], Феллера (Рейег) [103] и Розанова (Иохапоч) [298]. Имеется русский перевод: Д.
Кнут Искусство лрограммнрования, т. !. Основные алгорнлсны. 3-е ялд.— Мс И.Д. "Вильямс", 2000. Кроме топь уже после непнсення ленной кннсл вышел олерелной лом "Искусства лрограмннрованнлз полношъю ~осяяшенный вопросам комбннаторнкн: Д. Кнус. Искусство лрогранннроеання, т. Е, А Канбннаторные ал:оратмы, часть ! — М. И.Д.
"Внльямс", 2013 Приложение Г. Матрицы Г.1. Матрицы и матричные операции В этом разделе мы рассмотрим основные концепции теории матриц и некоторые их фундаментальные свойства. Матрицы и векторы Матрица (тапзх) представляет собой прямоугольный массив чисел. Например, О11 П12 4113 4121 4122 О23,6' '4 4 6 6 ) (Г.1) представляет собой матрицу А = (аб) размером 2 х 3, где для 1 = 1, 2 и 2 = 1, 2, 3 элемент матрицы, находящийся в строке 1 и столбце 2, обозначается как гн . Прописные буквы используются для обозначения матриц, а соответствующие строчные — для их элементов. Множество всех т х п-матриц действительных чисел обозначается как !й "" и в общем случае множество т х п матриц с элементами, выбранными из множества 5, — как о"-4"". Т)нгнслоннрованная (!талярове) матрица Ат получается из матрицы А путем обмена местами ее строк и столбцов. Так, для матрицы А из (Г.!) Ат= 25 С матрицами приходится сталкиваться в множестве различных приложений, включая (но не ограничиваясь) научные вычисления.
Если вы встречались с матрицами ранее, значит, ббльшая часть приведенного здесь материала будет вам знакома, но кое-что вы можете увидеть впервые. В разделе Г.1 рассматриваются основные определения и операции, а в разделе Г.2 — некоторые свойства матриц. Часть ЛП. Приважеааес математическое осиовы Вектор (чесгог) представляет собой одномерный массив чисел. Например, является вектором размером 3. Для обозначения векторов мы используем строчные буквы и обозначаем 1-й элемент вектора х как во Стандартной формой вектора будем считать векявор-слваябед (со)шпп чес1ог), эквивалентный матрице и х 1. Соответствующий веклвор-сверака (гоч чес1ог) получается путем транспонирования вектора-столбца: '=(2Зб). Единичным веклввран (цпй чесгог) е; называется вектор, 1-й элемент которого равен единице, а все остальные элементы равны нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
