Так, давайте продолжим разбираться с лекционным материалом.
Давайте рассмотрим, как водится, случайный граф G от (n, p) причем p — это
функция от n, которая ведет себя так, как она вела себя в основной теореме с лекции.
Это c логарифм n поделить на n, где c меньше 1.
И на лекции с помощью неравенства Чебышева мы доказали,
что в этой ситуации асимптотически почти наверное случайный граф содержит хотя
бы одну изолированную вершину и, стало быть, не является связным.
То есть вот пафос был в том, что нарушение связности совпадает с появлением
хотя бы одной изолированной вершины.
А вот давайте зададимся вопросом, а с какой вероятностью есть
ровно 1 изолированная вершина?
То есть мы точно знаем, что с вероятностью,
близкой к 1, изолированные вершины есть, но, может быть, их больше, чем 1.
И вот мы сейчас действительно докажем, что ровно 1 изолированная вершина есть с
маленькой, асимптотически маленькой вероятностью,
причем забавным образом мы снова применим неравенство Чебышева здесь.
Вот если на лекции мы доказали с помощью неравенства Чебышева, что асимптотически
почти наверное изолированные вершины присутствуют, то сейчас мы докажем с
помощью того же самого неравенства, что асимптотически почти наверное ровно 1
изолированная вершина все-таки не появляется, их появляется сразу несколько.
Вот, ну давайте в скобках введем обозначение X от G — это
есть число изолированных вершин
в случайном графе, изолированных вершин.
Так, ну и тогда в терминах этого X нас
интересует просто вероятность того, что X в точности равняется 1.
Конечно, эта вероятность не превосходит вероятности того, что X не больше 1,
ну потому что сюда входит еще, вообще говоря, ситуация, что X равняется 0.
Правда, вероятность того, что X равняется 0, как мы знаем, как раз маленькая,
но вот мне тем не менее удобно написать это в форме такого неравенства.
Дальше, давайте, как это уже показало себя полезным на лекции,
слева и справа вычтем константу,
равную математическому ожиданию нашей случайной величины.
То есть будет вероятность того, что (X − MX) не превосходит (1 − MX),
и это, конечно, не больше, чем вероятность того,
что модуль (X − MX) больше либо равняется (MX − 1).
Ну, то есть мы сначала поменяли знак,
вот здесь слева и справа домножили на (−1), я просто проглотил этот шаг,
домножили на (−1), получили слева (MX − X), справа (MX − 1),
вот, ну и конечно, вероятность того, что величина,
которая может принимать как отрицательные, так и положительные значения, больше
либо равна чего-то, она не превосходит вероятности того, что ее модуль,
модуль (MX − X) или, что то же самое, (X − MX) больше либо равняется того же самого.
То есть это неравенство, конечно, правильное.
А здесь мы уже можем применить неравенство Чебышева.
То есть у нас получается не больше, чем дисперсия X
поделить на MX минус 1 в квадрате.
Давайте перепишем вот так: дисперсия X
поделить на MX в квадрате умножить на MX в
квадрате и поделить на MX минус 1 в квадрате.
Но товарищи, мы на лекции доказали,
что вот в этой ситуации, когда p такое, c меньше 1,
в этой ситуации математическое ожидание стремится к бесконечности.
Мат. ожидание X стремится к бесконечности,
это мы доказали на лекции.
Также на лекции мы показали, что вот эта вот дробь DX поделить на MX в квадрате,
DX поделить на MX в квадрате стремится к нулю.
Ну и все.
Смотрите, вот эта дробь стремится к нулю по доказанному на лекции,
MX стремится к бесконечности, ну значит вот эта дробь стремится к 1.
Ну а, стало быть, произведение дробей стремится к нулю,
и мы действительно доказали, что с вероятностью, которая очень мала,
изолированная вершина ровно одна.
Да, изолированные вершины есть, но с высокой вероятностью их больше одной.
