Давайте рассмотрим теперь задачку на независимость случайных величин
– тоже очень полезная для понимания того,
как устроена независимость случайных величин задача.
Удобно опять работать с любимыми случайными графами,
то есть как обычно есть N вершин, есть вероятность ребра,
с которой возникает каждое ребро,
и давайте возьмём такие достаточно простые случайные величины,
сейчас я нарисую картинку, чтобы было понятно, что условие, конечно,
формальное, оно выглядит довольно страшно, а картинка – она вполне всё проясняет.
Вот у нас есть эти N вершин, их всего N штук,
и я их условно рисую как такую здоровенную сардельку.
Здоровенная сарделька – это множество из наших N элементов,
которое является множеством вершин.
В этой сардельке, как обычно, можно выделять разные подсардельки.
Значит, подсардельки давайте брать размера k.
Они там могут как угодно между собой пересекаться.
То есть подсарделька это просто произвольное подмножество мощности k
нашего исходного множества мощности N.
Всего таких подмножеств c из N по k штук.
c из N по k подмножеств множества вершин.
И вот давайте занумеруем их как-нибудь,
в каком-нибудь порядке.
Например, по i от единицы до c из N по k.
Это вот будут номера этих подмножеств.
Номера этих подмножеств.
Теперь давайте через
I большое с индексом i маленькое обозначим, как водится, индикатор.
Только ни о какой линейности математического ожидания сейчас речь не
пойдёт.
Вот давайте возьмём такой индикатор, который на графе j.
На вот этих вот N вершинах, хотите – на случайном графе,
принимает, естественно, два значения: единица или ноль.
Как и всякий индикатор, тут ничего особенного.
Важно только описать, на какое свойство он указывает.
То есть когда он принимает значение один,
ну и соответственно иначе он будет принимать значение ноль.
Главное описать, когда он принимает значение один.
Вот давайте считать, что он принимает значение один,
если у графа j на вот этом i-том
множестве из k вершин,
на i-той подсардельке, чтобы было приятнее.
Значит, на i-той подсардельке, на i-том подмножестве из k вершин
полный подграф.
То есть индикатор смотрит вот на этом, например,
конкретном множестве из k вершин,
на нём в нашем графе образовался полный подграф на k вершинах, или не образовался.
Если образовался, всё, ставим единичку, если не образовался, ставим нолик.
Ну понятно вроде.
Ещё раз смотрим кусок графа,
порождённый конкретным i-тым по счёту k-элементным подмножеством и,
если этот кусок представляет собой полный граф, то есть там все рёбра проведены,
тогда мы говорим, что индикатор принимает значение один, а если он
представляет собой неполный граф, там, какого-нибудь ребра не хвататет,
или вообще никаких рёбер нету, то мы говорим, что он принимает значение ноль.
Вот такой вот простой индикатор.
И в задаче спрашивается так: верно ли,
что любые два таких
индикатора I с индексом i,
I с индексом j независимы.
Вот так спрашивается.
Ну давайте попробуем порассуждать, то есть попробуем понять,
а вдруг это действительно верно.
Или, может быть, неверно?
Ну, смотрите.
Если i-тая и j-тая
подсардельки – я прям напишу это слово, меня распирает… если
i-тая и j-тая подсардельки не пересекаются вовсе,
не пересекаются...
или пересекаются по одной вершине...
или пересекаются по одной вершине...
То очевидно,
что вот такие индикаторы являются независимыми случайными величинами.
Сейчас я поясню почему.
То очевидно...
Ну действительно очевидно, но всё-таки требует некоторого пояснения...
Очевидно, что Ii и Ij, независимы.
Ну действительно, если у нас есть две подсардельки,
которые вовсе не пересекаются, или какие-то две подсардельки,
которые имеют только одну общую вершину, в этом случае у них вообще нет общих рёбер.
Но тогда, смотрите, вероятность того,
что I с индексом i принимает значение единица,
I с индексом j принимает значение единица.
Вернее даже вот эти два события.
Да Бог с ней с единицей, единица тут ни при чём.
Можно и ноль написать, это всё равно.
Давайте здесь напишем какое-нибудь «ню» для красоты, а здесь «мю».
Где «ню» – это какое-то число из ноль, один,
и «мю» – это какое-то число из ноль, один.
Любое, совершенно.
Два значения может быть, здесь может нолик, может быть единичка.
И здесь может быть нолик, а может быть единичка.
Ну ясно, что вот это событие от вот этого события зависеть не может,
потому что просто здесь рассматривается одно множество рёбер,
а вот здесь рассматривается совершенно другое множество рёбер.
Если можно, сюда сейчас вот вернусь, и...
Глядим сюда – вот здесь есть множество рёбер, и здесь есть множество рёбер.
Образует оно полный граф, или не образует оно полный граф?
Очевидно, эти события независимы.
Потому что нету общих рёбер.
Не о чем и говорить.
Конечно, вот это вот вероятность, это есть произведение того, что Ii равняется ню...
Извините, не то...
Умножить на вероятность того, что Ij равняется ню.
Но это в очевидном предположении, когда вот эти вот i-тая и j-тая
подсардельки пересекаются мало, когда у них нету общих рёбер.
Давайте посмотрим на случай...
Так, напишу, а что если i-тая и j-тая
подсардельки имеют
ровно одно общее ребро.
Ровно одно общее ребро.
Ну, то есть как множество из k элементов они пересекаются ровно по двум вершинам,
по двум элементам.
Ровно одно общее ребро.
Ну давайте, для примера посмотрим на вероятность того,
что Ii равно единице,
и одновременно Ij равно единице.
То есть это вероятность того, что и на вот этой подсардельке обрадовался полный граф
на k вершинах, и на вот этой подсардельке образовался полный граф на k вершинах.
Давайте посчитаем эту вероятность.
Давайте посчитаем эту вероятность.
Так.
Ну, смотрите.
С какой вероятностью в графе присутствуют все те рёбра,
которые должны присутствовать согласно вот этому условию.
То есть, есть и все рёбра полного графа на k вершинах такого,
и все рёбра полного графа на k вершинах такого.
При этом не забывайте, что у них есть ровно одно общее ребро,
которое мы посчитает дважды,
если просто возьмём и возведём в квадрат вот эту вот вероятность.
Значит, что у нас получится?
У нас получится так.
У нас получится p в
степени c из k по два – это вероятность того,
что на i-той сардельке образовался полный граф на k вершинах.
Дальше мы смотрим на те рёбра, которые принадлежат j-той подсардельке.
Их тоже c из k по два.
Но при этом есть одно, ровно одно общее ребро.
Его надо вычесть.
В итоге получаем p в степени дважды c из k по два минус один.
Но если бы мы написали вероятность
Ii равно единице умножить на вероятность Ij равно единице,
то мы, разумеется, получили бы просто p в степени c из k по два,
умножить на p в степени c из k по два.
И это равняется p в степени два на c из k по два.
Таким образом, вот это произведение не
равно вероятности одновременного выполнения наших событий,
а должно бы было равняться, коль скоро эти величины были бы независимы.
То есть уже даже вот в этом случае, когда есть ровно одно общее ребро,
видно, что, по крайней мере подставляя такие «ню» и «мю» мы зависимость получаем,
независимости нету.
Ну значит, её нету и глобально, потому что, если вы помните определение
независимости, то там всё-таки требуется, чтобы для любых «ню» и «мю» вероятность
одновременного выполнения была равна произведению вероятностей.
Здесь же у нас нашлись такие «ню» и «мю», когда
вероятность одновременного выполнения не равна произведению вероятностей.
Ну каждый из вас с лёгкостью может убедиться в том – да это видно из
выкладки, которую мы только что провели – что, если здесь ровно
одно общее ребро заменить на любое другое общее количество – два общих ребра,
три общих ребра, сколько хотите, неважно, сколько общих вершин, и это порождает
общее количество рёбер, то всё равно у вас будет проявляться такая зависимость.
В итоге мы получаем, что наши индикаторы зависимы тогда и только тогда,
когда пересечение соответствующих подсарделек,
то есть i-того и j-того k-элементного подмножеств не меньше двойки.
И, соответственно, «тогда и только тогда» – это уже и предполагает,
что если оно меньше, то они всё-таки независимы.
Вот полное, подробное решение этой задачи.