Так, ну давайте коротко на самом деле совсем, приведем задачку, которая в каком-то смысле призвана просто закрепить материал из лекции. Вот, давайте через N с индексом k, например, обозначим количество копий k-клики в случайном графе. Ну, то есть, количество просто k-клик, полных подграфов на k-вершинах в случайном графе. Количество k-клик в случайном графе. Такая вот случайная величина. Предлагается понять, как асимптотически устроена дисперсия этой случайной величины. Ну, на самом деле, доказывается-то это в точности так, как это было на лекции, только надо, конечно, оговорить, о какой вероятности идет речь. Давайте вероятность ребра случайного графа мы положим равной n в степени −2 / (k − 1). Вот если так, тогда мы сделаем сейчас в точности то же самое, что на лекции. А именно, смотрите, MNk = C из n по k * p в степени C из k по 2, ну или, что то же самое, C из n по k на n в степени −2 / (k − 1) * C из k по 2, то есть на (k * (k − 1)) / 2. Шлеп, шлеп, шлеп, шлеп, у нас осталось n в −k-той степени. C из n по k асимптотически равно n в степени k / k! мы умножаем на n в степени −k и получаем 1 / k!. Ну, на самом деле, товарищи, которые как следует осознали утверждение теоремы из предпредыдущей задачи. Теоремы о том, что случайная величина ведет себя как асимптотически пуассоновская, когда вероятность находится в точности на пороге, а как видите, вероятность сейчас находится в точности на пороге, n в степени −2 / (k − 1) — это в точности n в степени −1 поделить на плотность полного графа, у него ведь k-вершин и (k * (k − 1) / 2 ребер. Поэтому отношение числа вершин к числу ребер — это в точности −2 / (k − 1). Мы находимся в точности на пороге. Случайная величина имеет асимптотически пуассоновское распределение, это мы с вами не доказали, конечно, но утверждали. Мы видим, что математическое ожидание асимптотически равняется 1 / k!. И в сущности, это более чем согласуется с той замечательной теоремой об асимптотической пуассоновости. Потому что математическое ожидание пуассоновской случайной величины — это в точности параметр λ, но C у нас здесь равняется 1, то есть, C в k-той степени это просто 1, а число, извините, автоморфизмов нашего графа, — это в точности k!. Поэтому мы могли вообще ничего вот этого не вычислять, а сослаться на ту теорему и сказать: «ну да, конечно, асимптотически пуассоновская величина имеет в асимптотике математическое ожидание, равное своему асимптотическому параметру λ, то есть 1 / k!. Ну и товарищи, которые помнят, чему равняется дисперсия величины, которая имеет пуассоновское распределение с параметром λ, легко сообразят, что эта дисперсия есть в точности опять же 1 / k!, и в общем-то, по-большому счету, вся недолга. Если считать, что это закрепление материала на лекции, ну, да, мы конечно можем тупо провернуть всю ту же самую технологию, и аккуратненько убедиться в том, что дисперсия, она действительно сосредоточена на тех ситуациях, когда наши k-клики, вообще, пары k-клик, не пересекаются, ведь дисперсия, как обычно, включает в себя вычисления второго момента, а когда мы вычисляем второй момент, мы суммируем всевозможные произведения индикаторов. И вот асимптотика, которая здесь написана, она реализуется на произведениях таких индикаторов, которые отвечают вообще по вершинам непересекающимся кликом. То есть, вот так вот жизнь устроена: C из n по k — это количество способов выбрать вершины для первой клики, C из n − k по k — это количество способов выбрать вершину для второй клики. Ну, а дальше мы, собственно, пишем то же самое, там, p в степени C из k по 2, только уже дважды, потому что на каждом множестве из k-вершин должна присутствовать своя клика. Вот, и, собственно, когда вычисляем асимптотику этой величины и подставляем ее в определение дисперсии, мы, конечно, в итоге получаем ровно 1 / k!. То есть, с точки зрения повторения материала лекции, надо просто убедиться в том, что асимптотика сосредоточена вот здесь. А с точки зрения повторения той замечательной теоремы, которая у нас была, появилась, скажем так, две задачи назад, все совсем просто. 1 / k! — это параметр нашего пуассоновского распределения, но он играет роль, конечно, и математического ожидания, и дисперсии нашей случайной величины, ну, разумеется, в асимптотике. Так что, вот так!
