Так давайте продолжим разбирать задачи на математическое ожидание и в той задаче, о которой мы сейчас поговорим, будет важно все-таки знать, что такое линейность математического ожидания, а не просто действовать по определению, как это было в случае с веб-страницами. Давайте поставим задачу следующим образом: есть множество, состоящее из 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 + ..., + MXnn это вот в точности линейности математического ожидания. И все, что нам остается сделать, это найти математическое ожидание каждой из этих случайных величин. Но это совсем просто. Математическое ожидание X с индексами n, i это уже вот по тому определению, которое мы сегодня использовали и не только сегодня. Это есть 1 умножить на вероятность того, что данный конкретный элемент i в случайной перестановке ς неподвижен. То есть давайте так напишем, вероятность того, что i неподвижен в ς в случайной перестановке, ну а вот эта уже вероятность посчитать вообще не составляет никакого труда. Если мы зафиксировали какой-то элемент, то с какой вероятностью он неподвижен? Ну как водится в классической вероятности, в знаменателе надо написать общее число элементарных исходов, то есть n!, а в числителе надо посчитать, сколько есть всего перестановок, которые вот именно этот элемент i оставляют неподвижным, а остальные элементы как угодно распределяют, то ли подвижно, то ли неподвижно — это все равно. Ну вот понятно, что их n- 1!. Элемент с номером i стоит на месте, а все остальные мы перетасовываем как угодно. Это делается n- 1! способами. Получаем 1 поделить на n и в итоге вот в этом месте получаем n слагаемых, каждая из которых равняется 1 поделить на n. И ответ получен. Все.