Задача о разборчивой невесте

Невеста-девушка смышляла жениха:

Тут нет еще греха,

Да вот что грех: она была спесива.

Сыщи ей жениха, чтоб был хорош, умён,

И в лентах, и в чести, и молод был бы он

(Красавица была немножко прихотлива)...

И.А. Крылов. "Разборчивая невеста".

Эта задача была поставлена М.Гарднером (1960 г.). Первое решение получено Е.Б. Дынкиным (1963 г.). Более общее решение было найдено С.М. Гусейн-Заде (1966 г.). Решение Гусейна-Заде задачи в её простой первоначальной формулировке было опубликовано в издательстве "Математическое просвещение", но его способ рассуждения, при всей элементарности используемого аппарата, отнюдь не является простым.

Из обобщения этой полушуточной задачи Гусейном-Заде вырос целый новый раздел математики — теория оптимальной остановки случайных процессов. Развитие этой теории, в частности, связано с именем известного бизнесмена и политического деятеля Б.А. Березовского, защитившего свою докторскую диссертацию по теме дальнейшего обобщения задачи о разборчивой невесте.

Мы разберём решение задачи в её первоначальной формулировке, данной Гарднером. Идею её решения можно найти в англоязычной Википедии.

Формулировка задачи:

В некотором царстве, в некотором государстве пришло время невесте выбирать себе жениха. В назначенный день явились N царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса может сказать, познакомившись с ними, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?

Пусть принцесса отклонит первых r – 1 претендентов. Теперь она будет выбирать первого из последующих претендентов, который будет лучше, чем лучший среди этих r – 1 отклонённых.

Наша задача вычислить оптимальное соотношение r / N, которое необходимо для выбора наилучшего кандидата.

Очевидно, что если самый лучший кандидат находится среди первых r – 1 претендентов, то принцесса упустит свой шанс совершить наилучший выбор. Поэтому это отношение не должно быть слишком большим и уж точно не равно 1 (вероятность совершить при этом наилучший выбор равна 1 / N).

С другой стороны, оно не может быть и слишком маленьким, потому что тогда жених будет определён на основе очень малой выборки.

Пусть событие Аᵢ — "выбран кандидат i",

событие Вᵢ — "кандидат i является лучшим".

Тогда для произвольного отсечения r – 1 претендентов вероятность Р(r) найти лучшего кандидата равна сумме вероятностей независимых событий:

Здесь вероятность того, что i-й кандидат является лучшим, для любого i равна
1 / N, её можно вынести в записанной сумме за скобку.

Сумма первых r – 1 слагаемых в сумме условных вероятностей Р(Aᵢ│Bᵢ) равна нулю, поскольку соответствующих этим слагаемым претендентов невеста по условию задачи отклонила.

Для оставшихся слагаемых (от i = r до N) при вычислении этой вероятности мы предполагаем, что лучший из i – 1 кандидатов находится среди r – 1 первоначально отклонённых:

Таким образом,

В этой сумме если i-й принц является лучшим кандидатом, то он выбирается тогда и только тогда, когда лучший кандидат из первых i – 1 претендентов входит в число r – 1 отклонённых претендентов.

Данная сумма не определена для r = 1, но в этом случае единственно возможной стратегией является выбор первого кандидата,

поэтому Р(1) = 1 / N.

Пусть теперь N → ∞. Перейдём от дискретной величины к непрерывной. Обозначим

Тогда вероятность можно аппроксимировать интегралом

С помощью производной легко найти точку максимума этой функции:

х = 1 / e. Таким образом, оптимальную остановку невесте нужно сделать, просмотрев 1 / e ≈ 37% от общего числа N претендентов: отклонить первых
N / e кандидатов, пришедших просить её руки сердце, а затем остановиться на первом кандидате, который окажется лучше всех предыдущих. Оптимальная вероятность выигрыша при этом будет равна

1 / e ≈ 0,37.

Указанная оптимальная стратегия практически не зависит от количества претендентов N.