Прекрасно!
Ну давайте начнем с простого: найдем математическое ожидание случайной
величины ξ.
На это у меня места пока хватит.
Ну смотрите.
Чему равняется среднее число изолированных вершин в случайном графе?
Ну вообще это стандартное упражнение на то,
что называется линейностью математического ожидания.
То есть, надо ξ представить в виде какой-то суммы и воспользоваться тем,
что математическое ожидание суммы всегда вообще равно сумме математических
ожиданий.
Вот всегда.
Это классический факт, который называется линейностью матожидания.
Давайте ξ представим в виде суммы.
Смотрите.
Это математическое ожидание суммы (ξ1 +...
+ ξn), где, давайте я вот здесь напишу, ξ i-тое — это,
естественно, случайная величина, которая, как обычно, должна зависеть от графа.
Аргументом является граф.
Так вот, ξi (G) — это такой индикатор так называемый.
Это случайная величина, которая принимает только два значения: 1 или 0.
Значит, она принимает значение 1,
если вершина i изолирована в случайном графе G.
Изолирована вот в этом случайном графе G.
На нас спустился граф, и мы смотрим: вот эта конкретная вершина i,
она изолирована в нем или нет?
Если изолирована — все, ставим 1.
0 — в противном случае.
Ну понятно, мы здесь просуммировали по всем возможным вершинам нашего графа.
Вершины, не забывайте, это просто числа от 1 до n,
мы так договорились еще на прошлой лекции.
Ну вот мы просуммировали по всем возможным вершинам такие индикаторы.
Мы посмотрели на каждую вершину и сказали,
является она изолированной в нашем графе или не является.
И вот сколько раз на вопрос об изолированности мы ответили «да»,
столько у нас изолированных вершин и получится.
Ну а это и есть случайная величина ξ.
То есть, ξ,
равная количеству изолированных вершин — это сумма вот таких индикаторов.
Теперь пользуемся линейностью математического ожидания.
Получаем Mξ1 +...
+ Mξn.
И все, что остается сделать — это найти математическое ожидание ξ i-того.
Ну, математическое ожидание случайной величины,
которая принимает только два значения, 1 или 0, оно вычисляется более чем просто.
Надо взять 1, умножить на вероятность того события,
при котором получается 1, и прибавить 0, умножив на вероятность отрицания.
Ну, 0, умноженный на вероятность отрицания — и в Африке 0, поэтому достаточно просто
посчитать вероятность того, что данная вершина является изолированной.
Ну, для этого удобно нарисовать картинку.
Вот у нас есть какая-то конкретная вершина i,
и мы хотим посчитать математическое ожидание ξ i-того, то есть,
вероятность того, что именно эта вершина является изолированной в случайном графе.
Ну, рисуем все остальные вершины в виде такого, если хотите, облачка.
Облачко состоит, конечно же, из n − 1 вершины,
потому что всего в графе n вершин, а i вершина выделенная.
И вот эта вершина i, она будет у нас изолированной тогда и только тогда,
когда ни одного из указанных на картинке ребер нет в случайном графе.
Должны одновременно отсутствовать вот эти вот конкретные n − 1 ребер.
Ну с какой вероятностью у нас каждое конкретное отдельно взятое ребро в
случайном графе отсутствует?
Понятно, что вероятность отсутствия отдельного ребра есть просто (1 − p).
Но тогда вероятность того, что отсутствуют все вот эти (n − 1) ребер — это (1 − p)
в (n − 1) степени, потому что отсутствия ребер — это события взаимно независимые.
Мы перемножаем их вероятности.
Таким образом, мы получаем, что каждое из математических ожиданий,
давайте я вот здесь это напишу, равняется просто (1 − p) в степени (n − 1).
Таким образом, вся сумма равняется n * (1 − p) в степени (n − 1).
И у меня еще немножечко остается места на вот этой вот доске.
Понимаете, да?
Про бычка.
Доска кончается.
Но у меня немножечко места остается.
Я сейчас найду, куда стремится вот эта величина при n,
стремящемся к бесконечности, и, я думаю,
что наступит некий катарсис, потому что, ну, это будет настоящее просветление.
Вы наконец поймете, где важно, что c < 1.
В каком месте играет роль вот это вот условие, с которым мы, вроде как,
имеем дело.
Вот. Ну давайте посмотрим на эту функцию,
как она себя ведет.
Вот здесь вот это напишем.
Значит, у нас получается n.
Давайте я напишу так: (1 − p) я представлю как e в степени (ln (1 − p)).
То есть, у меня получится (n − 1) * ln (1 − p).
Ну, это совершенно понятно.
А дальше я вспомню, что p — это у меня величина, которая стремится к 0 при n,
стремящемся к бесконечности.
И здесь, кстати, совершенно неважно: c < 1, c > 1.
В этом месте просто важно, что p ведет себя, как (c * ln n) / n.
То есть, (c * ln n) / n — безусловно, стремящаяся к 0 функция.
И я могу заметить,
что ln (1 − p) в этом режиме асимптотически ведет себя так же, как −p.
Ну давайте это явно запишем.
Значит, у меня получается n * e в степени (n − 1),
а логарифм от (1 − p) я запишу, как −p.
Ну, это просто следствие, если хотите, из разложения логарифма в ряд Тейлора.
Понятно, что в ряде Тейлора первое слагаемое — это как раз −p.
Ну а все остальное идет в o (1), как водится,
и записывается это вот так: 1 + o (1).
Функция какая-то, которая стремится к 0 с ростом n при n,
стремящемся к бесконечности.
Дальше давайте заметим, что вот эта величина (n − 1),
ну конечно, она тоже асимптотически просто равна величине n.
То есть, можно это еще вот так вот переписать.
Это будет n в степени −...
Ой, извините.
n * e в степени −np.
Я заменяю (n −1) на n.
Естественно, когда я заменяю (n −1) на n,
я должен еще написать * (1 + o (1)), но когда я перемножаю две функции,
стремящиеся к единице, то я получаю тоже какую-то функцию, которая стремится к 1.
То есть, я опять могу написать таким вот образом.
Естественно, слушатели должны понимать,
что вот это o (1) — не то же самое, что вот это.
Ну, я думаю, что вы это прекрасно понимаете, товарищи.
Значит, замечательно.
И вот теперь наконец настает момент катарсиса, потому что я подставляю
сюда вместо p (c ln n) / n У меня получается n *
e в степени − Поделить на n, умножить на n — чпок!
Сократилось.
Не кокнул?
Никого?
Хе-хе.
Ну как мог кокнуть?
Ну в знаменателе n, в числителе n — сократилось.
Значит, тут осталось c * ln n.
Ну, это, собственно, числитель вероятности,
который выжил в результате сокращения.
Вот так.
Ну и умножить там на какую-то вот эту вот штучку ничтожную,
которая стремится к 1, (1 + o (1)).
Замечательно.
Сейчас оно все дальше посыпется, как в тетрисе.
Смотрите.
e в степени −ln n это ведь 1 / n, правильно?
e в степени −ln n — это 1 / n.
Ну еще в степени c и в степени «вот эта ерунда».
Переписываем.
Так.
Одно n вот тут, а в знаменателе
оказывается n в степени c * (1 + o (1)).
n в степени c *( 1 + (o (1))).
Вот так.
Ну и вот вам катарсис,
потому что условие c строго < 1, не ≤,
а именно строго < 1 означает, что, начиная с некоторого n,
c, помноженное вот на эту фигнюшку, тоже строго < 1.
c строго < 1, она умножается на нечто, стремящееся к 1.
Ну, значит, начиная с какого-то момента это произведение оказывается строго < 1.
То есть, n в 1 степени делится на n,
которое возводится в степень, строго меньшую 1.
Ну то есть это n в какой-то строго положительной степени,
ни к какому 0 не стремящееся.
Это означает, что все, что здесь написано, вся вот эта дробь,
стремится к + бесконечности при n, стремящемся к + бесконечности.
То есть, когда число вершин случайного графа растет,
математическое ожидание числа изолированных вершин в этом случайном
графе тоже стремится к бесконечности.
Это еще, внимание, вот тоже очень важный момент.
Это еще вовсе не означает,
что почти наверняка в случайном графе есть изолированная вершина.
Для того, чтобы это доказать, как мы помним,
нам нужно убедиться в том, что вот эта дробь стремится к 0.
Но одним из важнейших условий первоначальных для того,
чтобы вообще эта дробь смогла стремиться к 0, является, в том числе,
стремление к бесконечности матожидания.
Потому что если бы оно к бесконечности не стремилось, то, конечно, можно было бы
воспользоваться, наоборот, неравенством Маркова и убедиться в том, что в случайном
графе нельзя говорить о наличии с высокой вероятностью изолированной вершины.
Вот, оказывается, где нужно, что c < 1.
Ну и сейчас мы докажем все-таки,
что дисперсия поделить на квадрат матожидания стремится к 0.