Так, давайте продолжим разбираться с лекционным материалом. Давайте рассмотрим, как водится, случайный граф 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. Ну а, стало быть, произведение дробей стремится к нулю, и мы действительно доказали, что с вероятностью, которая очень мала, изолированная вершина ровно одна. Да, изолированные вершины есть, но с высокой вероятностью их больше одной.
