38
правок
Изменения
→Использование линейности - Добавлен новый пример
Итоговый результат: <tex>E(\xi)={\sum_{i=1}^n \limits}E(\xi^i)=\frac{n}{k} </tex>
===Пример 3===
Найти математическое ожидание количества инверсий на всех перестановках чисел от 1 до n.
Пусть <tex> \xi </tex> - случайная величина, которая возвращает количество инверсий в перестановке.
Очевидно, что вероятность любой перестановки равна <tex> {1 \over n!} </tex>
Тогда <tex> E\xi = {1 \over n!}\cdot{\sum_{i=1}^{n!}}E(\xi^i) </tex>
Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является перестановкой чисел <tex> 1, 2,\dots, n</tex>.
Тогда <tex> A = (p_n, p_{n-1}, \dots, p_1) </tex> является перевернутой перестановкой <tex> P </tex>.
Докажем, что количество инверсий в этих двух перестановках равно <tex> n\cdot(n-1) \over 2 </tex>
Рассмотрим все пары <tex> 1 \leqslant i < j \leqslant n </tex>, таких пар всего <tex> n\cdot(n-1) \over 2 </tex>. Тогда пара этих чисел образуют инверсию или в <tex>P</tex>, или в <tex>A</tex>. Если <tex>j</tex> стоит раньше <tex>i</tex> в перестановке <tex>P</tex>, то <tex>j</tex> будет стоять после <tex>i</tex> и уже не будет давать инверсию. Аналогично, если <tex>j</tex> стоит раньше <tex>i</tex> в перестановке <tex>A</tex>.
Всего таких пар из перестановки и перевернутой перестановки будет <tex> {n! \over 2} </tex>.
Итого: <tex> E\xi = {1 \over n!}\cdot{n \cdot (n-1) \over 2}\cdot{n! \over 2} = {n \cdot (n-1) \over 4} </tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
