Лента на n принцесс: самый короткий кусок в среднем 1/n², второй по малости — (1/n)(1/n+1/(n−1))

Условие

Парчовую ленту длиной 1 км разрезают в n−1 месте, выбранном случайно, независимо и равномерно, чтобы поделить её между n принцессами. Скромнице Василисе достаётся самый короткий кусок.

а) Какова ожидаемая длина Василисиного куска?

б) Какова ожидаемая длина самого короткого куска, не считая Василисиного?

Решение источника

Источник ищет вероятность того, что минимальная длина больше d, через дискретную модель: большая колода из N карт, среди которых n−1 отмеченная, и нужно, чтобы между отмеченными картами было не меньше dN карт. После вытягивания отмеченной карты следующие dN карт можно брать с конца колоды — это не меняет случайности порядка, зато упрощает подсчёт: нужно, чтобы (n−1)dN неотмеченных карт оказались в конце колоды и dN неотмеченных — в начале.

Для k-го по счёту минимального куска источник приводит формулу (1/n)·(1/n+…+1/k), а для второго по малости куска — идею доказательства: E(X)+(1−n·E(X))/(n−1)²=(1/n)·(1/n+1/(n−1)), где X — длина самого короткого куска.

Редакционное объяснение

а) Карточное рассуждение источника означает, что

P(X>t)=(1−nt)ⁿ⁻¹ при 0≤t≤1/n.

Непрерывная версия того же рассуждения: упорядоченные точки разреза u₁<…<u_n−1 равномерно распределены в соответствующем симплексе. Условие «все куски длиннее t» после сдвига v_i=u_i−i·t превращается в условие 0<v₁<…<v_n−1<1−nt, то есть в такой же симплекс для ленты длины 1−nt. Его объём в (1−nt)ⁿ⁻¹ раз меньше исходного. Интегрируя хвост,

E(X)=∫₀^1/n (1−nt)ⁿ⁻¹ dt=1/n² км.

При n=10 это 10 м, хотя средний кусок — 100 м.

б) Вычтем X из каждого куска. Кусок Василисы обнулится, а превышения остальных n−1 кусков в сумме дают 1−nX и при известном X ведут себя как равномерное разрезание ленты длины 1−nX на n−1 частей. Второй по малости кусок равен X плюс наименьшее из этих превышений, поэтому, по пункту а),

E(второго)=E(X)+E(1−nX)/(n−1)²=1/n²+(1−1/n)/(n−1)²=1/n²+1/(n(n−1))=(1/n)·(1/n+1/(n−1)) км.

Это и есть тождество из решения источника. При n=10 получаем 19/900 км≈21,1 м.

Исправление общей формулы. Продолжая то же рассуждение, получаем для k-го по малости куска

E(k-го по малости)=(1/n)·(1/n+1/(n−1)+…+1/(n−k+1)).

Формула источника (1/n)·(1/n+…+1/k) верна для k-го по величине куска, считая от самого длинного. Например, при k=1 она даёт (1/n)·(1+1/2+…+1/n) — среднюю длину самого длинного куска, а не самого короткого. При n=3 средние длины кусков по возрастанию равны 1/9, 5/18 и 11/18, а формула источника при k=1 даёт 11/18. Сумма средних длин всех n кусков, как и должно быть, равна 1 км.

Проверка: точные дроби для n=2, 3, 5, 10, 50 и моделирование 300 000 разрезаний при n=3, 5 и 10 совпали со всеми средними упорядоченными длинами до третьего-четвёртого знака.

Что не следует из ответа

1/n² — это среднее для самого короткого куска, а не для куска случайной принцессы: случайно выбранный кусок в среднем имеет длину 1/n. Самый короткий кусок в среднем в n раз короче среднего куска.

Ответ требует независимых равномерных разрезов. Если ленту режут «на глаз примерно поровну», распределение кусков совсем другое.

Не следует путать эту задачу с задачей о минимальном расстоянии между случайными точками без учёта концов отрезка: там n точек дают n−1 промежуток, и формула для хвоста другая.

Борис Демешев и участники · probability_dna, задача «Парчовая лента и принцессы» · Исходное задание и решение · CC BY 4.0. Адаптация: решение источника пересказано, вычисления доведены до ответов 1/n² и (1/n)(1/n+1/(n−1)), исправлена общая формула для k-го по малости куска (в источнике она относится к k-му по величине).