Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Оценка вероятности одного события
Loading...
Do curso por Moscow Institute of Physics and Technology
Случайные графы
63 classificações
Na lição
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Значит, давайте думать, как ее действительно найти.
Давайте для начала фиксируем какую-нибудь одну вершину x,
попадающую в дополнение до объединения множеств C1...
Cm. Вот фиксируем какую-то совершенно
конкретную вершину x.
Нам нужно, чтобы каждая такая вершина обладала каким-то свойством.
Ну вот давайте пока с одной такой вершиной разберемся.
Чему равна вероятность того,
что из этой вершины из
этой вершины в множество C1
идет хотя бы одно ребро?
Ну это ровно та вероятность, которая нас вообще-то интересует.
Вернее, нас интересует вероятность того, что из нее, из x,
идет хотя бы одно ребро сюда, хотя бы одно ребро в C1,
хотя бы одно ребро в C2, хотя бы одно ребро в Ci, хотя бы одно ребро в Cm.
Но вот мы совсем, так сказать, укоротили пока наше событие,
и хотим просто найти вероятность того, что из вершины x ну хотя бы вот в это
множество C1 выделенное идет не менее одного ребра.
Как бы это посчитать?
А очень просто.
Смотрите.
Вероятность того, что из этой
вершины в C1 нет
ребер, наоборот, отрицание вот этого события.
Здесь мы хотим посчитать вероятность того, что идет хотя бы одно ребро.
Ну давайте посмотрим на вероятность того, что в C1 вообще ни одного ребра не идет.
Эта вероятность очевидно, чему равна.
1/2 — это вероятность отсутствия ребра, правильно?
Каждое ребро отсутствует с вероятностью 1/2.
Но из вершины x в вершины множества C1, в принципе, может идти ровно a1 ребер.
Ну это понятно, потому что C1 состоит из a1 вершин, и в нашем случайном
графе из x в C1 могло бы идти вплоть до a1 ребер.
Ну это означает, что 1/2 возводится просто в степень a1.
Все вот эти вот потенциальные a1 ребер пропадают.
Их нет.
Ну стало быть, вероятность, которая нас интересовала сначала,
вот эта, это есть 1 − (1/2) в степени a1.
Мы просто ищем вероятность дополнительного события.
Вероятность отрицания.
Вот.
Ну точно так же вероятность того,
что из x в какое-либо C
i-тое идет не менее одного
ребра не менее, чем одно ребро,
эта вероятность вычисляется, как 1 − (1/2),
но уже в степени a i-тое, потому что в C i-том у нас уже a i-тое вершин.
Так.
Потрясающе.
По-моему, понятно.
А теперь смотрите.
Вот очень важный момент.
Событие, состоящее в том, что x соединена ребром с хотя бы одной вершиной из
множества C1, x соединена ребром хотя бы с одной вершиной из C1,
событие, состоящее в том, что x соединена ребром хотя бы с одной вершиной из Ci,
из c2, из c3, из чего угодно, все эти события очевидно взаимно независимы,
потому что множества C i-тые попарно не пересекаются.
События, описанные вот в этих строчках, все взаимно независимы.
Поэтому вероятность того, вероятность того,
что из вот этой конкретной вершины
x в каждое множество, в каждое множество
C i-тое идет хотя бы одно ребро,
эта вероятность за счет взаимной независимости представляет
собою произведение только что найденных вероятностей.
Значит, эта вероятность равна произведению
по i от 1 до m * 1 −
(1/2) в степени a i-тое.
Вероятность того, что данная конкретная вершина x смежна и с какой-то
вершиной из С1, и с какой-то вершиной из С2, и так далее вплоть до Сm, эта
вероятность за счет взаимной независимости пересекающихся в ее определении
событий равна произведению этих самых вероятностей событий, которые мы нашли.
Видите, вроде бы как не очень сложно,
но требуется много раз повторить, чтобы как-то это осознавалось.
Вот.
На самом деле все очень просто.
Замечательно.
Смотрите, это же мы зафиксировали x, а нам нужно найти
вероятность того, что вот это все, вот это все, что здесь написано,
выполнено не только для данного конкретного x, но для любого x отсюда.
Но опять независимость приходит на помощь.
Смотрите, если у нас есть какая-то другая вершина x', то то событие,
вероятность которого для нее мы тоже уже посчитали, то есть, событие,
состоящее в том, что x' соединена с кем-то отсюда, с кем-то отсюда, с кем-то отсюда,
вот это новое событие никак не зависит от события, которое порождено вершиной x.
То есть, тот факт, что из x есть вот такой веер ребер,
не зависит никак от того факта, что из x' есть какой-то аналогичный веер ребер.
Никак не зависит, потому что ребра, которые выходят из вершины x',
и ребра, которые выходят из вершины x, образуют непересекающиеся множества.
Это разные ребра.
Поэтому зависимости никакой нет.
У нас граф так строился, что если ребра в нем разные, то и зависимости не будет.
Если ребра разные, то и зависимости не будет.
Вот. Поэтому получается,
что искомая вероятность, то есть,
вероятность события B с индексами a1...
am, C1...
Cm — это есть просто найденная нами величина
произведения по i от 1 до m * (1 − (1/2) в степени a i-тое),
возведенное в степень вот здесь вот,
в степень, которая равна количеству всех возможных x,
находящихся вне объединения множеств C1...
Cm. То есть, в степень, равную n − a1 −...
− am.
Это я из n, из общего числа вершин, вычел количество вершин в C1, потом
вычел количество вершин в непересекающемся с ним C2, ну и так далее вплоть до Cm.
Вот столько x, и для каждого x вероятность того,
что x смежен с каждым из наших C i-тых, она вот равна такому произведению.
Поэтому вероятность того,
что это верно для всех x — это вот такая степень от этого произведения.
О! Ужас!
Страх и трепет!
Вообще!
Да ладно, нет.
Ну все не страшно.
Ну давайте смотреть на эту бяку или на эту красотищу, я не знаю уж,
как это правильно аттестовать, на самом деле, кто как смотрит.
Ну давайте смотреть.
Вспомним, какие у нас есть неравенства для величины a i-тое.
Вообще-то мы знаем, что для любого i a i-тое не превосходит 1 − δ * log2 n.
Сейчас у нас будет мой любимый тетрис, сейчас все будет проваливаться.
Все эти формулы очень красиво, аккуратно свернутся во вполне компактную запись.
Но всему свое время.
Смотрите.
Если a i-тое, a i-тое не превосходит чего-то,
значит, (1/2) в степени a i-тое — она ≥,
нежели (1/2) в степени того, чего не превосходит a i-тое, правильно?
Потому что 1/2 < 1.
Чем в большую степень половинку мы возводим, тем меньшее число мы получаем.
То есть, в свою очередь, давайте вот тут напишем.
(1/2) в степени a i-тое ≥ (1/2)
в степени (1 − δ) * log2 n,
ну и тут надо произвести первое сбрасывание уровня тетриса,
надо заметить, что (1/2) в степени log2 n — это просто 1 / n.
То есть, у нас получается 1 / n в степени (1 − δ).
Вот довольно симпатичная запись.
(1/2) в степени a i-тое ≥ этого выражения, но она-то стоит со знаком −.
Поэтому произведение по i от
1 до m * (1 −(( 1/2) в степени a i-тое)))
не превосходит произведение по i от 1
до m * (1 − 1 / n в степени (1 − δ)).
Теперь замечаем, что величины, которыми мы оценили каждую из скобок,
от i никак не зависят, поэтому у нас просто получается (1
− 1 / n в степени (1 −δ)), и все это в m-той степени.
Видите, ну уже как-то, в общем, поприятнее стало выглядеть.
на самом деле.
Ну, и дальше мы замечаем что?
Что n – вот эта вот штука, n – a1 –...
– am это конечно же больше либо
равняется n – m (1 – δ) на log2 n Вот так вот.
Но это я просто опять каждую Ɐi сверху оценил, ну,
а значит, разность получается, наоборот, больше либо равной такой величины,
ну, m потому что слагаемые все одинаковые после получения оценки стали, ну,
вот тогда вот тут будет m.
Такую штучку мы с вами оценивали, это получается больше либо равно n пополам.
То есть вот самих иксов, их довольно много, иксов, которые расположены вне
множества с1, объединенный и так далее, объединенного с C.
То есть в итоге мы замечаем, что вот это число опять меньше единицы, поэтому
если мы его возводим в какую-то меньшую степень, то мы получаем только больше.
И стало быть оценка пойдет в ту сторону, в которую нам нужно.
Получается вот так.
1 – 1 на n в степени 1 – δ m на n пополам.
Просто каждая скобка оценилась вот так,
как m-тая степень и теперь она еще возводится в степень n пополам, потому что
такова оценка для вот этого показателя, все совершенно естественно и благоразумно.
Вот. Ну, давайте еще немножко это оценим.
Я вот сейчас себе местечко такое отделю, я думаю, что нам его должно хватить.
Как обычно, переписываем это в виде e в степени m на n пополам,
умножить на log от 1 – 1 на n в степени 1 – δ.
Вот такая вот штука, логарифм от 1 – x.
Мы неоднократно в рамках этого курса оценивали сверху просто величиной – x.
Вот у нас x логарифм от 1 – x не превосходит – x.
Пишем, не превосходит e в степени – m n пополам,
умножить на 1, поделить на n в степени 1 – δ.
Так.
И я начинаю думать, что я умудрился что-то потерять.
Не хотелось бы, чтобы это случилось.
Так, а, может быть, все и хорошо.
Нет, все хорошо.
Друзья, не пугайтесь.
Катарсис будет.
Все будет.
Так, все, все, все замечательно.
Так, все замечательно.
Давайте опять проваливать тэтрис, то есть давайте сокращать то, что можно сократить.
Смотрите, вот эта n сокращается вот с этой единичкой благополучно.
n в первой, n в первой, да?
Значит, что у нас остается?
У нас остается e в степени – m, помноженная на n в положительной
степени δ, тут у нас n – δ в знаменателе, но оно перекочевывает в числитель.
Ну, и поделить на двойку, которая, конечно,
в итоге никакой роли по отношению к оценке не сыграет.
Так.
Ну, в принципе, можно оставить в таком виде, а можно еще раз переписать.
Давайте, наверное, еще раз перепишем, воспользовавшись тем,
что m у нас это целая часть от n поделить на дважды 1 – δ на log2n.
Давайте перепишем.
Скажем, что это точно меньше или...
Ой, нет, извините, извините, нам же нужно неравенство в эту сторону.
Нам нужно доказать, что экспонента чего-то не превосходит.
Значит, наоборот, надо сказать, чего такая целая часть больше.
Ну, давайте напишем, например, что эта целая часть уж точно не меньше, чем n,
скажем, поделить на 4 log2n.
Товарищи, откуда я взял такую оценку, только не пугайтесь, это очень просто.
1 – δ меньше 1.
Поэтому, когда оно стоит в знаменателе, и мы хотим получить оценку снизу,
мы на него можем просто, нет, мы про него можем просто забыть,
давайте я скажу более хорошим русским языком.
Так, мы можем его просто забыть.
Вот, а кроме того, есть такое замечательное неравенство,
целая часть x уж никак не меньше, чем x поделить на 2,
если x больше либо равняется 1.
Конечно, такое неравенство имеет место, ну,
вот за счет этого неравенства и получаем n поделить на 4 log2n.
Ну, а здесь, стало быть, продолжаем оценку.
Давайте я вот сюда вот перемещусь, вот так красиво себе
отделю позицию, и напишу: e в степени –.
Смотрите, тут n.
Оно умножается на n в степени δ, вот видите, n это оценка для m.
n умножается на n в степени δ, значит, получится n в степени 1 + δ.
Это n в степени δ умножилось на n.
Дальше надо поделить на двойку и надо поделить на 4 log2n.
Итого получается 8 log2n.
Во какая компактненькая оценка.
Вот смотрите, я специально старался уместить это на данную доску,
потому что тут какая-то жуть, пусть даже красивая, но какая-то вроде необозримая
совершенно, а оценивается она вот такой компактненькой-компактненькой штучкой.
Непонятно, как эта штучка в итоге сработает, но с
другой стороны сразу видно, что эта штучка стремится к нулю очень-очень быстро.
Ой, как быстро.
Смотрите, как e в степени – n в какой-то степени строго больше единицы,
но, правда, поделенной на 8 log2.
Вот они-то нам никак не помешают в конечном счете.
Но, заметьте, мы пока оценили вероятность только данного конкретного события.
Теперь полученную нами оценку надо аккуратненько просуммировать,
сначала по всем c1 cm с фиксированными a1 am,
а потом еще и по всем способам выбрать числа a1 am.
Как только мы это просуммируем и убедимся в том,
что за счет суммы много слагаемых не набежало,
и все равно стремление к нулю есть, так сразу у нас будет доказательство теорем.
Ну, сейчас продолжим.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
