Ну хорошо, давайте напишем матожидание Xh квадрат. Это есть, конечно, матожидание Хh, 1 +,..., + Xh, m. Давайте для тех, кто забыл, m это — C из n по k на A от k, l. Вот такая вот величина. Так. Но эту штуку надо возвести в квадрат. То есть воспользоваться линейностью, конечно, мы здесь никакой не сумеем, а нам надо честно ее возводить в квадрат. Вспоминайте, как мы подобную вещь делали, когда доказывали вторую часть теоремы о связности случайного графа. Здесь будет чуть-чуть труднее выкладка, нежели была там, но тем не менее, я думаю, мы справимся в ближайшее время. Так. Замечательно. Ну, надо возвести честно в квадрат, у нас, конечно, получится Xh первое в квадрате +, ..., + Xh, m-тая в квадрате. Ну, и дальше будет сумма по всем i уже не совпадающим с j. Xh, i-тая... Xh-тая, i-тая помножить на Xh-тая, j-тая. Ну и как вот я делал на второй лекции, когда рассказывал про связность случайного графа, я подчеркиваю, что вот здесь имеется в виду суммирование по всем упорядоченным парам индексов i и j. Не только они не совпадают между собой, но, если здесь в этом суммировании присутствуют, скажем, 1 и 2, то в нем отдельно присутствуют 2, 1. Именно поэтому я не рисую никакой 2 в качестве сомножителя около этого суммирования, это очень важно. 2 здесь уже не нужна, суммирование по упорядоченным парам. Вот. Теперь вспоминаем стандартную радость. Xh, i-тая в квадрате — это в точности то же самое, что просто Xh, i-тая, то есть я вот эти квадраты могу благополучно зачеркнуть. Напоминаю, что каждая из этих величин принимает только два значения, 1 или 0. Поэтому когда мы возводим эту величину в квадрат, она по-прежнему принимает значение 1 или 0, причем ровно там же, где исходная величина принимала эти же значения. То есть, конечно, в квадрат возведение смысла не имеет. Дальше. Замечаем, что вот этот кусок, вот этот кусок, по линейности опять же, — это просто хорошо известное нам математическое ожидание величины Xh-тая. Ну а в качестве добавки возникает вот эта самая неприятная величина, с которой нам сейчас предстоит немножко побороться. Это будет сумма по всем упорядоченным парам несовпадающих индексов математических ожиданий произведений Xh-тая, i-тая на Xh-тая, j-тая. Замечательно. Теперь смотрим. Это вот мы расписали таким образом числитель в той дроби, про которую мы хотим убедиться, что она стремится к 1. Мы видим, что в этом числителе есть слагаемое, равное математическому ожиданию, а в знаменателе, слава тебе, господи, находится мат. ожидание в квадрате. Поэтому, когда мы вот это слагаемое в числителе разделим на такой знаменатель, то мы в пределе, конечно, получим 0, потому что мат. ожидание стремится к бесконечности. А у нас это мат. ожидание останется ровно в первой степени в знаменателе нашей дроби. То есть вот это слагаемое на итоговую асимптотику никак не повлияет. Если мы желаем доказать, что это стремится к 1, то нам вполне достаточно взять только вот это двойное суммирование и его разделить на квадрат математического ожидания. Таким образом осталось доказать... осталось доказать, что сумма по всем i не равном j матожиданий Xh -тая, i-тая помножить на Xh-тая, j-тая, вот эта сумма асимптотически при n, стремящемся к бесконечности, ведет себя в точности так же, как квадрат математического ожидания. Тогда действительно результат деления этой суммы на квадрат мат. ожидания в пределе даст 1, и мы завершим доказательство второго случая теоремы. Замечательно. Как же нам это доказать? Значит, вы, конечно, должны понимать, что вот эти вот случайные величинки индикаторные, которые мы здесь перемножаем, ни в коем случае независимыми не являются. Потому что если бы они были независимыми, то было бы все замечательно, и мы вообще могли бы воспользоваться в каком-то смысле линейностью, ну просто дисперсия, сумма независимых величин, — это сумма дисперсий, и вся недолга. Но, к несчастью, конечно, эти случайные величины зависимы, поэтому мат. ожидание надо, в общем, считать честно. Ну, давайте подумаем, что значит более или менее честно посчитать такое математическое ожидание? Что такое произведение индикаторов Xh-тая, i-тая на Xh-тая, j-тая? Это 1, если обе копии H попадают в случайный граф G, и 0 — иначе. То есть, если хотя бы одна не попадает, то все, у нас произведение оказывается равным 0. Ну а математическое ожидание вот этого произведения, это, как водится, вероятность того, что обе копии, конкретные копии графа H, попадают в случайный граф G. Ну, давайте нарисуем соответствующую картину, мне кажется, так будет понятней. Вот множество вершин случайного графа, оно состоит, естественно, из n элементов. И вот есть какие-то две копии. Вот одна копия графа H. Она имеет номер i в нашей нумерации. А где-то расположена еще вторая копия графа H, она имеет номер j. Она имеет номер j. Но как они, могут как-то пересекаться, вообще говоря, правда же? Они ж могут как-то пересекаться. Ну, а могут и не пересекаться. Это я не знаю. Значит они могут быть вот так расположены. Вообще не иметь общих вершин ни в каком смысле. Так. А могут быть как-нибудь вот так расположены. Они могут как-то пересекаться. И мы все равно можем смотреть, а в нашем случайном графе это и это одновременно присутствует или нет? Мы же не говорим о компонентах связности. Мы говорим просто о подграфах. И, конечно, в случайном графе случайно может оказаться так, что и вот этот подграф является подграфом, и вот этот кусочек тоже является подграфом случайного графа. Поэтому такие случаи, когда наши копии как-то пересекаются, мы тоже обязаны рассматривать. И более того, возможна вот такая картинка, когда одна копия сидит на некотором множестве вершин. И другая копия сидит на том же самом множестве вершин. То есть они не только могут пересекаться, эти два множества, на которых сидят наши копии, вот эти конкретные i-тая и j-тая, эти два множества вполне могут совпадать. Вот нам нужно как-то разобраться с каждой из этих ситуаций. Ну, давайте приступим к этому делу.
