Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Применение неравенства Чебышева
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
63 ratings
From the lesson
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Значит, доказательство.
И, как я уже сказал, начинаем с пункта 2, то есть,
вот у нас давайте я вероятность ребра буду писать просто буквой p, то есть,
я не буду уже указывать явно зависимость от n, все понимают,
что p — это на самом деле функция, которая зависит от числа вершин.
Ну вот p = (c ln n) / n,
и c у нас сейчас строго < 1.
Давайте введем такую вспомогательную случайную величину,
иначе как мы будем применять какие-нибудь неравенства Маркова или Чебышёва?
Значит, вспомогательная случайная величина ξ, она, естественно,
определена на случайном графе, то есть,
в качестве аргумента в нее подставляется граф, упавший на нас с неба, случайный.
И ξ (G) по определению — это есть количество
изолированных вершин в графе G.
Количество изолированных вершин в графе G.
Ну что значит изолированная вершина?
Это просто компонента связности, которая состоит ровно из одной вершинки.
Изолированная вершина — это вершина степени 0, вершина,
из которой вообще не выходит ни одного ребра.
И вот сейчас мы докажем, что с вероятностью, стремящейся к 1,
в случайном графе есть хотя бы одна такая вершина.
Мы сейчас докажем, что вероятность вот такого вот события, события,
состоящего в том, что в случайном графе есть хотя бы одна изолированная вершина,
уже вот эта вероятность стремится к 1 при n, стремящемся к бесконечности.
Ну понятное дело, что отсюда будет следовать отсутствие связности.
Да? Не, ну будет, конечно.
Ну как оно может не следовать, друзья?
Ну конечно будет.
Если в графе есть хотя бы одна изолированная вершина,
то с какой радости он будет связным?
Но вот замечательно то, что, как видите, если мы это сейчас докажем,
переход от пункта 1 к пункту 2 или, если хотите, наоборот, переход от пункта
2 к пункту 1 — это переход от наличия в случайном графе хотя бы одной,
вообще отдельно взятой изолированной вершинки к отсутствию таковых.
И более того, к отсутствию вообще любых компонент связности,
отличных от всего графа.
То есть, еще раз.
Если мы это сейчас докажем, а потом еще докажем пункт 1, то это будет означать,
что переход от связности к несвязности — это не развал на какие-то там,
бог его знает, какого размера компоненты, а это развал на такие компоненты,
среди которых безусловно есть хотя бы одна изолированная вершина.
Вот это вот в каком-то смысле тоже неожиданный факт для человека,
который только начинает изучать эту науку.
В конце концов,
с какой радости должна была появиться именно изолированная вершина?
Может, граф развалился на две равные по размеру связные компоненты?
Но нет вот.
Поди ж ты!
Изолированная вершина возникает, а дальше уже это неважно.
Вот, ну вот это мы сейчас и докажем.
И я утверждаю, что для доказательства вот этой асимптотики,
то есть сходимости вероятности к 1, нам достаточно применить неравенство Чебышёва.
Сейчас я буду делать некоторые загадочные преобразования,
которые в конечном счете приведут нас ровно к левой части неравенства.
Давайте, прежде чем я перейду, собственно, к загадочным преобразованиям,
я вот это вот неравенство стану писать чуть более коротко.
Я не буду указывать G в качестве аргумента ξ, подразумевая,
конечно, что G является таковым, а буду писать просто ξ ≥ 1.
И это ровно то же самое, как написать: «множество тех графов, на которых ξ ≥ 1».
В общем, давайте напишем вот так.
Вероятность того, что ξ ≥ 1.
И вот про нее мы хотим сказать, что она стремится к 1.
Так. Ну, понятное дело, что отрицанием вот
этого события, отрицанием того, что ξ ≥ 1, то есть, что в графе есть хотя
бы одна изолированная вершина, служит событие, состоящее в том...
Ну это просто фанфары, да?
В том, что в графе нет изолированных вершин.
Ну давайте, я это напишу вот так.
1 − вероятность того, что в графе нет изолированных вершин.
Здесь я могу написать = 0, а я не хочу писать =.
Я напишу ≤.
Придирчивый слушатель, он, конечно, скажет: «Ну что за издевательство?
ξ — это число изолированных вершин.
Понятно, что оно не может быть отрицательным».
А вот я упрусь рогом и скажу: «Формально-то правильно».
Ну, плевать я на то хотел, что ξ не бывает отрицательным, мало ли что?
А вот мне хочется так написать.
Сейчас увидите, зачем.
Но следующее преобразование, оно носит ну ничуть не менее загадочный характер,
нежели только что произведенное.
Хотя подождите, а почему загадка?
Смотрите, нам же нужно доказать стремление к 1, да?
Ну вот она 1!
Хе-хе!
Ну, конечно, надо доказать теперь, что эта вероятность стремится к 0.
Ну что же делать?
Сейчас будем доказывать.
Так, 1 − вероятность того, ну тут опять должен быть какой-то...
какая-то барабанная дробь.
−ξ ≥ 0.
Вот это уже полное издевательство, конечно, над слушателем, я понимаю.
Потому что я взял и просто на −1 домножил левую и правую часть неравенства,
вот у меня получилась такая фигня, извините за выражение.
А теперь я сделаю еще одно замечательное преобразование.
Я опять слева и справа, но не домножу, а прибавлю.
Прибавлю константу, равную математическому ожиданию ξ.
Значит, у меня получится, получится у меня вот такая вот вещь.
1 − вероятность того, что Mξ − ξ ≥ Mξ.
Ну просто добавил константу слева и справа,
одну и ту же, одно и то же число — матожидание ξ.
Но смотрите, ведь я же уже почти подошел к неравенству Чебышёва.
Если я вот эту вот штуку, вот эту константу обозначу буквой a,
то у меня почти получается то, что написано слева в неравенстве Чебышёва,
в левой части этого неравенства.
Единственное, что там стоит вот так вот модуль, да?
В неравенстве Чебышёва еще нарисован модуль вокруг разности ξ и Mξ.
Ну я надеюсь, слушатели все-таки понимают, что вычесть из Mξ ξ и взять
модуль и вычесть из ξ Mξ и взять модуль — это все-таки одно и то же.
То есть, на это я как-то рассчитываю.
Ну и прекрасно.
Конечно, понимаете.
Конечно, понимаете.
Вот, другое дело, что видите: чтобы применить неравенство Чебышёва, вроде,
надо нарисовать модуль.
Ну смотрите, что бывает чаще, как вам кажется?
Вот что бывает чаще?
Сама вот эта разность оказывается достаточно большой,
≥ числа a или модуль этой разности оказывается достаточно большим?
≥ такого же числа a.
Ну очевидно, что сама величина может принимать как отрицательные,
так и положительные значения, поэтому, когда вы берете модуль,
у него есть больше шансов оказаться большим.
Модуль чаще, вообще-то говоря, превосходит наперед заданную величину a.
Ну то есть, это означает, что вероятность, которая здесь написана,
она не превосходит вероятности того, что модуль ≥.
Но поскольку вероятность взята с минусом, то мы напишем вот такое неравенство: ≥.
И нарисуем ровно то, что у нас присутствует в неравенстве Чебышёва.
То есть, здесь будет модуль (ξ − Mξ).
Повторяю, я просто поменял порядок, но под модулем это не имеет никакого значения.
≥ вот этой вот константы a,
которая в данном случае и есть математическое ожидание величины ξ.
Все. Применяем вот к этой вероятности
неравенство Чебышёва, это абсолютно стандартный трюк, запоминайте,
мы этим еще будем пользоваться в рамках курса.
Применяем к этой вероятности неравенство Чебышёва, это опять оценка сверху.
Но поскольку со знаком −, то получаем оценку снизу.
≥ 1 − Понятное дело, в числителе стоит дисперсия ξ,
а в знаменателе стоит a в квадрате, то есть, квадрат математического ожидания.
Квадрат математического ожидания величины ξ.
Ну, покуда я все эти загадочные выкладки производил, которые, впрочем,
в итоге привели нас к успеху и к применению неравенства Чебышёва, вы,
наверное, забыли, к чему мы стремимся.
А стремимся мы, конечно, к 1.
То есть, мы хотим доказать, что вот эта штука стремится к 1 при n,
стремящемся к бесконечности.
То есть, нам нужно, видимо, доказать, что вот эта вот дробь,
соответственно, стремится к 0, коль скоро n растет.
n растет, а дисперсия, поделенная на квадрат математического ожидания,
стремится к 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.
