§6. Наилучший выбор: сколько женихов пропустить

Финал главы — сказка, но с самой настоящей математикой внутри.

В некотором царстве жила-была царевна. Приехали к ней свататься добры молодцы, один другого лучше. Заходили женихи в палаты по очереди да кланялись. Беда в том, что добры молодцы были больно обидчивы: не дала царевна согласия сразу — садились на коня и уезжали восвояси, назад не вернёшь. А заранее о женихах ничего не известно, только сколько их всего приехало. Как царевне выбрать самого достойного?

По-дворовому та же история — съём хаты: смотришь варианты по одному, отказался — её тут же забрали, и сравнивать можно только с тем, что уже видел.

Модель

Пусть женихов $n$, и они встают в очередь в случайном порядке — все $n!$ перестановок равновероятны. Царевна видит только, кто лучше, а кто хуже среди уже прошедших. Цель — остановиться именно на самом лучшем.

Стратегия «осмотрись, потом бери»

Взять первого попавшегося — шанс всего $1/n$. Умнее так: пропустить первых $m$ женихов (просто посмотреть, какие вообще бывают), а потом взять первого, кто окажется лучше всех предыдущих. Если такой не найдётся — достанется последний. Конечно, можно упустить лучшего, если он был среди первых $m$. Вопрос — какое $m$ выбрать.

Считаем шанс

Пусть $A_k$ — событие «остановились на $k$-м женихе» ($k = m+1, \dots, n$). Это значит: все с номерами от $m+1$ до $k-1$ оказались хуже лучшего из первых $m$, а $k$-й — лучше всех предыдущих. Посчитав, куда может встать каждая следующая «точка» в порядке, Лагутин получает

Пусть $B$ — «выбрали самого лучшего». Остановка на $k$-м даёт лучшего, если $k$-й ещё и абсолютный лидер, тогда $\mathbf{P}(B \cap A_k) = \dfrac{m}{n(k-1)}$. Складываем по всем $k$ (формула полной вероятности):

По кирпичикам:

• $\tfrac{m}{n}$ — растёт с $m$: чем больше осмотрелся, тем выше планка, тем меньше шанс схватить середнячка.
• $\sum_{k=m}^{n-1} \tfrac1k$ — падает с $m$: чем больше пропустил, тем выше риск, что лучший был среди пропущенных.
• Два эффекта тянут в разные стороны, значит есть золотая середина $m^*$.

Ответ: пропусти примерно $n/e$

Таблица оптимальных $m^*$ и шансов $p^*_n$:

Шанс $p^*_n$ убывает с ростом $n$, но не к нулю, а к $1/e \approx 0{,}368$. Почему: сумму можно зажать интегралом, $\sum_{k=m}^{n-1}\tfrac1k \approx \ln\tfrac{n}{m}$, и тогда $\mathbf{P}_m(B) \approx -\tfrac{m}{n}\ln\tfrac{m}{n}$. Функция $f(x) = -x\ln x$ достигает максимума в точке $x^* = 1/e$, и сам максимум равен $1/e$.

Вывод: пропусти примерно $n/e \approx 37\%$ женихов, потом бери первого, кто лучше всех увиденных. Даже если женихов тысяча, шанс выбрать самого лучшего — больше трети. Без всякой информации о них заранее!

Покрути виджет: двигай $n$ и $m$, смотри, где у кривой вершина, и сравни формулу с симуляцией.

Та же стратегия в коде:

Если знаешь больше

Отдельно Лагутин замечает: если про женихов известно больше — например, их «качества» это выборка из равномерного закона на $[0,1]$, и царевна видит сами числа, а не только порядок, — то есть стратегия с шансом не меньше 0,58. Чем больше информации, тем точнее выбор. Но даже вслепую правило $1/e$ работает железно.

Проверь себя