Проанализируйте следующее вероятностно-комбинаторное утверждение: "При случайной перестановке n различных предметов ожидаемое число позиций, в которых предмет остался на своём месте, равно 1". Докажите это утверждение разными способами (линейность ожидания, индикаторные переменные) и обсудите, какие интуитивные ловушки могут ввести учащихся в заблуждение
Проанализируйте следующее вероятностно-комбинаторное утверждение: "При случайной перестановке n различных предметов ожидаемое число позиций, в которых предмет остался на своём месте, равно 1". Докажите это утверждение разными способами (линейность ожидания, индикаторные переменные) и обсудите, какие интуитивные ловушки могут ввести учащихся в заблуждение
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
1) Доказательство через индикаторные переменные и линейность ожидания.
Пусть XXX — число «фиксированных» позиций (fixed points) в случайной перестановке π\piπ из SnS_nSn . Для i=1,…,ni=1,\dots,ni=1,…,n введём индикатор
Xi={1,если π(i)=i,0,иначе. X_i=\begin{cases}1,&\text{если }\pi(i)=i,\\0,&\text{иначе.}\end{cases}
Xi ={1,0, если π(i)=i,иначе. Тогда X=∑i=1nXiX=\sum_{i=1}^n X_iX=∑i=1n Xi . По линейности математического ожидания (независимость не требуется)
E[X]=∑i=1nE[Xi]=∑i=1nPr(π(i)=i). \mathbb{E}[X]=\sum_{i=1}^n \mathbb{E}[X_i]=\sum_{i=1}^n \Pr(\pi(i)=i).
E[X]=i=1∑n E[Xi ]=i=1∑n Pr(π(i)=i). Для фиксированного iii число перестановок с π(i)=i\pi(i)=iπ(i)=i равно (n−1)!(n-1)!(n−1)!, поэтому Pr(π(i)=i)=(n−1)!/n!=1/n\Pr(\pi(i)=i)=(n-1)!/n!=1/nPr(π(i)=i)=(n−1)!/n!=1/n. Следовательно
E[X]=∑i=1n1n=1. \mathbb{E}[X]=\sum_{i=1}^n \frac{1}{n}=1.
E[X]=i=1∑n n1 =1.
2) Комбинаторическое (подсчёт пар).
Посчитаем количество пар (π,i)(\pi,i)(π,i), где π∈Sn\pi\in S_nπ∈Sn и π(i)=i\pi(i)=iπ(i)=i. Для каждого фиксированного iii таких перестановок (n−1)!(n-1)!(n−1)!, всего пар n⋅(n−1)!n\cdot(n-1)!n⋅(n−1)!. Делим на число перестановок n!n!n! — получаем среднее количество фиксированных позиций на одну перестановку:
n⋅(n−1)!n!=1. \frac{n\cdot (n-1)!}{n!}=1.
n!n⋅(n−1)! =1.
3) Симметрия / вероятность.
Из симметрии все позиции равнозначны, поэтому каждая позиция фиксируется с вероятностью 1/n1/n1/n. Сумма этих вероятностей по всем nnn позициям даёт ожидаемое число фиксированных позиций 111.
Дополнительное замечание (распределение): для больших nnn число фиксированных позиций сходится по распределению к закону Пуассона с параметром 111: X→dPois(1)X\overset{d}{\to}\mathrm{Pois}(1)X→dPois(1). В частности Pr(X=0)→e−1≈0.3679\Pr(X=0)\to e^{-1}\approx0.3679Pr(X=0)→e−1≈0.3679, Pr(X=1)→e−1\Pr(X=1)\to e^{-1}Pr(X=1)→e−1, но E[X]=1\mathbb{E}[X]=1E[X]=1 всегда.
Интуитивные ловушки и типичные ошибки:
- Ошибка: думать, что линейность ожидания требует независимости. Наоборот, линейность верна без независимости.
- Ошибка: путать математическое ожидание и «типичное» (модальное или медианное) значение. Ожидание равно 111, но самая вероятная конкретная величина может быть 000 (для больших nnn Pr(X=0)≈0.37\Pr(X=0)\approx0.37Pr(X=0)≈0.37).
- Ошибка: интерпретировать E[X]=1\mathbb{E}[X]=1E[X]=1 как «в каждой перестановке ровно один фикс-поинт» или как вероятность существования хотя бы одного фикс-поинта, — это неверно.
- Ошибка: попытка суммировать вероятности без учёта симметрии или неверный подсчёт числа перестановок с данным фикс-поинтом.
Вывод: все доказательства согласуются — ожидаемое число предметов, оставшихся на своих местах при случайной перестановке nnn элементов, равно 111.