Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Оценивание дисперсии
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
62 оценки
From the lesson
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, ну что, давайте считать дисперсию, стало быть?
Раз матожидания научились считать, значит дисперсию посчитаем.
Так, что же такое дисперсия ξ?
Ну понятное дело, что дисперсия ξ — это математическое
ожидание квадрата ξ минус квадрат математического ожидания.
Если кто эту формулу забыл, пожалуйста, вспомните, это совсем просто,
сразу вытекает из определения дисперсии или даже можно считать,
что это определение одно из двух равносильных.
Вот, ну квадрат математического ожидания мы с вами знаем — это просто n2 * 1 −
p в 2n−1.
Поэтому нам достаточно найти то, что называется «второй момент»,
то есть просто найти матожидание квадрата этой случайно величины ξ.
Давайте опять ξ представим в виде суммы индикаторов тех же самых,
с помощью которых мы считали математическое ожидание,
но только теперь эту сумму индикаторов мы еще возведем в квадрат.
Ну давайте честно ее в квадрат и возведем.
У нас получится ξ1 в квадрате +...
+ ξn в квадрате, ну а дальше будет, как водится,
сумма всяких там удвоенных произведений, но давайте я лучше без двойки ее напишу,
я буду иметь в виду, что у меня сумма ведется по
упорядоченным парам различных индексов i и j,
ну и суммируется всевозможные произведения ξi-тых и ξj-тых.
То есть имеется в виду, что, скажем, в этой сумме отдельно участвует
и слагаемое ξ1 * ξ2, и слагаемое ξ2 * ξ1.
Поэтому я не рисую 2 перед этой суммой.
Мне так сейчас будет гораздо удобнее.
Зачем бы 2 рисовать, все равно потом на 2 делить придется.
Это понятно.
Вот, ну, что, во-первых, давайте заметим, что ξi-тое — это у нас индикатор,
то есть случайная величина,
которая по определению своему принимает только два значения: 1 и 0.
Ну то есть в квадрате она ничем не отличается от самой себя.
Я могу вот эти квадраты спокойно стереть,
и случайные величины останутся абсолютно такими же, каким были изначально.
Таким образом, вот эта часть, это та самая часть,
которую мы с помощью линейности только что посчитали.
Эта часть, это n * (1 − p) в (n − 1)
степени — это в аккурат математическое ожидание ξ.
Таким образом, нам нужно посчитать оставшуюся часть,
то есть матожидание вот такой вот упорядоченной суммы.
Ну опять пользуемся линейностью.
Давайте я отдельно напишу, матожидание суммы по всем возможным несовпадающим
парам индексов i и j, произведение ξi * ξj
— это есть сумма по тем же самым i ≠ j,
математических ожиданий ξi * ξj.
Ну теперь давайте сообразим, а что такое ξi-тое * ξj-тое?
ξi-тое — это 1, если i, вершина i, изолирована.
ξj-тое — это единица тогда и только тогда, когда j является изолированной.
то есть произведение двух таких индикаторов — это 1 в том,
и только том случае, когда обе вершины i и j являются изолированными.
То есть написанное здесь математическое ожидание — это вероятность указанного
события.
Это, повторяю, вероятность того,
что одновременно i и j являются изолированными вершинами случайного графа.
Давайте, как водится, нарисуем картину… Вот у нас есть вершина i,
вот есть вершина j и вот есть облачко,
которое состоит на сей раз из n − 2 оставшихся вершин.
Всего их n, здесь 2, ну значит, облачко состоит из n − 2.
И вот мы говорим, что i и j должны быть изолированы в случайном графе.
Это значит, что нет вот такого ребра, этого ребра нет,
и нет ни одного из ребер такого вида...
Этих ребер тоже нет.
Я их нарисовал, но их не должно быть.
Каждое ребро отсутствует, как водится, с вероятностью 1 − p,
ребра отсутствуют взаимно независимо, поэтому получается,
что вот это вот математическое ожидание — это просто 1 − p, которое возводится в
степень равную количеству нарисованных на этом рисунке ребер.
Ну сколько здесь ребер?
n − 2 ребра из i-облачка,
еще n − 2 ребра из j-облачка и одно ребро между i и j.
Итого: 2n − 3.
Дважды (n − 2) — это 2n − 4 и плюс вот это одно, это получается 2n − 3.
Все, сосчитали математическое ожидание произведения любых двух различных
индикаторов.
Получаем сумму по всем i не совпадающим
j величин (1 − р) в степени (2n − 3).
Ну и замечаем, что всего таких пар индексов, естественно, n * (n − 1),
и получаем n * (n − 1) * (1 − р) в степени (2n − 3).
Таким образом, мы, по сути, дисперсию сосчитали.
Давайте сведем воедино все, что у нас получилось.
Смотрите, второй момент, который мы сейчас вычисляли, он складывается,
как первый момент и вот эта вот штуковина, которую мы вычислили напоследок,
кроме того, надо из этого вычесть квадрат математического ожидания,
то есть квадрат вот этой величины.
Это и будет дисперсия.
Ну, а я сразу напишу, дисперсию поделить на квадрат математического ожидания.
Ведь моя цель доказать, что именно эта штука стремится к нулю.
Давайте честно напишем длиннющую такую дробь.
В числителе у нас будет дисперсия, которую мы вычислили,
в знаменателе квадрат матожидания.
Так… Пишем, n * (1 − р)
в (n − 1) степени — это вот это слагаемое, которое входит во второй момент,
дальше пишем вот это слагаемое… n * (n − 1) * (1 − р)
в 2n − 3… Правильно?
Ну конечно, да.
Может я даже размахнулся… Давайте, знаете,
как сделаем… Давайте… Мы же делим на квадрат математического ожидания,
а вычитается у нас в аккурат квадрат математического ожидания.
Ну и зачем его лишний раз рисовать?
Давайте просто напишем отдельно от этой дроби, −1.
−1 за счет того, что квадрат матожидания поделили на квадрат матожидания.
А вот здесь, действительно будет стоять квадрат матожидания, то есть величина n
* (1 − р) в степени (n − 1) и все это в квадрате.
Вот здесь мне это не жалко написать.
Ну смотрите, товарищи, ничего не забыл?
Я сам погляжу… Знаете, мало ли… Может,
что вылетело… Но вроде ничего.
Вот это вот линейная составляющая, вот это вот попарные произведения,
это квадрат матожидания, это мы вычли отношение квадрата к квадрату.
Замечательно.
Теперь смотрите.
Вот если поглядеть вот сюда, то это на самом деле просто
отношение математического ожидания к своему квадрату.
Ну я уж написал это в явном виде, не судите меня,
ну написал и написал… Но в любом случае, мы-то что понимаем?
В знаменателе выживает первая степень вот этой величины,
а так оно… Хлоп… Хлоп… Понятное дело.
Да? То есть выживает только первая степень
этой величины.
Но мы же только что при участии катарсиса доказали,
что эта величина стремится к плюс бесконечности.
Значит дробь, которая сейчас обведена вот в это странное лекало,
эта дробь стремиться к 0, коль скоро n растет.
Давайте напишем это следующим образом.
Это o (1), ну, то есть я просто подчеркиваю,
что при n стремящейся к бесконечности, вот это лекало стремится к 0.
Так, давайте я сразу это −1 напишу?
Чтобы оно у меня перед глазами не прыгало.
Вот… И добавим вот эту дробь.
Но это чуть поинтереснее, давайте ее честно распишем, что у нас получится.
Так, в знаменателе у нас стоит n в квадрате, видите n в квадрате… да?
А в числителе n * (n − 1).
Ну понятно, что если вы n * (n − 1) делите на n в квадрате,
то в асимптотике вы получаете 1.
То есть это можно вот так написать: 1 + о (1).
Это я записал отношение, повторяю,
величины n * (n − 1) к величине n в квадрате.
Ну и мне еще надо (1 − p)-шки всякие сократить.
Что тут у меня стоит (1 − p) в (2n − 3), а тут (1 − p) в (2n − 2),
ну то есть у меня остается (1 − p) в −1 степени.
(2n − 3) / (2n − 2) остается (1 − p) в −1 степени.
Но все замечательно, но p же стремиться к 0… По условию теоремы.
И здесь опять не важно C < 1, C > 1, важно то,
что p стремиться к 0, как логарифм поделить на n.
Это понятно.
Но тогда (1 − p) — это 1 + o (1).
(1 − p) в −1 — это то же функция стремящаяся к 1.
Короче говоря вот это все выражение, это просто 1 + o (1) с
каким-то там еще о малым которое, естественно, отлично от написанного выше.
В итоге мы получаем такую формальную запись… o (1)
− 1 + 1 + o (1).
Шлеп… Шлеп… Равняется o (1), то есть мы действительно доказали,
что вожделенная асимптотика имеет место, дробь дисперсия поделить на квадрат
матожидания стремится к нулю и тем самым пункт 2 теоремы доказан.
По-моему, это очень мило.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
