Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Оценивание математического ожидания
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
63 ratings
From the lesson
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Прекрасно!
Ну давайте начнем с простого: найдем математическое ожидание случайной
величины ξ.
На это у меня места пока хватит.
Ну смотрите.
Чему равняется среднее число изолированных вершин в случайном графе?
Ну вообще это стандартное упражнение на то,
что называется линейностью математического ожидания.
То есть, надо ξ представить в виде какой-то суммы и воспользоваться тем,
что математическое ожидание суммы всегда вообще равно сумме математических
ожиданий.
Вот всегда.
Это классический факт, который называется линейностью матожидания.
Давайте ξ представим в виде суммы.
Смотрите.
Это математическое ожидание суммы (ξ1 +...
+ ξn), где, давайте я вот здесь напишу, ξ i-тое — это,
естественно, случайная величина, которая, как обычно, должна зависеть от графа.
Аргументом является граф.
Так вот, ξi (G) — это такой индикатор так называемый.
Это случайная величина, которая принимает только два значения: 1 или 0.
Значит, она принимает значение 1,
если вершина i изолирована в случайном графе G.
Изолирована вот в этом случайном графе G.
На нас спустился граф, и мы смотрим: вот эта конкретная вершина i,
она изолирована в нем или нет?
Если изолирована — все, ставим 1.
0 — в противном случае.
Ну понятно, мы здесь просуммировали по всем возможным вершинам нашего графа.
Вершины, не забывайте, это просто числа от 1 до n,
мы так договорились еще на прошлой лекции.
Ну вот мы просуммировали по всем возможным вершинам такие индикаторы.
Мы посмотрели на каждую вершину и сказали,
является она изолированной в нашем графе или не является.
И вот сколько раз на вопрос об изолированности мы ответили «да»,
столько у нас изолированных вершин и получится.
Ну а это и есть случайная величина ξ.
То есть, ξ,
равная количеству изолированных вершин — это сумма вот таких индикаторов.
Теперь пользуемся линейностью математического ожидания.
Получаем Mξ1 +...
+ Mξn.
И все, что остается сделать — это найти математическое ожидание ξ i-того.
Ну, математическое ожидание случайной величины,
которая принимает только два значения, 1 или 0, оно вычисляется более чем просто.
Надо взять 1, умножить на вероятность того события,
при котором получается 1, и прибавить 0, умножив на вероятность отрицания.
Ну, 0, умноженный на вероятность отрицания — и в Африке 0, поэтому достаточно просто
посчитать вероятность того, что данная вершина является изолированной.
Ну, для этого удобно нарисовать картинку.
Вот у нас есть какая-то конкретная вершина i,
и мы хотим посчитать математическое ожидание ξ i-того, то есть,
вероятность того, что именно эта вершина является изолированной в случайном графе.
Ну, рисуем все остальные вершины в виде такого, если хотите, облачка.
Облачко состоит, конечно же, из n − 1 вершины,
потому что всего в графе n вершин, а i вершина выделенная.
И вот эта вершина i, она будет у нас изолированной тогда и только тогда,
когда ни одного из указанных на картинке ребер нет в случайном графе.
Должны одновременно отсутствовать вот эти вот конкретные n − 1 ребер.
Ну с какой вероятностью у нас каждое конкретное отдельно взятое ребро в
случайном графе отсутствует?
Понятно, что вероятность отсутствия отдельного ребра есть просто (1 − p).
Но тогда вероятность того, что отсутствуют все вот эти (n − 1) ребер — это (1 − p)
в (n − 1) степени, потому что отсутствия ребер — это события взаимно независимые.
Мы перемножаем их вероятности.
Таким образом, мы получаем, что каждое из математических ожиданий,
давайте я вот здесь это напишу, равняется просто (1 − p) в степени (n − 1).
Таким образом, вся сумма равняется n * (1 − p) в степени (n − 1).
И у меня еще немножечко остается места на вот этой вот доске.
Понимаете, да?
Про бычка.
Доска кончается.
Но у меня немножечко места остается.
Я сейчас найду, куда стремится вот эта величина при n,
стремящемся к бесконечности, и, я думаю,
что наступит некий катарсис, потому что, ну, это будет настоящее просветление.
Вы наконец поймете, где важно, что c < 1.
В каком месте играет роль вот это вот условие, с которым мы, вроде как,
имеем дело.
Вот. Ну давайте посмотрим на эту функцию,
как она себя ведет.
Вот здесь вот это напишем.
Значит, у нас получается n.
Давайте я напишу так: (1 − p) я представлю как e в степени (ln (1 − p)).
То есть, у меня получится (n − 1) * ln (1 − p).
Ну, это совершенно понятно.
А дальше я вспомню, что p — это у меня величина, которая стремится к 0 при n,
стремящемся к бесконечности.
И здесь, кстати, совершенно неважно: c < 1, c > 1.
В этом месте просто важно, что p ведет себя, как (c * ln n) / n.
То есть, (c * ln n) / n — безусловно, стремящаяся к 0 функция.
И я могу заметить,
что ln (1 − p) в этом режиме асимптотически ведет себя так же, как −p.
Ну давайте это явно запишем.
Значит, у меня получается n * e в степени (n − 1),
а логарифм от (1 − p) я запишу, как −p.
Ну, это просто следствие, если хотите, из разложения логарифма в ряд Тейлора.
Понятно, что в ряде Тейлора первое слагаемое — это как раз −p.
Ну а все остальное идет в o (1), как водится,
и записывается это вот так: 1 + o (1).
Функция какая-то, которая стремится к 0 с ростом n при n,
стремящемся к бесконечности.
Дальше давайте заметим, что вот эта величина (n − 1),
ну конечно, она тоже асимптотически просто равна величине n.
То есть, можно это еще вот так вот переписать.
Это будет n в степени −...
Ой, извините.
n * e в степени −np.
Я заменяю (n −1) на n.
Естественно, когда я заменяю (n −1) на n,
я должен еще написать * (1 + o (1)), но когда я перемножаю две функции,
стремящиеся к единице, то я получаю тоже какую-то функцию, которая стремится к 1.
То есть, я опять могу написать таким вот образом.
Естественно, слушатели должны понимать,
что вот это o (1) — не то же самое, что вот это.
Ну, я думаю, что вы это прекрасно понимаете, товарищи.
Значит, замечательно.
И вот теперь наконец настает момент катарсиса, потому что я подставляю
сюда вместо p (c ln n) / n У меня получается n *
e в степени − Поделить на n, умножить на n — чпок!
Сократилось.
Не кокнул?
Никого?
Хе-хе.
Ну как мог кокнуть?
Ну в знаменателе n, в числителе n — сократилось.
Значит, тут осталось c * ln n.
Ну, это, собственно, числитель вероятности,
который выжил в результате сокращения.
Вот так.
Ну и умножить там на какую-то вот эту вот штучку ничтожную,
которая стремится к 1, (1 + o (1)).
Замечательно.
Сейчас оно все дальше посыпется, как в тетрисе.
Смотрите.
e в степени −ln n это ведь 1 / n, правильно?
e в степени −ln n — это 1 / n.
Ну еще в степени c и в степени «вот эта ерунда».
Переписываем.
Так.
Одно n вот тут, а в знаменателе
оказывается n в степени c * (1 + o (1)).
n в степени c *( 1 + (o (1))).
Вот так.
Ну и вот вам катарсис,
потому что условие c строго < 1, не ≤,
а именно строго < 1 означает, что, начиная с некоторого n,
c, помноженное вот на эту фигнюшку, тоже строго < 1.
c строго < 1, она умножается на нечто, стремящееся к 1.
Ну, значит, начиная с какого-то момента это произведение оказывается строго < 1.
То есть, n в 1 степени делится на n,
которое возводится в степень, строго меньшую 1.
Ну то есть это n в какой-то строго положительной степени,
ни к какому 0 не стремящееся.
Это означает, что все, что здесь написано, вся вот эта дробь,
стремится к + бесконечности при n, стремящемся к + бесконечности.
То есть, когда число вершин случайного графа растет,
математическое ожидание числа изолированных вершин в этом случайном
графе тоже стремится к бесконечности.
Это еще, внимание, вот тоже очень важный момент.
Это еще вовсе не означает,
что почти наверняка в случайном графе есть изолированная вершина.
Для того, чтобы это доказать, как мы помним,
нам нужно убедиться в том, что вот эта дробь стремится к 0.
Но одним из важнейших условий первоначальных для того,
чтобы вообще эта дробь смогла стремиться к 0, является, в том числе,
стремление к бесконечности матожидания.
Потому что если бы оно к бесконечности не стремилось, то, конечно, можно было бы
воспользоваться, наоборот, неравенством Маркова и убедиться в том, что в случайном
графе нельзя говорить о наличии с высокой вероятностью изолированной вершины.
Вот, оказывается, где нужно, что c < 1.
Ну и сейчас мы докажем все-таки,
что дисперсия поделить на квадрат матожидания стремится к 0.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
