Условие
В самолёте 100 мест, все билеты проданы. Первой в очереди на посадку стоит Сумасшедшая Старушка: она врывается в самолёт и, не глядя на билет, садится на случайно выбранное место. Каждый следующий пассажир садится на своё место, если оно свободно, а если оно занято — на случайно выбранное свободное место.
а) Какова вероятность того, что последний пассажир сядет на своё место?
б) Чему примерно равно среднее количество пассажиров, севших на свои места?
Решение источника
Источник даёт два рассуждения для пункта а).
Первое: проследим цепочку пересаживаний, которую запускает Старушка. В этой цепочке Старушка (точнее, её место) и последний пассажир (его место) равноправны, поэтому каждое из двух мест оказывается занятым раньше другого с одинаковой вероятностью. Значит, ответ 1/2.
Второе — индукция. Для двух пассажиров вероятность равна 1/2. Если мест n, то Старушка либо садится на своё место (тогда все, включая последнего, сядут на свои), либо на место последнего (тогда он точно не сядет на своё), либо на место какого-то промежуточного пассажира. В последнем случае, когда очередь дойдёт до этого пассажира, он сам превращается в «сумасшедшую старушку» для задачи меньшего размера, где ответ по предположению индукции равен 1/2. По симметрии первых двух случаев ответ 1/2 сохраняется.
Пункт б) в источнике не разобран.
Редакционное объяснение
Ключевое наблюдение для пункта а). Каждый, кто вынужден выбирать место наугад, выбирает его среди свободных, а место Старушки (№ 1) и место последнего пассажира (№ 100) остаются свободными до тех пор, пока кто-то не займёт одно из них. Как только занято место № 1, все оставшиеся пассажиры садятся на свои места; как только занято место № 100, последний пассажир обречён. В каждый момент случайного выбора эти два места симметричны, поэтому P=1/2 при любом числе мест n≥2.
Пункт б). Пассажир № k (k≥2) не попадает на своё место только тогда, когда его место уже занято к моменту его прихода. К этому моменту заняты все места 2, …, k−1 и ровно одно место из множества {1, k, k+1, …, n}: цепочка пересаживаний продолжается, только пока случайный выбор попадает на места пассажиров 2, …, k−1, а первое же попадание в это множество её прерывает до прихода k-го. Для случайных выборов все n−k+2 мест множества равноправны, поэтому занятым оказывается любое из них с одинаковой вероятностью. Значит,
P(пассажир k не на своём месте)=1/(n−k+2), k=2, …, n.
Старушка сама оказывается на своём месте с вероятностью 1/n. По линейности ожидания среднее число пассажиров на своих местах равно
1/n+Σ(1−1/(n−k+2))=1/n+(n−1)−(1/2+1/3+…+1/n)=n−Hn+1/n,
где Hn=1+1/2+…+1/n — гармоническое число. При n=100: H100≈5,1874, поэтому среднее ≈94,82. Приближённо это n−ln n−0,577: «пострадавших» в среднем около ln n, то есть очень мало.
Для последнего пассажира (k=n) формула даёт 1/2 — это ответ пункта а).
Проверка: точный перебор всех вариантов при n=2, …, 6 дал среднее 1, 3/2, 13/6, 35/12, 223/60 — ровно n−Hn+1/n — и вероятность 1/2 для последнего пассажира; моделирование 4000 посадок при n=100 дало среднее 94,80.
Что не следует из ответа
Ответ 1/2 не означает, что каждый пассажир сгоняется с вероятностью 1/2. Чем ближе пассажир к началу очереди, тем меньше шанс, что его место уже занято: второй пассажир согнан лишь с вероятностью 1/n, а 1/2 получается только для последнего.
Аргумент симметрии работает, потому что случайный выбор делается равновероятно среди свободных мест. Если согнанные пассажиры предпочитают, например, места у окна, ответ меняется.
Это не та же задача, что о 99 сумасшедших старушках, где безумны почти все пассажиры: там цепочку запускает последний пассажир, и вопросы о распределении числа потревоженных решаются через циклы случайной перестановки.
Борис Демешев и участники · probability_dna, задача «Сумасшедшая Старушка» · Исходное задание и решение · CC BY 4.0. Адаптация: история задачи и иллюстрация опущены, решение источника для пункта а) пересказано, добавлены решение пункта б) (в источнике отсутствует) и проверка перебором и моделированием.