И еще одна симпатичная задачка на линейность математического ожидания в
духе того, какими вещами мы до сих пор занимались, например,
в рамках схемы испытаний Бернулли.
Не случайный граф.
Вот не случайный граф.
Но все равно берется множество, состоящее из n элементов,
и вероятность p, но только строится не случайный граф, а случайные подмножества.
Мы с таким неоднократно сталкивались.
Строятся случайные подмножества A1,
..., A с индексом m согласно схемы испытаний Бернулли.
Все вот просто очень-очень до боли знакомо.
То есть каждый элемент из исходного множества мы,
независимо от всех остальных элементов с вероятностью p, кладем в множество A1,
потом точно так же строим A2 и так далее вплоть до A с индексом m.
Вот у нас получается набор случайных множеств.
Давайте определим случайную величину ξ, которая зависит от этого набора.
То есть элементарным событием мы здесь считаем весь набор случайных множеств.
И определяем случайную величину ξ следующим образом – это количество
пар индексов i,
j таких, что Ai-тое, пересеченное с Aj-тым пусто.
Предлагается, как ни странно,
снова найти математическое ожидание такой вот случайной величины.
Ну это линейность.
Конечно, линейность.
Давайте сделаем следующее.
Как, опять таки, перечислить все возможные пары индексов,
для которых там что-то произошло?
Ну надо перебрать, вообще, все возможные пары, вообще,
все возможные пары индексов, и про каждый из них...
про каждую из них понять: а вот для нее, родной и хорошей, верно,
что Ai-тое, пересеченное с Aj-тым пусто или нет?
Вот сколько раз будет «верно» – столько раз и счастье.
Ну вот давайте так и напишем.
Матожидание суммы по всем i не равным j...
Ну здесь, наверное, все-таки надо считать, что пары неупорядоченные,
потому что с какой радости нам отдельно рассматривать Ai-тое Aj- тое,
а потом еще отдельно брать Aj-тое Ai-тое?
Ну давайте считать, например, что i строго меньше, чем j.
Так, понятно будет.
Вот.
Ну а здесь индикаторы ξi-тое, j-тое.
То есть ξi-тое, j-тое на элементарном исходе на совокупности множеств A1, ...,
Am принимает значение, представьте себе, 1 и 0.
Причем 1 – если конкретно Ai-тое,
пересеченное с Aj-тым, пусто, и 0 – естественно, иначе.
Как это ни удивительно.
Вот опять такая задачка, да.
Пользуемся линейностью математического ожидания.
Получаем сумму по всем i меньшим j.
Ну я не буду писать i не равно j ,потому что если i < j, то оно j и не равняется.
Вот. Ну а здесь математическое ожидание
ξi-того, j-того.
Ну и что такое математическое ожидание ξi-того, j-того?
По определению это вероятность того, что два случайных множества,
построенные согласно схеме испытаний Бернулли независимо друг от друга,
имеют пустое пересечение.
Еще раз, вот это математическое ожидание – это просто вероятность вот этого события.
Мы в этом месте вообще можем забыть про все остальные случайные множества.
Вот мы два их построили и хотим найти вероятность того, что они не пересекаются.
Но ведь такую вероятность мы с вами уже считали, когда занимались схемой Бернулли.
Эта вероятность есть не что иное...
Ну давайте я еще раз напишу, значит, сумма по i меньшим j вероятности того,
что Ai-тое, пересеченное с Aj-тым, пусто.
...пересеченное с Aj-тым, пусто.
Эту вероятность мы считали.
Это есть не что иное, как (1 – p²) в n-й степени.
Все.
Получаем сумму по всем i
меньшим j (1 – p²) в n-й степени.
Ну, если хотите, я напомню, конечно, откуда взялось (1 – p²).
Мы просто рисовали такую табличку размера 2 × n и смотрели на каждый
столбик по отдельности, то есть смотрели на каждый элемент потенциальный вот этих
множеств – входит он сюда или сюда, или никуда, или куда-то.
Ну (1 – p²) — это вероятность того просто, что данный элемент...
p² — это вероятность того, что данный элемент принадлежит обоим множествам,
а (1 – p²) — это вероятность того, что он не принадлежит хотя бы одному из них.
Но тогда по этому элементу они заведомо не пересекаются.
Все. Вероятность того,
что вообще не пересекаются – это, стало быть, есть (1 – p²) в n-й степени.
Ну посмотрите другую задачку, там я подробно это рассказываю.
А теперь мы видим, что суммирование-то оно идет по i и j.
А здесь где i и j?
Нигде.
От i и j эта величина никак не зависит.
То есть нам просто надо написать количество слагаемых,
помноженное на эту величину.
Ну слагаемых, очевидно, C из n по 2 – число неупорядоченных пар элементов из n,
– ну и умножаем на (1 – p²) в n-й степени,
в итоге получая ответ на поставленный в задаче вопрос.