Так, ну давайте коротко на самом деле совсем, приведем задачку,
которая в каком-то смысле призвана просто закрепить материал из лекции.
Вот, давайте через 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!
— это параметр нашего пуассоновского распределения,
но он играет роль, конечно, и математического ожидания,
и дисперсии нашей случайной величины, ну, разумеется, в асимптотике.
Так что, вот так!
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
