Условие
В стиральной машинке во время стирки перемешалось большое количество пар носков — n пар, все пары разные.
а) Я в случайном порядке достаю носки по одному до получения первой пары. Пусть мне потребуется T носков. Найдите точное значение E(T), приближённое выражение для E(T) без факториалов и приближённое значение P(T/√n≤x).
б) Я достаю случайное количество носков S, где S равновероятно принимает значения от 0 до 2n включительно. Сколько в среднем полных пар я достану?
Решение источника
Источник приводит только ответы со ссылками на литературу: E(T)=22n/C(2n, n)≈√(πn); P(T/√n≤x)≈1−exp(x²/4); во втором пункте — N/3.
Редакционное объяснение
Хвост распределения T. Событие T>k означает, что первые k носков взяты из разных пар. Выбрать k пар можно C(n, k) способами, а из каждой пары — один из двух носков, поэтому
P(T>k)=C(n, k)·2k/C(2n, k), k=0, 1, …, n.
При k>n вероятность равна нулю: среди n+1 носков обязательно есть пара, так что T≤n+1.
Точное среднее. E(T)=ΣP(T>k) по k от 0 до n. После подстановки j=n−k слагаемое принимает вид (2n/C(2n, n))·C(n+j, j)·2−j. Сумма C(n+j, j)·2−j по j от 0 до n равна 2n — это то же тождество, которое обеспечивает сумму вероятностей 1 в задаче о спичках Банаха. Поэтому
E(T)=4n/C(2n, n)≈√(πn)
(приближение — по формуле Стирлинга). Примеры: n=1 даёт 2 (два носка одной пары), n=2 — 8/3, n=10 — ≈5,68, n=100 — ≈17,75 при √(100π)≈17,72.
Предельное распределение. P(T>k)=∏(2n−2j)/(2n−j) по j от 0 до k−1, и каждый множитель равен 1−j/(2n−j)≈exp(−j/(2n)). Отсюда P(T>k)≈exp(−k²/(4n)) и
P(T/√n≤x)≈1−exp(−x²/4) — распределение Рэлея.
Исправление: в источнике пропущен минус в показателе. Выражение 1−exp(x²/4) отрицательно при x>0 и не может быть вероятностью. Согласованность с первым ответом: ∫0∞ exp(−x²/4) dx=√π, то есть E(T)/√n≈√π. Точный расчёт при n=10 000 даёт для x=1 и x=2 вероятности 0,2202 и 0,6340 против приближённых 0,2212 и 0,6321.
Пункт б). Если достать s носков, конкретная пара окажется среди них целиком с вероятностью C(2n−2, s−2)/C(2n, s)=s(s−1)/(2n(2n−1)), а среднее число полных пар равно s(s−1)/(2(2n−1)). Усредняя по равновероятным s от 0 до 2n, используем Σs(s−1)=(2n+1)·2n·(2n−1)/3 и получаем
среднее число полных пар = n/3.
Исправление: «N/3» в источнике означает n/3 — опечатка в обозначении.
Проверка: точное равенство E(T)=4n/C(2n, n) проверено в рациональных числах для n=1, 2, 3, 5, 10, 30, 100; формула пункта б) — для n=1, 2, 3, 5, 10, 50, а условные средние — полным перебором при n=3; моделирование 200 000 опытов при n=50 дало E(T)≈12,567 против точного 12,565.
Что не следует из ответа
Первая пара появляется на масштабе √n, а не n: при 100 парах в среднем хватает примерно 18 носков. Это то же явление, что в парадоксе дней рождения.
Ответы требуют, чтобы все пары были разными, а порядок извлечения — случайным. Если же носки не различаются, любые два уже образуют пару, а при носках двух цветов пара гарантированно найдётся среди трёх.
Ответ n/3 относится к случайному S. При фиксированном S=n (достали половину носков) среднее число полных пар равно n(n−1)/(2(2n−1))≈n/4.
Борис Демешев и участники · probability_dna, задача «Носки в стиральной машинке» · Исходное задание и решение · CC BY 4.0. Адаптация: к ответам источника добавлены выводы; исправлены знак в показателе экспоненты (1−exp(−x²/4) вместо 1−exp(x²/4)) и обозначение N/3 → n/3; добавлены численные проверки.