Очередной замечательный пример того, как можно с помощью линейности посчитать
матожидание и дисперсию, дает нам, конечно, случайный граф.
Вот давайте поставим, как обычно, задачу следующим образом: у нас есть n вершин,
есть вероятность ребра p.
Ну то есть обычный случайный граф Эрдеша – Реньи,
с которым мы уже неоднократно имели дело.
И давайте в качестве случайной величины ξ рассмотрим величину,
которая для данного конкретного графа принимает значение, равное количеству...
равное количеству изолированных вершин...
изолированных вершин в графе G.
Ну тут надо пояснить, конечно, для тех, кто немножко, может быть, подзабыл,
что такое граф, какие там понятия бывают.
Изолированной вершиной называется такая вершина,
которая имеет просто степень ноль.
То есть вершина, которая не соединена ни с каким ребром.
Вот она изолирована.
Она совершенно отдельно.
Ну на картинке это можно как-то вот так изобразить.
Есть вершина, а дальше есть еще что-то, какой-то там граф,
и вот эта вершина никак ни с чем оставшимся не соединена.
Вот нас интересует в случайном графе, который на нас с неба упал согласно вот
этому вероятностному распределению, в нем сколько изолированных вершин?
Ну, естественно, задача состоит в том,
чтобы найти математическое ожидание ξ и дисперсию ξ.
Давайте попробуем понять, что же происходит.
Ну для того чтобы найти математическое ожидание ξ, кажется,
нет ничего лучшего, как снова воспользоваться замечательным принципом
линейности этого самого матожидания.
То есть надо просто заставить, как я уже много раз говорил,
компьютер каким-то образом посчитать: спустился на него граф –
сколько в этом графе изолированных вершин?
Действуем стандартно.
Берем случайные величины (ξ1 +...
+ ξn), где ξi-тое от G, естественно, это есть индикатор того,
что i-тая по счету вершина является независимой в графе G.
То есть это единичка – если вершина i
изолирована в G, и ноль – иначе.
Ну действительно, если мы сложим такие единички и нолики, то
в итоге мы получим ровно столько, сколько есть изолированных вершин в нашем графе.
Посмотрели на первую.
Изолирована?
Отлично.
Добавили к счетчику.
Не изолирована?
Не добавили.
Ну так же на вторую, так же на n-ную.
Стандартный принцип линейности.
Математическое ожидание линейно всегда без относительно каких-либо
свойств случайных величин, поэтому получаем Mξ1 +...
+ Mξn, и все что нам остается – это найти матожидание каждого из таких индикаторов.
Ну, понятное дело, матожидание ξi-того – это есть просто вероятность того,
что вершина i изолирована в случайном графе.
Давайте в случайном графе напишем, она изолирована.
Ну и тут надо, наверное, нарисовать вот эту картинку.
Она, собственно, уже нарисована.
Вот вершина i, и нам хочется понять,
с какой вероятностью именно эта вершина изолирована в случайном графе.
Ну это значит, что ни одного ребра,
которое могло бы выходить из этой вершины в оставшиеся вершины графа, просто нету.
Ни одного ребра.
Но сколько всего могло бы выходить ребер?
Понятное дело, (n − 1) штука, потому что всего вершин n, i зафиксировано, а вот
здесь вот в этом остатке (n − 1) вершина, и в каждую из них могло бы идти ребро.
Но оно не идет.
Эта вероятность есть, стало быть,
(1 − p) в (n − 1) степени, потому что вероятность отсутствия ребра –
это (1 − p), и должно отсутствовать (n − 1) ребро.
Итого получаем в этом месте...
Давайте я звездочку нарисую, чтоб было понятнее.
Звездочка равна n умножить на величину каждого из слагаемых,
то есть на (1 − p) в (n − 1) степени.
Все. Математическое ожидание таким образом
найдено.
А вот над дисперсией надо еще поработать.
Почему?
А неприятность состоит в том, что мы не можем утверждать,
что вот эти случайные величины попарно независимы.
Это просто неправда, что ξi не зависит от ξj-того, подумайте над этим.
Конечно, если бы это было так, тогда мы просто взяли и применили бы
дисперсию суммы, разложив ее как сумму дисперсий.
Но это, к сожалению, не так.
Значит, надо считать аккуратнее, что мы и проделаем.
Дисперсия ξ – это матожидание ξ² минус квадрат матожидания.
Вот эту величину мы с вами уже отыскали,
поэтому нам предстоит найти только лишь второй момент, что мы сейчас и сделаем.
Значит, Mξ² это есть M.
Ну ξ в любом случае представляет собою ту сумму, которой мы уже воспользовались.
Давайте эту сумму честно нарисуем (ξ1 +...
+ ξn) и ее же честно возведем в квадрат.
У нас получится: математическое ожидание...
Возводить в квадрат сумму n слагаемых мы, разумеется, я думаю, умеем.
Получится вот так: (ξ1² +...
+ ξn²), а дальше будет сумма по всем упорядоченным
парам различных индексов ξi-тое помножить на ξj-тое, и скобка закрывается.
Видите, я здесь не рисую двойку,
потому что я рассматриваю именно упорядоченные пары, то есть я считаю,
что в этой сумме одновременно присутствуют и (ξi-тое, ξj-тое) и (ξj-тое, ξi-тое).
Я их не группирую вместе.
Я считаю, что это как бы отдельные слагаемые.
Вот. Ну а если так считать, тогда двойка,
конечно, не нужна.
И у нас получается вот такая вот сумма.
Давайте заметим, что поскольку ξ1 ξn – это индикаторы,
ну то есть случайные величины, которые принимают значение 0 и k1,
то при возведении в квадрат они принимают те же самые значения,
притом с теми же самыми вероятностями: 1² = 1; 0² = 0.
Поэтому если я вот здесь вот эти двоечки сотру, то у меня
ничего абсолютно не изменится – какие были функции ξ1 ξn, такие и остались.
0, 1 в квадрате – это 0, 1.
Вот, поэтому вот этот кусочек с помощью линейности мы найдем.
Это же просто математическое ожидание, которое мы благополучно уже знаем.
Видите, я и здесь это подчеркивал, и здесь подчеркиваю снова.
Сюда его можно просто подставить.
Нас, стало быть, интересует, опять же, с точки зрения линейности,
только математическое ожидание вот этой суммы.
Ну давайте его напишем.
Это будет по линейности сумма по i не равным j
математических ожиданий вот таких произведений.
И повторяю еще раз: если бы эти случайные величины были независимы,
тогда мы просто написали бы произведение матожиданий, и дальше все бы сократилось.
Но они немножко зависимы.
Ну давайте посмотрим честно, что такое матожидание ξi-того на ξj-тое.
Давайте, сумма по i неравным j, а вот это значение, это знаете что?
Ведь надо сообразить, что такое ξi-тое умножить на ξj-тое?
Какие значения принимает вот такое произведение?
ξi-тое принимает значения 1 и 0, ξj-тое принимает значение 1 и 0.
Ну значит, произведение тоже принимает значение 1 и 0.
А когда оно принимает значение 1?
Когда ξi-тое = 1 и одновременно ξj-тое = 1.
То есть когда i (вершина i) изолирована и когда вершина j тоже изолирована.
Поэтому мы получаем вероятность того, что одновременно
одновременно i и
j изолированы в случайном графе.
Ну тут снова надо нарисовать картинку, вот у нас какая-то вершина i,
вот у нас какая-то вершина j, а дальше есть такая сарделька,
в которой находятся все остальные (n − 2) вершины нашего случайного графа.
И вот нам нужно найти вероятность того, что одновременно и вот эта вершина ни с
кем вообще не соединена, и вот эта вершина ни с кем вообще не соединена.
То есть, во-первых, отсутствует вот такое ребро, а во-вторых,
отсутствуют все ребра, которые ведут внутрь сардельки.
Вот такие ребра.
Вот они все отсутствуют.
Ну это означает, что мы фактически суммируем по всем i не равным
j (1 − p) в какой степени?
Ну еще раз, отсутствует вот это одно ребро и отсутствуют
эти (n − 2) ребра, и эти (n − 2) ребра.
Итого, 2 × (n − 2), это получается (2n − 4 + 1), то есть (2n − 3).
Сумма по i не равным j, (1 − p) в степени (2n − 3).
Ну, как видите, от i и j теперь эта вероятность никак не зависит,
это математическое ожидание.
Поэтому нам просто нужно посчитать,
сколько всего существуют таких вот неупорядоченных пар.
Ой, извините!
Упорядоченных, конечно, пар.
Их n × (n − 1), поскольку i не равняется j,
это умножается на (1 − p) в (2n − 3) степени.
И в итоге мы получаем ответ.
Давайте я его вот здесь прям напишу.
Смотрите, вот надо эту штуковину взять.
Это будет n × (n − 1) × (1 − p) в (2n − 3) степени.
Дальше надо к ней добавить математическое ожидание,
которое у нас n × (1 − p) в (n − 1) степени,
и вычесть квадрат этого самого математического ожидания,
то есть n² × (1 − p) в (2n − 2) степени.
И вот это вот ответ на вопрос: чему равняется дисперсия числа
изолированных вершин в случайном графе?