Условие
На самолёт со 100 местами проданы все билеты. Пассажиры садятся по очереди. Первые 99 пассажиров — сумасшедшие старушки: каждая садится на случайно выбранное свободное место. Последний пассажир идёт на место, указанное в его билете. Если оно занято, он с помощью стюардессы сгоняет старушку со своего законного места. Согнанная старушка становится благоразумной и идёт на своё место по билету; возможно, ей придётся согнать ещё одну старушку, и так далее.
а) Какова вероятность того, что потревожат старушку, стоявшую i-й в очереди?
б) Каково ожидаемое количество потревоженных старушек?
в) Как распределено количество потревоженных старушек?
Решение источника
Источник рассматривает конкретную старушку, например № 42, и цепочку пересаживаний, которую запускает последний пассажир. Рано или поздно цепочка выйдет либо на старушку № 42, либо закончится, не дойдя до неё. По симметрии эти исходы равновероятны, поэтому вероятность потревожить конкретную старушку равна 1/2, а для очереди длины n ожидаемое число потревоженных R равно (n−1)/2.
Распределение находится пошагово: P(R=0)=1/n — место последнего пассажира оказалось свободным. Если последний пассажир кого-то потревожил, задача сводится к такой же, но с очередью на одного человека короче. Отсюда P(R≥2)=(n−1)/n·(n−2)/(n−1)=(n−2)/n, P(R≥3)=(n−3)/n и так далее: R равновероятно принимает значения 0, 1, …, n−1, и снова E(R)=(n−1)/2.
Редакционное объяснение
Сведём задачу к случайной перестановке. Пусть σ(k) — место, которое занял k-й пассажир при первой посадке, а для последнего пассажира σ(100) — единственное место, оставшееся свободным после старушек. Первая старушка выбирает одно из 100 мест, вторая — одно из 99 оставшихся и так далее, поэтому все 100! вариантов σ равновероятны: σ — равномерная случайная перестановка. Место j считаем «принадлежащим» пассажиру j по билету.
Последний пассажир идёт на место 100. Если там сидит старушка a1, то есть σ(a1)=100, она идёт на место a1; там может сидеть старушка a2 с σ(a2)=a1, и так далее. Цепочка обрывается, когда очередная старушка идёт на своё место σ(100), которое свободно. Значит, потревоженные старушки — это в точности остальные элементы цикла перестановки σ, содержащего элемент 100, а R+1 — длина этого цикла.
Длина цикла, содержащего фиксированный элемент, равномерна на {1, …, n}: при обходе цикла каждый следующий элемент оказывается новым с вероятностями (n−1)/n, (n−2)/(n−1), …, а цикл замыкается на k-м шаге с вероятностью 1/(n−k+1). Произведение телескопируется в 1/n. Это и есть пошаговое рассуждение источника.
Ответы для n=100:
а) Если длина цикла равна k, то конкретная старушка попадает в него с вероятностью (k−1)/99. Усредняя по равномерному k, получаем (1/100)·Σ(k−1)/99=1/2. Вероятность равна 1/2 для любого i: порядок в очереди не важен, потому что итоговая перестановка равномерна.
б) По линейности ожидания E(R)=99·1/2=49,5.
в) P(R=k)=1/100 при k=0, 1, …, 99. Дисперсия равномерного распределения: Var(R)=(100²−1)/12=833,25, стандартное отклонение ≈28,9.
Проверка: полный перебор всех рассадок для n=3, …, 6 даёт точно равномерное распределение R и вероятность 1/2 для каждой старушки; моделирование 200 000 посадок при n=100 дало среднее 49,50 и частоты потревоженности старушек № 1, № 42 и № 99, равные 0,502, 0,499 и 0,500.
Что не следует из ответа
Вероятность 1/2 для каждой старушки не означает, что старушек тревожат независимо. Иначе R имело бы биномиальное распределение с центром около 49,5 и стандартным отклонением около 5. На самом деле R равномерно от 0 до 99: с одинаковой вероятностью 1/100 не потревожат никого или потревожат всех.
Ответ опирается на то, что каждая старушка выбирает место равновероятно среди свободных, не глядя на билет. Если старушки предпочитают определённые места или иногда садятся на своё, перестановка перестаёт быть равномерной, и ответы меняются.
Это не классическая задача о сумасшедшей старушке, где безумна только первая пассажирка, а остальные садятся на свои места, если те свободны. Там спрашивают о судьбе последнего пассажира, и ответ 1/2 получается из другого рассуждения.
Борис Демешев и участники · probability_dna, задача «Самолёт и сумасшедшие старушки» · Исходное задание и решение · CC BY 4.0. Адаптация: условие переформулировано, решение источника сокращено, добавлены сведение к циклам случайной перестановки, дисперсия и численная проверка.