Разборчивая невеста
«Задачу о секретаре» сформулировал ещё в 1960 году Мартин Гарднер. В русской литературе её обычно называют «Задачей о разборчивой невесте» (видмо, по одноимённой басне Крылова). Суть задачи в том, что к невесте приходят по одному N женихов. Она общается с каждым не более одного раза и может сравнить его с любым из предыдущих. Если она кого-то выбирает, то процесс останавливается. Если она кому-то отказывает, то вернуться к нему уже не сможет, женихи, типа, гордые. Цель - с максимальной вероятностью выбрать самого лучшего из всех женихов.
Для двух женихов, понятно, алгоритм будет «брать первого». Вероятность 50%, что он же будет и лучшим. Для трех - хитрее. Если действовать по принципу «брать первого» («второго» или «третьего» - не принципиально), то вероятность уменьшится до 33%. Но можно усовершенствовать процесс таким образом: первому отказать сразу, второго брать только если он окажется лучше первого, иначе брать третьего. Если пронумеровать женихов по «лучшести» от 1 до 3, то при таком подходе невеста выберет лучшего (№3) жениха в трёх случаях: 1-3-2, 2-3-1 и 2-1-3 из шести возможных. То есть снова с пятидсятипроцентной вероятностью!
Несложное доказательство показывает, что для любого N, действуя подобным образом, можно выбрать лучшего жениха с вероятностью не хуже ~37%, что, согласитесь, не так уж плохо. Нужно лишь отказать первым N/e (e - основание натуральных логарифмов = 2.71828…) и дальше ждать лучшего чем они. Вероятность того, что он и будет самым лучшим, будет стремиться к 1/e.
У крыловской невесты, однако, была серьёзная проблема. Она не знала заранее чему равно число женихов N, не смогла применить наш алгоритм и, в итоге:
За первого, кто к ней присватался, пошла:
И рад ж была,
Что вышла за калеку
Задачу с заранее неизвестным N смогли решить только в 1984 году и, совершенно неожиданно, результат оказался таким же!!! При гораздо более слабом начальном условии принцесса всё равно смогла бы выбрать лучшего жениха с вероятностью 1/e (правда, для этого ей бы пришлось научиться брать интегралы :)). Если стоит цель выбрать не самого лучшего, а одного из двух лучших, то результат станет больше 50%.
Дальнейшим обобщением задачи о разборчивой невесте занимался в докторской диссертации покойный Б.А.Березовский. В частности, потом он применил этот же метод для построения модели формирования инвестиционного портфеля - какие акции надо покупать, если известна только часть информации.
На задачу я наткнулся после того как все праздники читал роман «Большая пайка» Юлия Дубова, бывшего зама Березовского. По этому роману сняли фильм «Олигарх» с Машковым в главной роли. Фильм слабенький, а вот роман - о-го-го. Рекомендую.
Запись опубликована gava.chgk.info. You can comment here or there.