Так давайте продолжим разбирать задачи на математическое ожидание и в той задаче,
о которой мы сейчас поговорим, будет важно все-таки знать,
что такое линейность математического ожидания,
а не просто действовать по определению, как это было в случае с веб-страницами.
Давайте поставим задачу следующим образом: есть множество,
состоящее из n элементов — это наш конек такие множества,
мы их постоянно рассматриваем в разных контекстах.
И давайте сделаем случайную перестановку элементов этого множества.
Рассмотрим случайную перестановку случайная
перестановка элементов этого множества.
Ну если, например,
обозначать как водится в математике перестановку ς вот так вот, например,
часто пишут ς — это вот такая вот перестановка то конечно предполагается,
что вероятность каждой перестановки это есть 1 поделить на n!.
То есть в данном случае мы находимся опять в классическом определении,
в рамках классического определения вероятности.
Всего n!
различных перестановок и мы наугад выбираем из этого множества мощности n!
одну случайную перестановку.
Так вот теперь на пространстве случайных перестановок определяется
случайная величина Xn, которая, будь в нее подставлена некоторая ς,
некоторая перестановка, выдает нам вот чего.
Количество элементов нашего исходного
множества то есть из вот этого множества: 1, 2, ...,
n которые сохранили позиции при вот этой вот перестановке ς которые не шелохнулись,
так сказать, сохранили позиции,
сохранили позиции
при перестановке ς.
Ну, товарищи,
как всегда, в этом месте я еще и еще раз повторяю, что случайная величина,
она случайна до тех пор, пока мы не знаем, какая ς на нее свалится.
Но как только ς свалилась, то естественно, Xn-нная от ς вот так вот вычисляется.
То есть ς выпала какая-то после эксперимента так сказать,
мы запустили ее на нашем множестве,
какие-то элементы поменяли свои позиции, а какие-то остались на местах.
Вот Xn-нная посчитала,
сколько таких оставшихся на своих местах элементов у нас есть.
И нас интересует в этой задаче просто математическое ожидание этой
случайной величины.
Сколько в среднем таких элементов, которые не поменяли свои позиции.
Можно конечно пытаться воспользоваться той формулой, с помощью которой мы
решили задачу про пользователя, который выбирает там из скольких-то веб-страниц.
Но в этом случае, вам придется перечислить те значения,
которые может принимать случайная величина Xn, и найти вероятность каждого из них.
И вот это будет довольно противно.
А если действовать с помощью линейности, то все получится совсем в одну строчку.
Смотрите, вот как заставить условно говоря, компьютер,
машину да, посчитать сколько есть таких неподвижных элементов.
Поступила к нему ς какая-то перестановка, вот как посчитать,
сколько в этой конкретной ς неподвижных элементов?
Ну давайте просто двигаться по вот этому списку и смотреть,
а элемент 1 — он неподвижен?
Ну если неподвижен — отлично, записываем в копилку, складываем.
Если нет, ну значит счетчик обнуляется.
Дальше, если 2 неподвижна, если она не изменила свою
позицию в результате перестановки, ну отлично, значит ее добавляем к счетчику.
Если нет, не добавляем ничего.
И так далее, просто перебирая все вот эти вот n элементов.
Таким образом, понятно, что Xn-нное представляется, если угодно,
как Xn1 +, ..., + Xnn,
где Xn i-ое — это такой индикатор
то есть случайная величина, которая принимает всего 2 значения — 1 или 0.
1 она принимает, если,
если в данной перестановке ς элемент
i неподвижен, не изменил свою позицию.
Элемент i — неподвижен и 0 в противном случае.
И 0, иначе.
Ну тогда мы воспользуемся, конечно, линейностью математического ожидания.
То есть напишем, что MXn — это есть MXn1 + ...,