Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Задача о существовании изолированной вершины в случайном двудольном графе
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Случайные графы
63 個評分
從本節課中
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, друзья, ну тут вынужден принести извинения, эту задачу я прочитаю со
шпаргалкой, потому что я не хочу упустить какие-нибудь технические детали,
но суть от этого, конечно, не поменяется.
Так, ну просто громоздкие обозначения.
Давайте рассмотрим тот же самый случайный граф, с которым мы имели дело в предыдущей
ситуации, когда считали матожидание, дисперсию, там, изолированных вершин.
Это граф G(n, n, p), то есть мы берем полный двудольный граф с одинаковыми
долями, и каждое ребро этого полного двудольного графа удаляем независимо от
всех остальных ребер с вероятностью (1 − p), сохраняем с вероятностью p.
Тут все понятно, но ужас состоит в том, что p — функция от n,
которую мы сейчас зададим весьма специфичным образом.
Это будет логарифм натуральный n минус повторный
натуральный логарифм n, и все это поделить на n.
Ну это я, признаю, это еще можно запомнить.
Вот давайте рассмотрим такую забавную вероятность ребра.
Предлагается найти вероятность того,
предельную вероятность того, что в таком случайном
графе есть хотя бы одна изолированная вершина в верхней доле.
Значит, нас интересует предел вероятности того,
что в верхней доле
есть изолированные вершины.
Ну понятно, на что эта задача.
Мы должны каким-то образом закрепить тот материал, который у нас был на лекции.
Мы тоже считали вероятности того, что где-то есть изолированные вершины и
доказывали, что, да, эти вероятности куда-то стремятся.
Вот здесь в верхней доле есть изолированная вершина.
Вот оказывается, что параметры подобраны таким образом впритык,
вот этот вот загадочный повторный логарифм выбран, в частности,
таким образом, чтобы эта вероятность на самом деле все-таки устремилась к единице.
Сейчас мы в этом убедимся, что в пределе при n,
стремящимся к бесконечности, такая вероятность равна единице.
Но в пределе, конечно.
Давайте обозначим буковкой x произвольную вершину верхней доли.
Ну то есть раньше мы их обозначали как-то конкретно: a1, ..., an.
Ну давайте x — это любая произвольная вершина в верхней доле.
[ШУМ] В
верхней, давайте целиком, доле.
Так, ну тогда нашу вероятность можно записать следующим
образом: это 1 минус вероятность того,
что x не является изолированной вершиной,
не изолированная вершина,
и вот эту вероятность надо просто возвести в n-ную степень.
Ну, смотрите, что такое вероятность того, что там есть изолированная вершина?
Это 1 вычесть вероятность того, что там,
то есть в верхней доле, нет изолированных вершин.
А что значит, что там нет изолированных вершин?
Это значит, что никакая из вершин верхней доли не является изолированной.
Вот мы фиксируем какую-то произвольную вершину и считаем вероятность того,
что она, вот эта конкретная вершина, не является изолированной.
Понятно, что события, отвечающие разным конкретным вершинам верхней доли,
события, состоящие в том, что вот эти вершины не являются изолированными,
они не зависят друг от друга, потому что ребра, которые выходят из вершины x,
и ребра, которые выходят из какой-то другой вершины, скажем, y, они все разные.
Из x выходят одни ребра, а из y какие-то совершенно другие.
Поэтому вот эти события взаимно независимые, и, как водится,
вероятность того, что каждое из них выполнено,
это n-ная степень вероятности того, что выполнено любое конкретное из них.
Вероятность того, что данная конкретная вершина не является изолированной.
Ну при этом понятно, что значение вот этой вероятности от x-то не зависит.
Именно поэтому я не стал перемножать по всем x из верхней доли разные
величины вот этих вероятностей.
Нет, они все одинаковые.
Для каждого x вот это число мы сейчас посчитаем, вероятность того,
что x не является изолированной, и аккуратненько в n-ную степень возведем.
Ну давайте думать, с какой вероятностью данная конкретная вершина
верхней доли не является изолированной.
Ну забавно то, что сейчас мы опять вот в этих скобках уже из
единицы вычтем вероятность того, что x является изолированной.
Такая будет вложенность вычитания из единицы,
то есть перехода к отрицанию данного события.
Ну понятно, x — конкретная вершина — является изолированной,
является изолированной, то есть все ребра вообще пропали,
все ребра пропали, с вероятностью (1 − p) в n-ной степени.
Было n ребер из этой вершины, и вот они все пропали.
Ну то есть у нас получается вот так: 1 минус,
а здесь снова (1 − (1
− p) Очень забавно выглядит, смотрите: 1 минус, 1 минус, 1 минус.
Такая вот глубокая вложенность.
Ну (1 − p) здесь в n-ой степени, конечно, что пропали все n ребер,
которые из данной вершины выходили, так, и вот это все в n-ной степени.
Выглядит, конечно, устрашающе.
Сейчас я погляжу в шпаргалку, чтоб не дай бог не наврать вам.
Не, ну, конечно, все правильно.
То есть вот эта вот вероятность того,
что данная конкретная вершина утратила все ребра, которые из нее выходили.
1 минус вот эта штука — это вероятность того, что хотя бы одно ребро сохранилось,
то есть x уже не является изолированной вершиной, мы возводим эту вероятность в
n-ную степень, вот как здесь, и из единицы вычитаем.
Итого мы получаем вероятность того, что в верхней доле есть изолированная вершина.
Такая вот симпатичная штука.
Ну а дальше надо пользоваться, конечно, элементами асимптотического анализа,
который мы с вами благополучно применяли на лекции.
А именно — представлять каждую такую штуку в виде экспоненты, и логарифмы,
которые окажутся в показателе экспоненты, асимптотически как-то раскрывать.
Ну вот сейчас посмотрим, как у меня здесь написано.
Давайте.
Равняется...
Вот эту вот первую единицу я пока сохраняю.
1 минус...
Вот эту тоже единицу, конечно, я сохраняю.
А вот (1 − p) в n-ной я записываю как e в степени n помножить
на логарифм от (1 − p).
В общем, у меня получается e в степени n логарифм от (1 − p).
Так.
И это все в n-ной степени, да, вот в этой n-ной степени.
Ну пока ничего особенно умного не произошло,
ровно такие штуки у нас происходили на лекции.
Так.
Теперь давайте даже не асимптотики писать,
а, скажем, снизу оценивать.
Так. Вот чтобы оценить снизу, надо,
понятное дело, логарифм тоже оценить снизу.
Видите, он тут стоит с минусом, но потом еще раз с минусом.
Поэтому логарифм от (1 − p) надо оценить не сверху, а снизу.
Если на лекции мы его оценивали сверху величиной (− p),
то сейчас мы его снизу оценим − p − p²/2.
Есть такая оценка.
Давайте я ее здесь напишу.
Логарифм от (1 − x) больше либо равняется − x − x²/2.
И вот этой оценкой я сейчас благополучно воспользуюсь.
Тогда у меня получится 1 − (1 −
e) в степени (− np −
np²/2), и все это, очевидно, в n-ной степени.
Так, сравниваем.
Да, нигде не ошибся.
Все вполне благополучно.
Шпаргалка спасает.
Так, ну что мы дальше с вами сделаем?
Ну давайте как-нибудь это снизу оценим.
А, ну понятно как, понятно как.
Мы сейчас сюда подставим вместо p нашу функцию.
У нас же p задано вот этим загадочным образом.
Сюда ее легко подставить.
Мы просто честно n умножим на p.
Вот эта n пропадет.
Появится разница логарифма и повторного логарифма,
и мы честно эту разницу нарисуем.
Так.
А что касается p²/2...
Так, сколько у нас минусов у этого p²?
Один минус, второй минус, третий минус.
То есть если мы хотим продолжить оценивать вот эту величину снизу,
надо p вот в этом месте оценить сверху,
оценить сверху, сказать, например, что p не превосходит просто
логарифм n поделить на n и на этом благополучно утешиться.
Так, ну давайте.
Больше либо равно...
больше либо равно 1 минус,
1 минус...
так, не в степени (давайте я сюда подсмотрю) минус
логарифм n плюс повторный логарифм n.
Так, это я просто n умножил на p, как и обещал,
минус логарифм n плюс повторный логарифм n, все вполне понятно.
Так, а здесь минус np квадрат пополам.
Так, ну еще раз, двойкой я могу пренебречь,
если мне очень хочется, потому что p квадрат пополам меньше, чем p квадрат,
с минусом больше, с минус меньше, с минусом больше — все в порядке.
То есть я здесь могу написать np квадрат, и даже более того,
могу написать просто n помноженное на квадрат вот этой дроби.
То есть у меня получится логарифм в квадрате n — это я возвел
в квадрат логарифм, я его делю на n в квадрате, но потом на n умножаю.
То есть у меня получается просто деление на n,
скобка закрывается и в n-ную степень возводится.
Значит, не пугайтесь, что я вот тут вот много чем пренебрег,
зато вот здесь я все аккуратно сохранил, и это по делу.
То есть повторный логарифм это никакая не загадка, она действительно сейчас
сработает некоторым образом, и вы убедитесь в этом благополучно.
Так, ну хорошо.
Давайте прямо точное равенство напишем, что у нас получится, я сейчас перепишу
со шпаргалки, чтобы особо не задумываться, а потом вам аккуратно прокомментирую.
Значит, у меня будет 1 минус 1 минус
логарифм n поделить на n в
степени 1 прибавить
логарифм n деленный на n (слишком большую черточку написал,
вот так), логарифм n деленный на n и это все в n-ной степени.
Ну сейчас будем разбираться почему это так, не должно быть сложно.
Так, ну 1 минус 1 минус — это просто повторяется,
тут ничего нового не произошло.
Что такое логарифм n в числителе?
Э-э-э-э, это e в степени повторный логарифм n,
и он совершенно по делу, то есть вот этот, казалось бы, ничтожный повторный логарифм,
попавший в показатель экспоненты, при эскпоненцировании превращается
во вполне себе уже осязаемый однократный логарифм.
Вот это он — e в степени повторный логарифм.
Дальше, e в степени минус логарифм n — это 1 поделить на n,
вот это вот n в первой степени, которое стоит в знаменателе,
n в первой степени — это как раз e в степени минус логарифм n.
Ну а e в степени минус логарифм в квадрате n поделить на n
превратилось вот в эту штуку, в n в степени логарифм n поделить на n.
Ну смотрите, давайте, вдумайтесь: значит,
логарифм в квадрате n — это логарифм n умножить на логарифм n.
Правильно?
Логарифм на логарифм.
Если вы e возводите в степень просто логарифма с минусом,
то вы получаете деление на n, правильно?
Но вы вот это вот n в знаменателе вы еще потом
возводите в степень логарифм n поделить на n, потому что
вы квадрат логарифма представили как логарифм умножить на логарифм.
Один логарифм дал вам вот это вот n в знаменателе, а оставшийся логарифм,
вместе со знаменателем n, перекочевал благополучно вот сюда.
Ну вот такое вот искусство быстро в уме возводить что-то в степени логарифма.
Не кажется, что что-то запредельное, но вот так вот, да.
Причем вот эта вот штучка — логарифм n поделить на n — это фигня, на самом деле,
она сейчас никакой роли играть не будет.
Дело в том, что n, возведенное вот в эту степень стремится к единице,
при n стремящемся к бесконечности, не играет никакой роли,
не дает серьезного вклада в нашу асимптотику.
Вот, ну я прошу прощения, сейчас надо снова переписать это в виде экспоненты.
Значит, давайте запишем это: 1 минус,
а вот эту вот степень я опять представлю как экспоненту.
То есть учитесь, учитесь, вот такие вот экспоненты писать очень полезно.
Значит у меня получится e в степени n на логарифм от вот
этой разности (1 минус логарифм n
поделить на n в степени 1 плюс логарифм n на n).
Так, вот такая вот бяка, это, естественно, все в показателе экспоненты.
Ну что я могу сделать?
Я могу оценить вот этот логарифм сверху уже, как мы на лекции делали,
оценить его сверху просто вот этой вот величиной со знаком минус.
То есть логарифм от 1 минус x не превосходит минус x,
не превосходит минус вот эта штука, да?
Вот. С этим минусом у меня как раз получится
больше либо равно 1 минус e в степени
минус n на логарифм n вот на этот, да?
поделить на n в степени 1 плюс логарифм n, поделенный на n.
Я уж прошу прощения, этот логарифм n получается меленький,
маленький такой, но это неважно, он все равно роли не играет.
Так, это знак умножения, ну и видно: здесь у нас n в первой,
а здесь n почти в первой, то есть единичка и плюс что-то очень маленькое.
Значит, вот это вот n кокается вместе с этой единицей,
у меня в итоге получается такая вот штука,
у меня получается единица минус
e в степени минус логарифм n поделить
на n ну вот в этой степени логарифм n поделить на n.
Ну давайте я еще раз прокомментирую, значит, n возведенный в степень
логарифм n поделить на n — вот тот самый, который у меня вот тут в знаменателе,
это то же самое, что e в степени логарифм в квадрате n поделить на n, но функция,
стоящая в показателе экспоненты стремится к нулю довольно быстро,
то есть все это стремится к единице.
Ну и, соответственно, можно переписать, давайте это в скобки возьмем,
это просто пояснение, все вот это можно переписать так: 1 минус e в степени,
ну давайте, минус (1 плюс o (маленькое) от единицы).
1 плюс o (маленькое) от единицы — это и есть как раз стремление к одному,
которое написано в скобках.
Вот. Ну а дальше надо умножить на
содержательный логарифм.
Ну и, собственно говоря, вроде все понятно, потому что когда n стремится
к бесконечности, такая вот отрицательная экспонента благополучно уходит в ноль, но,
вычитаясь из единицы, она дает нам обещанную асимптотику 1 при n,
стремящимся к плюс бесконечности.
И мы доказали, что в высокой вероятность, то есть асимптотически почти наверное,
в верхней доли есть изолированная вершина,
коль скоро вероятность вот так вот тонко устроена.
Вот нетрудно подумать и заметить, что если мы чуть-чуть еще сдвинемся,
то уже вот так не получится.
Вероятность того, что есть изолированная вершина, перестанет стремиться к единице.
Подумайте над этим, это довольно забавно.
