Значит, доказательство.
И, как я уже сказал, начинаем с пункта 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.
Если мы это докажем, то мы в героях.