Так, давайте разберём задачу про пересечение нескольких случайных
подмножеств.
Задача ставилась следующим образом: у нас есть множество чисел от 1 до n,
ну, просто множество некоторое, состоящее из n элементов,
и есть число p из отрезка [0, 1], которое отвечает
за вероятность вытаскивания любого из этих элементов из этого множества.
Нужна она для того, чтобы строить случайные подмножества этого множества.
Мы на лекции нечто подобное делали, я разбирал пример такой задачи, когда
вытаскивались два случайных подмножества, каждое с вероятностью успеха p,
и потом считалась вероятность того, что эти два подмножества не пересекаются.
Ну, вот сейчас будет обобщение этой задачи, давайте ещё раз вспомним ту схему,
с помощью которой вытаскиваются наши подмножества.
Вообще, в итоге у нас должно получиться некоторое количество этих подмножеств,
которое мы обозначим m, то есть у нас есть три уже параметра n, p и m в этой задаче,
и каждое из этих подмножеств, ну, как бы совершенно независимо от того,
как строятся все предшествующие и, впрочем, все последующие тоже, каждое из
этих подмножеств строится так: ну, вот, давайте, допустим, A1, как его построить?
Строится оно так: берем схему из n испытаний Бернулли с ну вот этой
вероятностью успеха p, и если в очередном испытании происходит успех,
то элемент с номером этого испытания кладётся в строящееся множество A1,
а если неудача, то не кладется.
То есть, каждый элемент от 1 до n входит в строящееся
множество A1 с вероятностью p независимо ото всех остальных,
ну и с вероятностью (1 − p) или q, если хотите, он туда не входит.
И то же самое касается A2, то же самое касается A3, то же самое касается Am.
То есть, такая вот есть очень-очень длинная схема испытаний Бернулли,
мы сначала строим A1, потом A2, и так далее, они могут совпадать,
могут как угодно располагаться друг относительно дружки,
но в итоге нам нужно посчитать вероятность того,
что общее пересечение этих множеств A1 и так далее,
Am пусто, то есть попарно, там, потройно, как хотите, они могут пересекаться,
но, вот так чтобы все эти m множеств пересекались, такое запрещено.
Вот, спрашивается, чему равна такая вероятность?
Что ж, давайте действовать так, как в точности я разбирал это дело на лекции,
когда у меня было два множества.
На лекции было два множества, и мне хотелось найти вероятность того,
что они не пересекаются.
Я интерпретировал эти множества как последовательности из нулей и единиц.
А именно, я писал так: вот, у меня есть A1 и по сути,
поскольку оно строится с помощью схемы испытаний Бернулли,
эта последовательность каких-то единичек и ноликов в каком-то там порядке,
где единицы ставятся ровно на позиции с номерами из вот этого множества A1.
То есть множество A1 – это 1, 3, 4, n в данном случае.
Ну, и там какие-то еще промежуточные элементы, наверное, в множество A1 входят.
Я, конечно, не утверждаю, что множество A1 именно такое.
Я нарисовал его совершенно случайно.
Если хотите, закрыл глаза и расставил единички и нолики так, как придется.
И точно так же случайно строится множество A2,
какое-то там 0, 1, 1, 0, 1, 1, не важно.
И так далее, в таком же стиле строится случайное множество Am,
но удобно интерпретируется с помощью последовательности ноликов и единичек.
Ну, не знаю, 1, 1, 0, 0, 1, и так далее, 1.
Что-то такое, сейчас совершенно не важно, как оно выглядит.
В принципе, оно вполне может совпадать с кем-то из предшественников,
как я уже говорил.
Важно лишь понять, как теперь найти вероятность того, что вот эти вот все
множества, которые мы построили, вообще между собой не пересекаются.
Не вообще не пересекаются, но в совокупности не пересекаются.
Все вместе не пересекаются.
Ну, давайте попробуем осознать, что означает вот это событие.
Как оно раскладывается на какие-то ситуации, что ли.
Что, что ему благоприятствует.
Ну вот, давайте посмотрим, как и на лекции, кстати, мы смотрели,
давайте посмотрим, например, на первый столбец.
Вот в этой, ну, так сказать, матрице, в этой таблице, которая состоит из нулей
и единиц, по строчкам записаны множества, а, вот, что написано по столбцу?
Столбец отражает вхождение, вот,
первый столбец, отражает вхождение элемента с номером 1,
вхождение элемента с номером 1 в наше множество.
Смотрите, если здесь нарисована единичка, это уже означает,
что элемент с номером 1 попал в множество A1.
Если здесь нарисован нолик, то это означает,
что элемент с номером 1 в множество A2 не попал.
Ну, и, наконец, вот здесь нарисована единичка, значит,
элемент с номером 1 оказался внутри множества A с индексом m.
А вообще, тот столбец, вот, как он здесь нарисован, он показывает следующее:
он показывает, что элемент с номером 1 попал в некоторые из наших множеств,
но нашлось, по крайней мере, одно множество, в которое он не попал.
Но это означает, товарищи, смотрите, вот,
если элемент с номером 1 хотя бы в одно из наших множеств не попал, это,
конечно, означает, что он не попал в их совокупное пересечение.
Не может элемент с номером 1 лежать в пересечении всех-всех-всех,
если он заведомо не лежит в множестве A2, это очевидно.
Понимаете, да?
Смотрим на второй столбец, ага,
тут тоже есть нолики вот в этом втором столбце, ну, по крайней мере, один.
Это означает, что элемент с номером 2 тоже не может оказаться внутри пересечения.
А вот, если бы нашелся хотя бы один столбец, вот,
у меня тут потенциальный есть такой герой, если б нашелся хотя бы один столбец,
в котором стоят сплошь единицы, то такой столбец уже
свидетельствовал бы о том, что вот это пересечение множеств не пусто.
То есть, давайте так: пересечение множеств пусто,
вот это вот событие — это в точности то же самое,
это в точности то же самое, что в каждом столбце вот в этой таблице,
в каждом столбце есть хотя бы один ноль.
Хотя бы один ноль.
Повторяю, если бы хоть один столбец содержал сплошные единицы,
то по элементу с номером этого столбца наши множества пересекались бы в
совокупности, а мы смотрим событие, которое состоит в обратном,
что они все-таки ни по какому элементу не пересекаются.
Поэтому получается, что вот это вот обратное событие равносильно тому,
что в каждом столбце нашей таблицы есть хотя бы один нолик, хотя бы один нолик.
Ну, стало быть, будем искать вероятность,
которая нас интересует, как вероятность того, что я вот здесь написал.
Вероятность того, что в каждом столбце есть хотя бы один ноль.
Ну, смотрите, вот это свойство,
что в данном столбце есть хотя бы один ноль, оно, конечно,
по столбцам независимо, то есть если мы посчитаем вероятность того,
что в данном столбце есть хотя бы один ноль, а потом возведем эту вероятность в
n-ую степень, то есть перемножим её по всем нашим столбцам, то, естественно,
мы и получим тот ответ, который нам нужен.
То есть, давайте так и напишем: вероятность того,
что в данном фиксированном, например,
первом столбце есть хотя бы один ноль,
хотя бы один ноль,
так, и это вероятность в n-ой степени.
Очевидно, надо её возвести в n-ую степень, потому что по столбцам имеется,
конечно, независимость.
Взаимная, совокупная независимость.
Так, ну, и с какой же вероятностью в данном столбце есть хотя бы один ноль?
Ну, проще, наверное, посчитать вероятность того, что там стоят сплошные единицы.
То есть, пользуемся свойством вероятность A с чертой равняется
1 минус вероятность A, пишем, 1 минус вероятность того,
что в данном столбце...столбце,
сплошные единицы,
так, все это в n-ой степени, но а уж вероятность того,
что в данном столбце сплошь стоят единицы, она совсем просто считается,
ведь вероятность каждой единицы- это просто P, и должно быть m ровно единиц.
Ну, то есть P в m-ой степени.
Все, получаем ответ: (1 − p в m-ой) в n-ой.
Ну, это прекрасно согласуется с результатом,
который у нас был как раз получен в качестве примера на лекции,
потому что там в качестве m рассматривалась двойка, и,
если вы помните, там как раз получалось (1 − p²) в n-ой степени.
Ну, такое вот, приятное и естественное обобщение.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
