Задача 65343

Темы:    [ Дискретное распределение ] [ Средние величины ] [ Условная вероятность ] [ Произведения и факториалы ] [ Суммы числовых последовательностей и ряды разностей ]

Сложность: 4+ Классы: 9,10,11

Условие

На сушке в случайном порядке (как достали из стиральной машины) висит n пар носков. Двух одинаковых пар нет. Носки висят за сохнущей простыней, поэтому Рассеянный Учёный достает по одному носку на ощупь и сравнивает каждый новый носок со всеми предыдущими. Найдите математическое ожидание числа носков, снятых к моменту, когда у Учёного окажется какая-нибудь пара.

Решение

  Назовём ξ_n случайную величину, равную числу снятых носков при условии, что на сушке висит n пар. Очевидно,  Eξ₁ = 2.
  Пусть  n > 1.  Пронумеруем носки в том порядке, в каком Рассеянный Учёный их снимает с сушки. (Очевидно, способ нумерации не играет роли.) В этой нумерации какой-то носок является последним (его номер 2n, и он никогда не будет снят, поскольку носок с номером  n + 1  наверняка образует пару с каким-либо предыдущим). Отличим как-нибудь этот последний носок: пусть он будет белым.
  Обозначим через p_j,n вероятность события  ξ_n = j.  Очевидно,  p_{1, n} = 0.
  Найдём p_2,n. Все зависит от того, где висит другой белый носок. Если он висит на первом или втором месте (вероятность этого ²/_2n–1), то первые два носка пару не образуют. Если же он висит на третьем или последующих местах (вероятность этого равна ^2n–3/_2n–1), то условная вероятность того, что первые два носка образуют пару равна p_2,n–1 – это вероятность получить пару со второй попытки, выбрасывая из последовательности оба белых носка. По формуле полной вероятности получаем: .
  Аналогично найдём p_3,n. Если белый носок висит на одном из двух первых мест (с вероятностью ² /_2n–1), то условная вероятность того, что третий носок даст пару, равна вероятности того, что второй носок даст пару в последовательности без белых носков. Если белый носок на третьем месте (вероятность ¹/_2n–1), то условная вероятность того, что третий носок даст пару, равна 0, поскольку он белый, а парный к нему висит в конце. Если белый носок висит далее третьего места (вероятность ^2n–4/_2n–1), то условная вероятность того, что первые два носка образуют пару, равна p_3,n–1, поскольку в этом случае наличие белых носков роли не играет. Формула полной вероятности даёт: .
  Рассуждая аналогично и дальше, получаем:    для всех k от 2 до n.

  Если всего пар  n – 1,  то вероятность того, что первая пара получится на (n+1)-м носке, равна нулю:  p_n+1,n–1 = 0.  Поэтому для  k = n + 1  получаем:  
  Найдём теперь математическое ожидание:

  Группируя слагаемые при p_k,n–1, получаем:

  Полученное соотношение даёт возможность вычислить Eξ_n, зная, что  Eξ₁ = 2:

  Для получения приближения при больших n воспользуемся формулой Стирлинга:  .  Получаем:  

Ответ

Замечания

Скажем, если на сушке висит 2012 пар носков, то точная формула даст  Eξ₂₀₁₂ ≈ 79,509,  а приближенная даст     Погрешность менее 0,065%. Таким образом, если на веревке 4024 носка, то Рассеянному Учёному в среднем повезет уже на 79-80-й попытке.

Источники и прецеденты использования

олимпиада
Название	Заочная олимпиада по теории вероятностей и статистике
год
Дата	2012
задача
Номер	19