Ожидание числа неподвижных точек случайной перестановки

Научная визуализация Ожидание числа неподвижных точек случайной перестановки

Ожидание числа неподвижных точек случайной перестановки. Диагональ кодирует неподвижные точки.

E[X]=ΣᵢE[Iᵢ]=n·(1/n)=1

Диагональ кодирует неподвижные точки.

Задача

Случайная перестановка n элементов равномерна среди n! вариантов. Сколько элементов в среднем остаются на своих местах?

Пусть I_i=1, если элемент i остаётся на месте. Тогда X=ΣI_i.

Для фиксированного i его образ равномерно выбирается из n позиций, поэтому

P(I_i=1)=1/n.

E(X)=ΣE(I_i)=n·(1/n)=1.

Независимость индикаторов для этого расчёта не требуется; они действительно зависимы.

Результат верен для любого n≥1, хотя само распределение X меняется и при больших n приближается к Poisson(1).

Редакционная практика по индикаторам probability_pro · CC BY 4.0.