Давайте я введу еще одно замечательное вероятностное пространство,
которое будет очень полезно для красивых комбинаторных иллюстраций тех
методов и тех оценок, которые мы будем в дальнейшем получать.
Это то, что называется случайный граф.
Это будет еще один важный пример пространства,
который, как мне кажется, максимально хорошо проиллюстрирует в дальнейшем
наши выкладки и наши результаты.
Значит, случайный граф понимается очень просто.
На самом деле это частный случай схемы испытаний Бернулли, я вам сразу скажу.
Давайте, зафиксируем множество чисел натуральных от 1 до n.
Обозначим его, скажем, V с индексом n в честь того,
что это множество будет множеством вершин будущего случайного графа.
Множеством вершин будущего случайного графа.
Но множество вершин, как видите, фиксированы не случайно ни в коем случае.
Значит, наверное, случайными будут ребра.
И правда, давайте посмотрим,
а сколько всего можно ребер провести в графе, если у него n вершин?
Ну, понятно, в полном графе на n вершинах...
В полном графе на n вершинах...
В полном графе на n вершинах,
конечно, C из n по 2 ребер.
Всего C из n по 2 ребер.
Ну, естественно, мы предполагаем, что в графе нет петель,
в графе нет ориентации и в графе нет кратных ребер.
Тогда, действительно, в полном графе на n вершинах C из n по 2 ребер.
Давайте их как-нибудь обозначим.
e1, e2,..., e с индексом C из n по 2.
Это вот все ребра полного графа на n вершинах.
Скажем, если n равняется 4.
Давайте, я уж для максимальной ясности изложения нарисую этот самый
полный граф на 4 вершинах.
Вот у него 1, 2, 3, 4, 5, 6 ребер.
Это как раз C из 4 по 2, если посчитать.
Ну и точно так же полный граф на 5 вершинах
имеет соответственно 10 ребер.
Это C из 5 по 2.
Ну и так далее.
Для каждого n выпишем все ребра, какие, в принципе,
можно провести на этом множестве из n вершин.
Давайте далее зафиксируем число p из отрезка 0,1.
Мы n зафиксировали, p тоже зафиксируем вслед за n.
И давайте считать, что p – это вероятность,
с которой мы проводим каждое отдельно взятое ребро.
То есть, мы каждое отдельное ребро вот из этого множества проводим
независимо от остальных с одной и той же вероятностью вот этой самой p.
То есть, мы имеем дело со схемой Бернулли, в которой производится
C из n по 2 испытаний, и в каждом испытании либо успех, либо неудача.
Причем, если успех, то мы проводим ребро с соответствующим номером,
с номером этого испытания, а если неудача – ну,
тогда не проводим соответствующего ребра, не судьба.
Такая вот ситуация.
Вот.
На выходе возникает случайный граф, у которого фиксированное,
повторяю, множество вершин и случайное множество ребер,
какое-то подмножество вот этого множества, зависящее от того,
сколько раз фишка легла, ну, условно говоря, решкой кверху.
То есть, когда действительно, случался успех,
и мы проводили соответствующее ребро.
Конечно, граф является элементарным исходом точно так же,
как в любой схеме испытаний Бернулли
вся последовательность из ноликов и единичек является элементарным исходом.
Граф – это элементарный исход в нашей схеме.
И вероятность того,
что реализуется в результате вот этой схемы именно такой конкретный граф,
она, конечно, вычисляется стандартно по формуле p в степени число успехов.
Ну, а успехов то сколько?
А сколько ребер мы провели, столько и успехов.
То есть, p в степени мощность E (количество успехов) умножить на q (ну,
то есть, на 1-p) в степени общее количество испытаний минус число успехов.
Ну, понятно, я ж говорю, что это частный случай схемы испытаний Бернулли.
Вот такая вот простая тоже конструкция дает нам некий пример
содержательного нового вероятностного пространства, в котором,
повторяю, элементарными исходами являются графы.
А вероятности графов задаются вот такими вот бернуллиевскими выражениями.
Ну, мы же все-таки с вами говорим про какие-то случайные величины.
Вот, на графах очень удобно задавать какие-то
разумные естественные случайные величины,
поэтому я хотел рассматривать это как продолжение вот этого множества примеров.
Все-таки sinω – это какая-то глупость.
А вот когда реализовался случайный граф, тогда можно много чего посчитать.
Вполне практически значимое, и об этом мы обязательно в свое время поговорим.
Значит, смотрите: ξ(G) давайте, например,
положим равным числу треугольников в случайном графе.
Ну, действительно, давайте рассмотрим совсем уж частный случай.
Пусть n = 4, и реализовался случайный граф,
представляющий собой вот такой вот цикл.
Ну, так случилось.
То есть, вот эти ребра не реализовались, а вот эти четыре произошли,
пожалуйста, провелись.
Спрашивается, ну сколько в нем треугольников?
Ну, конечно, ξ от этого графа равняется нулю,
потому что треугольник – это просто полный подграф на трех вершинах.
То есть, три вершины, которые попарно соединены ребрами.
В данном случае такой тройки вершин в графе нет.
Ну, ξ = 0, хорошо.
А если вдруг реализовался, например,
вот такой вот граф, тогда ξ от него чему будет равняться?
Ну, видно, здесь уже есть и этот треугольник, и этот треугольник.
Таким образом, ξ будет равняться 2.
Бывают разные ситуации.
В зависимости от того, какой реализуется элементарный исход,
ξ может принимать то или иное, внимание, конкретное неслучайное значение.
То есть, хоть она и называется случайной величиной,
но случайность ее связана только и только с тем, что объект, который
подставляется в нее в качестве аргумента, изначально кажется нам случайным.
Но когда он уже реализовался, значение ξ на нем – это вполне конкретное число.
Вот это очень важно понимать.