0:00
Так, друзья, прежде чем я сформулирую очередную задачу,
давайте я немножко напомню, вот у нас на лекции была основная теорема, собственно.
Теорема, которая утверждала, что количество копий конкретного
графа H в одном случае почти наверняка равняется 0,
ну а в противоположном случае, почти наверняка не меньше 1.
Если я правильно помню, на лекции я обозначал количество копий графа
H в случайном графе G величиной X с индексом H(G).
H у меня имел k вершин и
l ребер.
ρ(H) — это, естественно, плотность, равная l / k.
Ну и пороговая вероятность, собственно, вот для того утверждения,
которое я только что озвучил, пороговая вероятность p(n) — это
есть n в степени −1 / ρ(H).
Но...
то есть, еще раз, если...
это такая пороговая вероятность, давайте я здесь поставлю звездочку,
чтобы было понятно, что это именно критическое значение вероятности.
То есть, если вероятность ребра это o (маленькое) от вот этой величины при n
стремящемся к бесконечности, то асимптотически почти наверное XH-тое = 0.
А если, наоборот, ω (маленькая), то есть вот эта функция помножить на еще
что-нибудь, растущее к бесконечности, то асимптотически почти наверно XH-тое это,
как минимум, единица, то есть хотя бы одна копия присутствует.
Ну и я вам говорил, что в случае, когда, собственно,
вероятность вот какая-то такая, а именно,
когда вероятность ведет себя асимптотически как некоторая константа C,
неважно какая положительная константа, помножить на n в степени −1 / ρ(H),
то в этом случае вероятность вхождения графа H в случайный граф G,
G(np) Эрдёша-Реньи, вот эта вероятность, она не стремится ни к нулю, ни к единице.
Я об этом говорил.
То есть, вот в одном случае к нулю, в другом случае — к единице,
а вот в этом пограничном случае, когда мы находимся, так сказать, внутри порога,
еще не перескочили через него, предельная вероятность отсутствия,
скажем, или присутствия графа H в случайном, она не равна ни нулю,
ни единице, а равна какой-то там константе, зависящей от величины C.
И вот на самом деле, несложно написать какой.
Я не буду сейчас это доказывать.
Это, конечно, трудная теорема, это не задачка для разбора на видеосеминаре.
Но мне это утверждение сейчас понадобится, для того чтобы сформулировать, собственно,
хорошую задачу.
А именно, давайте будем утверждать вот что: положим λ равным...
сейчас я вам скажу чему...
C в степени k / a(H),
где C — это вот это C, k — это количество вершин графа H.
А величина a(H) это та самая, которую мы ввели в предыдущей задаче.
То есть, это количество автоморфизмов графа H.
Так вот, теорема утверждает,
что если вероятность ребра случайного графа устроена так, как здесь написано,
то для любого m вероятность того,
что X с индексом H равняется m ведет
себя при n стремящемся к бесконечности асимптотически как λ в
степени m e в степени −λ поделить на m!.
То есть, как говорят, случайная величина X с индексом H имеет
асимптотически пуассоновское распределение.
Ну это действительно распределение Пуассона, да?
Товарищи, кто знает теорию вероятности?
Да, это конечно распределение Пуассона с параметром λ, и вот этот параметр λ так
вот хитро, забавно выражается через константу C и через число автоморфизмов.
Ну, в принципе, это не очень сложно сообразить откуда взялось, дело в том,
что если вы посчитаете просто среднее значение X с индексом
H вот в таких предположениях, то оно как раз таким-то и получится.
Если аккуратно посчитать...
вот помните, я на лекции писал какие-то чиселки — a(kl), что-то такое,
b(kl) — вот на самом деле, их надо заменять на число автоморфизмов,
и это будет правильный ответ в задаче про математическое ожидание.
Ну да Бог с ним.
Значит, вот в эту теорему давайте просто поверим.
Есть такое замечательное утверждение, что, ну, например, вероятность того, что XH =
0, это приближенно e в степени минус — вот такая вот штука — C в k-той / a(H).
Вот представьте себе.
Да, то есть, вот если m равняется нулю, то λ в m от m!
пропадает, остается e в степени −λ.
Ну, вот давайте предложим, например, такую задачу.
Рассмотрим случайный граф G(n, n в степени −4/5),
и попробуем посчитать асимптотическую вероятность,
ну, предел то есть, при n стремящемся к бесконечности, вероятности того,
что вот в этом случайном графе, в этом случайном графе
ровно один граф на четырех вершинах с не менее пятью ребрами.
Ровно один граф
на четырех вершинах с не менее пятью ребрами.
Вот, конечно, не зная утверждения этой теоремы,
посчитать такую штуку не представляется возможным,
а коль скоро мы поверили в справедливость этого замечательного результата,
то уже вот эту вероятность посчитать нам не слабо.
А именно давайте действовать так: ну, во-первых, поймем,
а какие вообще графы на четырех вершинах имеют не менее, чем пять ребер.
Вообще сколько есть всего таких графов?
На самом деле, все исключительно просто.
Один граф вот такой: на четырех вершинах и в точности с пятью ребрами, правильно?
Такой вот ромбик.
С диагональкой.
Это один вариант, а другой, собственно, полный граф,
полный граф на четырех вершинах.
Да, товарищи, я надеюсь вы понимаете,
что вот в этой теореме H по-прежнему предполагается сбалансированным, конечно.
Потому что мы и теорему на лекции доказывали только для сбалансированного
случая.
То есть, и здесь в этом утверждении речь идет о том, что граф H,
конечно, является сбалансированным,
иначе это все не так просто устроено и надо рассуждать немножко по-другому.
Но замечательно то, что как нетрудно увидеть, это просто очевидно, мне кажется,
и вот этот граф и, конечно же,
полный граф на четырех вершинах — это сбалансированные графы.
То есть, если обозначить, скажем, первый граф буковкой H1,
а второй граф буковкой H2, то присутствие каждого из них,
ну, то есть, поведение случайной величины X с индексом H1,
и поведение случайной величины X с индексом H2 присутствия в случайном графе,
это поведение вполне себе может быть охарактеризовано вот этой вот теоремой.
Как вот этой теоремой, так, естественно, и теоремой с лекции.
Так, естественно, и теоремой с лекции.
Ну, давайте посмотрим, давайте посмотрим сначала на граф H с индексом 2.
Для его изучения вполне достаточно результата,
который мы строго доказали, который у нас на лекции просто был.
Плотность этого графа — ρ(H2) — это, естественно,
шесть ребер поделить на четыре вершины и это есть 3/2.
Плотность этого графа: 3/2.
Ну значит, 1 / ρ(H2) = 2/3.
Правильно?
А вероятность ребра случайного графа, с которым мы сейчас имеем дело, это 4/5.
То есть, вероятность ребра стремится к нулю гораздо быстрее,
конечно, гора-а-аздо быстрее, чем n в степени −2/3.
То есть, пороговая вероятность (p*) = n в степени −2/3,
а наша текущая вероятность n в степени −4/5, ну понимаете,
n в степени −2/3 = n в степени −0,6 в периоде.
А n в степени −4/5 = n в степени −0,8.
То есть, наша вероятность — это o(p*).
n в степени −4/5 = o(p*).
Поэтому по теореме, которая была доказана на лекции для сбалансированных графах,
копий полного графа на четырех вершинах в текущем случайном графе почти,
наверное, нету.
Асимптотически почти наверное такие графы просто отсутствуют,
поэтому вот в эту вероятность они дадут вклад o(1).
Вероятность того, что в случайном графе присутствует такая штуковина,
стремится к нулю при n стремящемся к бесконечности.
Ну и еще есть слагаемое, которое отвечает количеству копий графа H1.
Ну, а граф H1 замечательно подобран,
потому что ρ(H1) это в точности 5/4,
у него пять ребер и четыре вершины.
В точности 5/4, то есть, у нас получается,
что 1 / ρ(H1) это в аккурат 4/5.
Иными словами, наша вероятность текущая — n в степени −
4/5 = n в степени −1 / ρ(H!).
То есть, мы находимся прямо на пороге и C у нас равняется, очевидно, единице.
Правильно?
Ну, конечно!
Так...
дальше...
сейчас, очевидно равняется единице, да...
и чего, собственно говоря?
Давайте λ напишем.
λ у нас получится 1 в 4 степени / a(H1).
Ну и это, конечно, равняется 1/4.
Ну, легко сообразить, что автоморфизмов у такого графа — 4 штуки, это,
я надеюсь, каждый из вас может легко посчитать.
Таким образом...
я, собственно, поэтому в шпаргалку поглядел, я забыл!
Ну, это понятно, да, понятно.
Я сейчас вот поглядел — конечно, их 4.
То есть λ = 1/4, ну и согласно вот этой вот замечательной теореме,
которая у нас прошла без доказательства, конечно, вот это вот слагаемое,
которое я пока что не дописал, оно имеет асимптотику,
давайте я вот сюда перемещусь, 1 + o(1),
ну, то есть, оно имеет асимптотику, помножить на, собственно,
вот какую величину: нам же надо, чтобы ровно один граф был на четырех вершинах.
То есть, надо m положить равным 1.
Это будет 1/4 в первой степени,
e в степени −1/4 и поделить на 1!.
То есть, итоговый ответ: вероятность
асимптотически равна 1/4 (e в степени −1/4).
И это, собственно, то, к чему мы и стремились.
Вот можно посчитать такую штуку с помощью наших теорем.