После гибели квортермастера капитану Флинту нужно было выбрать нового. Из ста претендентов он мог выбрать одного, но выбор осложнялся гордыней пиратов — ни один не хотел ждать и не стерпел бы отказа: отказать и потом передумать было невозможно. Брать первого же было рискованно — необходимо поговорить с несколькими и потом выбрать. Сколько претендентов следовало проверить Флинту? И какого взять? Каким по счету пошел Сильвер, который знал, что он заведомо лучше всех? Известно, что Флинт выбрал его, но как Сильвер это устроил?
Задачка известна как "задача о секретаре" и "задача о разборчивой невесте". Здесь надо многое уточнить: критерий оптимальности, например. Мы считаем, что Флинт стремится максимизировать вероятность выбрать лучшего претендента. Еще нужно договориться, как оценивать претендентов. У нас для каждого претендента можно сказать, лучше он или хуже тех, с которыми Флинт уже побеседовал (они уже потеряны для него). Поговорив со всеми, Флинт узнает, кто был лучшим; но будет поздно.
Распределение претндентов равномерное: вероятность, что лучший идет под номером i, от i не зависит.
Есть вариант задачи, точное решение которого пока неизвестно — о ней в другой раз.
Вообще, небольшие вариации условий сильно меняют задачу. Если известна численная оценка и она ограничена (а если не ограничена, то распределение не может быть равномерным), то вероятность найти кого-то лучше сильно зависит от качества этого претендента.
Если я имею удовольствие впервые знакомить Вас, мой читатель, с этой замечательной задачкой, то предлагаю прикинуть навскидку, какова вероятность выбрать самого лучшего претендента, и сколько нужно пропустить для набора статистики.
Решение задачи таково: нужно пропустить не менее N/e (N — число претендентов, е — основание натурального логарифма) претендентов, отказывая всем и накапливая статистику; для N=100 это 37 человек. Далее берем того, который лучше всех, с кем уже говорили.
При этом вероятность взять лучшего не такая маленькая: она равна 1/e≈0.37.
Говорят, что женщины инстинктивно (в среднем, конечно) следуют похожей схеме: в юности "набирают статистику", потом внезапно начинают всерьез искать спутника жизни.
Приведем нестрогие рассуждения, приводящие к правильному ответу. Итак, Флинт не имеет численной оценки качества претендентов, но может сравнивать претендентов между собой.
Можно считать, что качество есть число от нуля до единицы, но Флинту это число неизвестно. Он может перебрать M претендентов, чтобы определиться, а потом взять первого же, который лучше всех из начальной группы. Проблема сводится к выбору M, доставляющего максимум вероятности выбрать лучшего.
Вероятность, что равномерная случайная величина на отрезке [0,1] меньше числа x, равна x — это функция распределения равномерного распределения. Вероятность, что все из набора k таких величин (независимых) меньше x, равна x^k, поскольку есть одновременное наступление k независимых событий, вероятность каждого x.
Лучший претендент может иметь любой номер i. Если этот номер меньше M или равен M, то вероятность выбрать его равна нулю. Пусть i>M. Тогда лучший претендент будет выбран, если каждый из множества от M+1 до i-1 уступает кому-то из начальной группы; иными словами, если максимум из них меньше максимума начальной группы.
Вероятность, что максимум начальной группы попал в интервал [x,x+dx], равна d(x^M)=Mx^{M-1}dx. Вероятность, что он попал туда, а максимум по номерам от M+1 до i-1 меньше, равна произведению: x^{i-M-1}d(x^M). Полная вероятность — это интеграл:
Можно трактовать этот интеграл как среднюю вероятность по распределению максимума.
Осталось сложить эти вероятности по всем позициям i от M+1 до N, умножая на вероятности застать лучшего в этих позициях 1/N:
и найти ее максимум по M.
Легко видеть, что при увеличении M на единицу в сумме станет на одно слагаемое меньше: исчезнет слагаемое со знаменателем M, которое равно 1. Остальные слагаемые в обеих суммах соответствуют друг другу, и при вычитании из суммы для M+1 суммы для M получим
Две суммы выше являются частичными суммами гармонического ряда, который приближается кривой ln(x). Тогда левую часть можно приблизить так:
Нам нужна точка, в которой эта величина меняет знак, а она равна нулю при M=(N-1)/e. При этом
Получается, что при большом числе претендентов N вероятность выбрать лучшего довольно велика: близка к 1/e, что намного больше 1/N (вероятность угадать с одного раза). Сильверу достаточно было идти сразу после начальной группы претендентов (нет сомнений, что Флинт был в курсе оптимальной стратегии!)
Стратегия работает и при маленьких N. Например, при N=3 у Флинта есть три стратегии: взять первого; пропустить первого и потом взять второго, ели он лучше, или третьего, так как кого-то же взять надо; пропустить двоих и взять третьего. В первом и последнем случае вероятность взять лучшего равна 1/3. Во втором же есть три варианта: если лучший был первым, вероятность взять его равна нулю; если вторым, то единице; если третьим, то 0.5: ведь это вероятность что второй хуже первого, а без дополнительной информации шансы равны. В итоге имеем вероятность
0*1/3+1*1/3+0.5*1/3=1/2.
При этом (N-1)/e=2/e<1, так что пропустить надо не менее этой величины, то есть ровно одного претендента. Вероятность получилась не 1/е (это асимптотика), а 1/2, но это близко.