Условие
В тарелке, запутавшись, лежат макаронины. Их очень много — n штук. Я по очереди связываю попарно все торчащие концы макаронин, каждый раз выбирая пару свободных концов наугад.
а) Какова примерно вероятность того, что я свяжу все макаронины в одно большое кольцо?
б) Сколько в среднем образуется колец?
в) Каково среднее число колец длиной в одну макаронину?
Решение источника
а) Занумеруем макаронины и выделим у каждой левый и правый конец. Возьмём правый конец первой макаронины и привяжем к случайному свободному концу. Затем возьмём свободный конец только что присоединённой макаронины и снова привяжем к случайному, и так далее. Одно кольцо получится с вероятностью
(2n−2)/(2n−1) · (2n−4)/(2n−3) · … · 2/3 · 1.
б) Если en — среднее число колец при n макаронинах, то после первого связывания задача сводится к меньшему числу макаронин; важно лишь, образовалось ли кольцо при первом связывании: en=en−1+1/(2n−1).
в) Число коротких колец раскладывается в сумму X=Z1+…+Zn, где Zi — индикатор того, что i-я макаронина завязана сама с собой. Её левый конец должен быть привязан именно к её правому, вероятность этого 1/(2n−1). Значит, E(X)=n/(2n−1).
Редакционное объяснение
Модель: все (2n−1)·(2n−3)·…·3·1 способов разбить 2n концов на пары равновероятны. Последовательная процедура источника даёт то же распределение, потому что на каждом шаге свободный конец привязывается к равновероятно выбранному из оставшихся.
а) Пусть в руке свободный конец текущей цепочки, а всего осталось m «кусков» (цепочка тоже считается куском). Свободных концов, кроме того, что в руке, 2m−1, и ровно один из них — второй конец той же цепочки. Значит, кольцо преждевременно не замкнётся с вероятностью (2m−2)/(2m−1). Перемножая по m=n, n−1, …, 2, получаем произведение источника, которое равно 4n−1·((n−1)!)²/(2n−1)!. По формуле Стирлинга (или Валлиса)
P(одно кольцо)≈√π/(2√n)=√(π/(4n)).
Например, при n=100 точное значение 0,08873, приближение 0,08862; при n=1000 — около 0,028.
б) Первое связывание с вероятностью 1/(2n−1) замыкает макаронину в кольцо, а иначе склеивает две макаронины в одну длинную. В обоих случаях остаётся такая же задача с n−1 куском, поэтому рекуррентное соотношение источника верно, и при e1=1
en=1+1/3+1/5+…+1/(2n−1)≈½·ln n+ln 2+γ/2≈½·ln n+0,98,
где γ≈0,5772 — постоянная Эйлера. Например, e100≈3,28, e1000≈4,44, e10000≈5,59: число колец растёт очень медленно.
в) E(X)=n/(2n−1)→1/2. Индикаторы зависимы, но для ожидания суммы это не важно.
Проверка: полный перебор всех разбиений на пары при n=1, …, 6 подтверждает все три формулы (например, при n=2 из трёх разбиений одно кольцо дают два, среднее число колец 4/3, среднее число коротких колец 2/3). Моделирование 20 000 опытов при n=100 дало 0,0896, 3,28 и 0,508.
Что не следует из ответа
Ответы верны, только если концы связываются наугад. Если связывать физически близкие концы, вероятности будут другими.
Вероятность одного кольца стремится к нулю, но медленно, как 1/√n: даже при тысяче макаронин она около 2,8%.
Величина ½·ln n+0,98 — это среднее число колец. В конкретном опыте колец может оказаться и одно, и заметно больше среднего.
Борис Демешев и участники · probability_dna, задача «Задача о макаронинах» · Исходное задание и решение · CC BY 4.0. Адаптация: решение источника сохранено, добавлены приближённая вероятность одного кольца (в источнике только произведение), сумма для среднего числа колец с асимптотикой и проверка перебором и моделированием.