Найдите дисперсию числа копий полного графа на 4 вершинах в случайном графе G(7,1/2).

задан 12 Май 16:31

10|600 символов нужно символов осталось
1

Для каждого 4-элементного подмножества вершин графа рассмотрим случайную величину, равную 1, если полный граф на этих четырёх вершинах в случайном графе присутствует. Если не присутствует, то она равна 0.

Число копий графа K4 оказывается равно сумме X=X(1)+...+X(35) для описанных выше случайных величин. Нам надо найти DX=cov(X,X). Эта задача сводится к нахождению cov(X(i),X(j)) для каждой пары индексов i,j от 1 до 35. Фиксируем одно из значений i.

Из 35 подмножеств мощности 4 у нас есть одно, которое имеет с данным 4 общих вершины; 12 подмножеств имеют 3 общих вершины; 18 имеют по 2, и 4 по одной. Для каждого из этих случаев находим ковариацию.

Заметим, что MX(i)=2^{-6} для любого i, поэтому MX=35/64. Для любых i,j имеет место равенство MX(i)MX(j)=2^{-12}.

Пусть число общих вершин двух подграфов равно 1<=k<=4. Тогда MX(i)X(j) равно вероятности возникновения полного подграфа на заданных 8-k вершинах. При k=4,3,2,1 это даёт 2^{-6}, 2^{-10}, 2^{-15}, 2^{-21}. Это значит, что сумма величин cov(X(i),X(j)) по всем j от 1 до 35 равна (2^{-6}-2^{-12)+12(2^{-10}-2^{-12})+18(2^{-15}-2^{-12})+4(2^{-21}-2^{-12}). Умножая на 35, имеем DX=355075/524288, что приблизительно равно 0.6772518158.

ссылка

отвечен 12 Май 17:41

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,540
×1,123
×481

задан
12 Май 16:31

показан
73 раза

обновлен
12 Май 17:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru