Еще одна содержательная задача про линейность математического ожидания носит в каком-то смысле вполне прикладной характер, а именно мы сейчас поговорим опять про любимый случайный граф, но поговорим про такую его характеристику, о которой сходу, – ну вот если не знать линейности матожидания, – вообще, трудно догадаться, что нужно действовать именно таким образом. Ну это я замучил слушателей. Давайте рассмотрим множество из 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, стремящимся к бесконечности. Ну если вот это вот более или менее простое упражнение, то здесь уже требуется определенная изощренность. Такая вот интересная тут возникает наука.
