Давайте нарисуем заново рисуночек по-другому немножко. Вот у нас есть Mi-тое, вот у нас есть Mj-тое. В каждом из них, конечно, n элементов. Мы знаем, что они как-нибудь точно пересекаются. Давайте обозначим просто h – мощность их пересечения. Это количество их общих элементов, и мы точно уверены в том, что h не меньше 1. Потому что, повторяю, они пересекаются. Просто введем такое обозначение, и в зависимости от того, чему равняется h, получим оценку вероятности вот этого события Bij-того. Так, ну, давайте смотреть. Смотреть будем так. Сначала посмотрим на общую часть двух множеств Mi-того и Mj-того. То есть посмотрим на те элементы, которые находятся в пересечении. Вот что мы про них знаем? Что мы знаем про элементы, которые находятся в пересечении этих двух множеств? Мы знаем, что все эти элементы синие в первом этапе, потому что они все принадлежат множеству Mj-тое. Давайте писать. Меньше, либо равно – пока не понятно почему. Вроде мы пока пишем точное равенство, но я в конечном счете аккуратно скажу, где возникает именно неравенство. Итак, 1/(2 в степени h), сейчас поаккуратнее напишу h. 1/(2 в степени h) – это просто вероятность того, что вот эти h общих элементов, h общих элементов, все покрашены в первом этапе в синий цвет. Но, смотрите, мы же про них еще что-то знаем, про эти элементы. Ааа! Мы знаем, что Mi-тое, которое в частности эти элементы содержит, – внимание! – оно красное целиком во втором этапе. Но это значит, что каждый из этих элементов все-таки поменял свой цвет на противоположный, будучи синим на первой раскраске вот с такой вероятностью, он в итоге оказался красным. То есть, нам еще все это надо умножить на p в степени h. p – это вероятность смены цвета, и мы точно знаем, что h элементов поменяли свой цвет на противоположный. Значит, надо умножить на p в степени h. Повторяю, это пока точное равенство, тут никакого «меньше» нет. Никакого обмана. Перемножаем мы, естественно, за счет независимости, за счет схемы испытаний Бернулли. Давайте, наверное, знаете что, посмотрим теперь вот сюда, на тот кусочек множества Mj-тое, который не содержит элементов из Mi-того. А вот что мы про эти элементы знаем? Что мы знаем про элементы из этого кусочка? Ну, точно, точно мы знаем, что элементы этого кусочка все синие на первом этапе. Вот ничего больше мы про них не знаем с определенностью, потому что мы не знаем, меняли они свой цвет после перекраски, не меняли, но мы точно знаем, что они синие на первом этапе. Что это 1/2, ну а элементов таких у нас (n – h), поэтому мы 1/2 возводим в степень (n – h). И вот, наконец, самый интересный момент. А что же происходит с элементами, которые живут вот здесь, вот в этой части нашей «сосиски» Mi-тое? Берем Mi-тое без Mj-того, то есть те элементы этого множества, которые не попадают в пересечение. Вот про них то мы что знаем? А про них мы знаем, в общем, то же самое, что знали с самого начала. Мы знаем, что они – какие-то. Мы даже не знаем: хорошие они или не хорошие. Нет, ну, наверное, хорошие, да? Но какие-то на первом этапе и красные в результате второго этапа. Смотрите: вот это «какие-то» оно подсказывает, что надо сделать что-то, что привлечет формулу полной вероятности. Нужно рассмотреть случай, какими эти элементы могли быть, вот каждый из этих элементов? Берем какой-то элемент x, принадлежащий множеству Mi-тое без Mj-тое. Каким он мог быть на первом этапе? Понятно, есть два варианта: либо x – красный на первом этапе, либо x – синий на первом этапе. Никаких других вариантов нет. Вот вам и формула полной вероятности. То есть, давайте посмотрим на случай, когда x красный на первом этапе. Вот, если он красный на первом этапе, тогда как он мог стать красным на втором? А черт его знает. Может быть он пытался перекраситься, и ему это не удалось. Конечно, он станет это делать только в случае, если сам находится в каком-то целиком красном множестве. Но мы же не знаем, понятия не имеем, этот конкретный x, находится он целиком в каком-нибудь красном множестве или не находится. Знать не можем. Но такое теоретически может быть. А может быть, он не находится ни в каком красном множестве, и он просто не перекрашивался, а остался красным, каким и был на первом этапе. Короче говоря, вероятность того, что он на первом этапе красный – это 1/2, а вероятность того, что он остался красным после второго этапа, ну, она точно не превосходит 1. Вот именно здесь появляется значок неравенства. Ну, конечно, любая вероятность не превосходит 1. Плевать нам на то, как он остался красным. Остался и слава Богу! Произошло это с вероятностью не больше, чем 1. А вот во втором случае здесь будет точное равенство, потому что если x – синий на первом этапе, и это происходит с вероятностью 1/2, то, зная, что он стал красным в результате второго этапа, мы можем сказать, что произошла перекраска, и это происходит с вероятностью p. Короче говоря, вот здесь возникает такая штука: (1/2 + p/2) и все это в степени (n – h). Вот это вот то, что я здесь написал, – это в точности формула полной вероятности. Либо x – красный, и тогда с вероятностью, не превосходящей 1, он останется красным в результате второго этапа, либо x – синий, что происходит с вероятностью 1/2, и тогда с вероятностью в точности p он таки станет красным в результате второго этапа. Поэтому верхняя оценка получается ровно такой, какой она у нас получилась. Ну, давайте немножко ее еще причешем. = p в степени h * (1 + p) в степени (n – h). И надо еще собрать вместе все двойки. Давайте как-нибудь аккуратно соберем. Значит, 2 в степени –h отсюда, из этого сомножителя. Из этого сомножителя будет + Эээ... Сейчас, сейчас, сейчас... 2 в степени –h, да, + h – n. И из вот этой вот половинки у нас получается еще раз + h и – n. Вот так вот. Значит, эти два – шлеп, шлеп – сокращаются. Тут получается (h – 2n). Итого имеем (p в степени h) * (1 + p) в степени (n – h) и * 2 в степени (h –2n). Вот, оценили, наконец, вероятность события Bij-того. Давайте заметим теперь, что мы же не знаем, чему равняется вот это число h. Мы лишь знаем, что оно не меньше 1. Легкое упражнение по анализу, которое я не буду за вас решать, друзья, говорит нам, что это всегда не больше, чем если подставить сюда вместо h в точности единичку. То есть, максимум достигается тогда, когда h таки равняется в точности 1. То есть, мы получаем такое неравенство: p * (1 + p) в степени (n – 1) * 2 в степени (1 –2n). Вот такое вот замечательное неравенство. Давайте соберем все вместе. Во-первых, заметим, что вероятность Ci-того – вот она у нас там замечательным образом написана – не превосходит количество слагаемых, которые присутствуют в этом суммировании. Ну, сколько здесь слагаемых? Ну точно не больше, чем всего слагаемых вообще, какие могли бы возникнуть. То есть, точно не больше, чем m. Это я огрубляю достаточно сильно. Помножить на вот эту вот величину, которая служит оценкой вероятности каждого из слагаемых. (1 + p) в степени (n – 1) * 2 в степени (1 – 2n). Вот такая вероятность Ci-того у нас получилась.