Еще одна содержательная задача про линейность математического ожидания
носит в каком-то смысле вполне прикладной характер, а именно мы сейчас поговорим
опять про любимый случайный граф, но поговорим про такую его характеристику,
о которой сходу, – ну вот если не знать линейности матожидания, – вообще,
трудно догадаться, что нужно действовать именно таким образом.
Ну это я замучил слушателей.
Давайте рассмотрим множество из n элементов и вероятность ребра p.
Это у нас будет случайный граф модели Эрдеша-Реньи, но давайте вот что сделаем.
Давайте определим такую любимую замечательную характеристику графа,
которая называется «хроматическое число».
Обозначается греческой буквой χ – хроматическое
число графа.
Пока не случайного, хотя, если угодно, это случайная величина,
которая работает на множестве графов.
Что такое хроматическое число?
Если говорить словами – это минимальное количество цветов,
в которые можно так покрасить вершины графа, – то есть каждой вершине
присваивается какой-то цвет, – чтобы вершины, соединенные ребром,
были обязательно разного цвета, каждое ребро имело концы разного цвета.
И при этом хочется, чтоб таких цветов было наименьшее количество.
Такая вот очень важная, на самом деле,
графовая задача о кластеризации множества вершин, о разбиении их на куски.
Причем в каждом куске должны отсутствовать ребра.
Видите как: вершины одного цвета не могут быть соединены ребром, поэтому
если кусок покрашен в один цвет, то в этом куске нет вообще ни одного ребра.
Вот это вот определение хроматического числа.
А дальше говорится так: давайте предположим что
p – это функция от n,
то есть когда n, в свою очередь, начинает меняться, вот это вот множество
вершин начинает расти, вероятность ребра изменяется вместе с ними.
Она как-то себя там ведет по-разному, как функция от n.
Давайте предположим, что p – это функция от n, причем такая, что если p(n),
вот эту функцию, умножить на n²,
произведение n² на p(n),
то в пределе при n, стремящимся к бесконечности, получится ноль.
Предлагается доказать,
что с вероятностью,
крайне близкой к единице, с вероятностью, которая стремится к единице при n,
стремящимся к бесконечности, случайный граф имеет
идиотское хроматическое число, равное единице.
Давайте: доказать, что хроматическое число случайного графа (ну это
такая случайная величина), хроматическое число случайного графа равняется
единице в этом случае с вероятностью, которая сама стремится к единице, при n,
стремящимся к бесконечности, то есть когда N (большое) кластеризовать вообще нечем.
Граф красится целиком в один цвет.
Ну доказательство: вот тут
надо сообразить прежде всего, – ну это, в общем,
понятно из определения, – что граф красится в один цвет тогда и только тогда,
когда в нем вообще отсутствуют ребра, просто по определению.
Ведь цвет не должен содержать ребра, а если цвет только один,
значит у графа ребер нет.
Давайте введем случайную величину ξ вспомогательную,
которая на графе G, спустившимся на нее, принимает значение,
равное просто количеству ребер, количеству ребер этого графа G.
Тогда, как я уже сказал, вероятность того,
что хроматическое число графа равняется единице – это есть
вероятность того, что ξ от этого графа равняется нулю,
потому что нету ребер в графе, если он красится в один цвет.
Но это, конечно, есть единица минус вероятность того,
что ξ (G) больше, либо равняется одному.
Ну понятно, потому что число ребер,
оно если не равно нулю, то оно уже, как минимум, единичное.
Отрицательным оно уж никак не может быть, как вы понимаете.
И вот тут вступает в дело замечательное неравенство Маркова,
которое мы с вами доказали на лекции.
Мы знаем, что вероятность, с которой случайная величина,
принимающая неотрицательные значения, – например, число ребер,
оно принимает неотрицательные значения, – так вот вероятность,
с которой такая случайная величина не меньше какой-то константы,
не превосходит математического ожидания этой величины поделить на эту константу.
Ну в данном случае поделить на единицу, то есть можно ничего не делать.
Не превосходит, но со знаком минус больше, либо равняется...
больше, либо равняется единица минус математическое ожидание ξ.
И вот смотрите, в чем пафос, так сказать.
Матожидание χ я ни в коем случае бы не нашел,
это безумно трудная задача – найти среднее значение хроматического числа графа.
Этим занималась, там, куча народу, и это совершенно нетривиальная наука.
А вот математическое ожидание ξ (числа ребер в случайном графе)
я вам сейчас вмиг найду с помощью линейности.
А именно, мы получаем: единица минус математическое ожидание (ξ1 +...
+ ξ с индексом C из n по 2), где, ну я думаю, что многие догадались,
ξi-тое от G – это есть индикатор того, что i-тое ребро присутствует в графе.
То есть это есть единица – если ребро
с номером i есть,
проведено в графе G, и ноль – иначе.
Ноль в противном случае.
Конечно, сложив такие индикаторы,
мы в аккурат и получим количество ребер в графе.
Просто посмотрим на каждое ребро: есть оно или нет его?
Уж проще некуда.
То есть у нас получается: 1 минус сумма по i
от 1 до C из n по 2 вероятностей того, что i-тое ребро,
i-тое ребро находится в графе G вот таких от вероятностей.
Ну и с какой вероятностью i-тое ребро находится в случайном графе?
Просто по определению это p.
Тут, вообще, думать нечего.
Мы получаем: 1 − C из n по 2 × p,
то есть 1 − n × (n − 1)/2 × p.
Но ведь n², умноженное на p, у нас сейчас стремится к нулю по условию.
По условию n², умноженное на p, стремится к нулю.
Значит, и n × (n − 1)/2 × p,
вот это выражение, тоже благополучно стремится к нулю.
А стало быть, разность один минус это выражение стремится к единице при n,
стремящимся к бесконечности.
Что и требовалось доказать.
Видите, мы не боролись с самой этой случайной величиной, а заменили
ее на такую, матожидание которой можно было бы посчитать с помощью линейности,
после чего еще хитренько применили наше замечательное неравенство Маркова.
Давайте в качестве небольшого комментария развлекательного, но уже без доказательств
каких-либо я вам предложу подумать над следующими вопросами:
а что если p – это по-прежнему функция от n,
но на сей раз n × p(n) стремится к нулю, а не n² × p(n).
Видите, это более как бы слабое ограничение на функцию вероятности ребра.
Если раньше мы предполагали, что n² × p стремится к нулю,
то теперь только лишь, что n × p стремится к нулю.
Это означает, что p чуть медленнее убива...
(убивает – это хорошо) убывает, нежели в предыдущем случае, убывает чуть медленнее.
Вот. И если p убывает несколько медленнее,
чем в предыдущем случае, тогда предлагается доказать,
что вероятность, с которой χ от G не превосходит двойки,
стремится к единице при n, стремящемся к бесконечности.
Вот тут надо просто сообразить, опять-таки,
что означает, что граф красится в два цвета?
Это классическое свойство двудольности графа.
Если кто-то изучал курс графов, – например наш, – то он знает,
что граф двудолен тогда и только тогда, когда нечто.
И вот этим можно воспользоваться, дальше применить линейность матожиданий,
и все получится.
Еще более интересно устроена жизнь,
когда p = p(n),
и давайте так скажем: p(n) =
C/n, где C < 1.
Понятно, что это как бы следующая ступенька после предыдущей ситуации,
потому что здесь p(n) должно вести себя как-нибудь так: это единица поделить на n,
ну и еще на что-нибудь, на что-нибудь растущее.
То есть недостаточно взять C поделить на n в качестве p для того,
чтобы вот это произведение стремилось к нулю.
Надо взять все-таки какую-то быстрее стремящуюся к нулю функцию,
дабы вот это произведение ушло в ноль.
А вот то, что здесь рассматривается, это как бы следующая еще ступенька,
p еще медленнее стремится к нулю, нежели вот в этом случае и вот в этом.
Утверждается, что тогда хроматическое число
случайного графа не превосходит тройки с вероятностью,
которая стремится к единице при n, стремящимся к бесконечности.
Ну если вот это вот более или менее простое упражнение,
то здесь уже требуется определенная изощренность.
Такая вот интересная тут возникает наука.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
