Я вам уже рассказывал про задачи о выборе: как Сильвер был избран квотермейстером и как сам Сильвер выбирал хирурга. Напомню суть первой из этих задач, известной как задача о секретаре или о "разборчивой невесте".
Есть несколько претендентов, о которых почти ничего не известно, кроме их количества. Их качество случайно и имеет какое-то распределение: только распределение мы и знаем. Пусть оно равномерное. Выбирающий может только сравнивать претендента с другими, уже проходившими собеседование. Претенденту можно дать место (все остальные уходят и про них ничего неизвестно) или отказать, и тогда он уйдет и вернуть его нельзя. Надо как можно более высокую вероятность выбрать самого лучшего.
Во второй задаче выбирающий узнает числовую оценку качества претендента и гонится не за шансом взять самого-самого, а стремится взять получше в среднем.
Понимаете разницу? В любом случае есть риск нанять дрянного специалиста. Даже и самого плохого: если не повезет. Но вероятностная задача всегда предполагает многократность попыток.
Первый подход, максимизация вероятности взять самого лучшего, означает примерно вот что: Сильвер, который действует по оптимальному правилу, будет чаще выбирать самого лучшего, чем остальные, кто нанимает пиратов. Если он не смог взять лучшего, ему все равно уже, кто будет, он в этот раз проиграл.
Второй подход означает, что среднее качество нанятых Сильвером будет лучше, чем у других. Он может вообще ни разу не нанять лучшего, но будет брать вполне приличных. Это как сорвать суперприз или иметь небольшой, но стабильный выигрыш. Разные тактики.
Когда Флинт выбрал Сильвера квортермастером, он только сравнивал претендентов между собой. Все, что он мог — это пропустить несколько претендентов, набирая статистику, а потом взять первого же, который лучше всех уже опрошенных. Вопрос только в том, сколько надо пропустить, и интересна оценка вероятности взять лучшего, например, из ста претендентов. Выбор наугад дает малый шанс, правда? А насколько больше шанс при оптимальном выборе? Спойлер: намного больше!
Важно, что Флинт не оценивал качество претендента, а только сравнивал "лучше-хуже". Что довольно типично: адекватно оценить качество квортермастера (жениха, ученого, актера, секретаря, шахматиста) одним числом вообще очень трудно.
Ответ к задаче таков: надо пропускать около 1/e доли претендентов (около 37%), что дает асимптотически (при большом числе претендентов) шанс взять лучшего 1/е≈0.368. Примерно одна треть, даже побольше.
Важно понимать, что равномерное распределение означает, что претендентов с качеством между 0.15 и 0.16 столько же, сколько между 0.92 и 0.93: вероятность интервала зависит только от его длины, а не от положения. Если взять много человек, то возможность, что все хуже 0.5, есть, но мала; скорее всего, будут и более достойные.
А теперь рассмотрим, что нам может дать информация о качестве.
Как-то после жаркого дела Флинт лишился стрелка, и пришлось нанимать нового. Флинт настаивал на том, что взять нужно непременно лучшего стрелка, ну или постараться. Он хотел применить ту же технику, что подсказал ему Сильвер: опросить около трети претендентов и взять потом того, кто лучше всех уже опрошенных.
Сильвер в целом не возражал, но отметил только, что стрелку легко можно дать численную оценку. Например, с какого расстояния он может сбить бутылку или сколько бутылок он собьет. Это позволяет, конечно, объективно сравнить стрелков, но дает кое-что еще: числовую оценку меткости стрелка, и эту информацию надо разумно использовать. Более того, Сильвер бился об заклад с каждым, кто пожелает, дублон против дублона, что выберет самого лучшего стрелка из присутствующих. Именно по таким правилам: Сильвер оценивает стрелка и либо принимает, либо отказывает.
Итак, задача: дано N претендентов, их качество случайно и распределено равномерно на [0,1]. Испытание дает оценку этого качества и на основе этой оценки надо претендента взять или отказать. В последнем случае он уходит и вернуть его нельзя. Нужно максимизировать вероятность взять самого лучшего стрелка.
Нам нужны пороги: значения качества, ниже которых мы претендента с данным номером не берем. Надо выбрать пороги оптимально.
Беседуя со стрелком, который пока лучший, вы должны оценить шансы, что еще более хорошего впереди нет. Для равномерного распределения это качество текущего в степени числа оставшихся.
Дело в том, что для равномерного распределения на [0,1] вероятность, что случайная величина меньше x, равна x. В случае независимых событий, вероятность, что наступят оба, получается перемножением вероятностей. Здесь удобно, что качество приведено к [0,1] и оно же равно вероятности, что другой будет хуже.
Если вы решаете отказать, то далее вы будете действовать по той же схеме. Придется пропускать всех, кто хуже нынешнего, и брать первого же, кто лучше. При этом надо надеяться, что все остальные хуже, чем взятый.
Получается много вариантов: следующий лучше нынешнего, все остальные хуже него; следующий хуже нынешнего, потом лучше, все остальные хуже него; и так далее. Записывается вероятность всего этого в таком виде:
В формуле сумма отражает все варианты принятия претендентов (j — это номер принятого, а i — номер рассматриваемого в данный момент, его меткость x); первый множитель есть вероятность, что все между нынешним и принятым хуже нынешнего, под интегралом вероятность, что все после принятого хуже него, интеграл перебирает все возможные качества принятого претендента: все N-j претендентов после должны быть хуже, иначе проиграем.
Мы решаем не продолжать, если вероятность, что нынешний, наилучший пока что, вообще самый лучший, равна (или больше) вероятности успеха при продолжении. Получаем неравенство
Теперь обозначим k=N-j+1 и получим
Но суммировать без разницы в какую сторону, поэтому перепишем в порядке возрастания номеров и заменим неравенство на равенство:
Корень этого уравнения дает порог: минимальное качество, при котором претендента номер i c меткостью x надо брать.
Например, если он предпоследний, то в сумме одно слагаемое, k=1, и получаем уравнение 1/x-1=1, откуда x=0.5. Логично, если остался один претендент, то именно 0.5 и будет порогом: раз мы добрались до конца, то все остальные оказались хуже, а шанс, что последний лучше 0.5, равна как раз 0.5. Так что если текущий лучше, чем 0.5, берем его.
За два претендента до конца очереди имеем (после упрощений) уравнение 5x²-2x-1=0, откуда x=0.689. И так далее. Чем дальше от конца, тем выше требования.
При этом вероятность взять лучшего при небольшом числе претендентов довольно большая и убывает, стремясь на бесконечности к примерно 0.58. Иными словами, оптимальная стратегия дает вероятность выбрать самого лучшего близкую к 0.58 при большом числе претендентов. При малом и того больше. Поверить трудно, конечно. Классическая задача дает 1/е, что примерно 0.37, то есть владение информацией дает не так и мало.
Давайте возьмем троих и посмотрим на решения двух изученных задач на максимальную вероятность взять лучшего. Итак, есть три претендента, их меткости распределены равномерно. Первая задача: надо взять лучшего с наибольшей вероятностью, можно только сравнивать стрелков между собой. Стратегия: пропускаем первого, берем второго, если он лучше первого. Если лучший был первым, проиграем, если вторым — выиграем, если третьим — выиграем только в том случае, если второй хуже первого (шанс 0.5). В итоге имеем 1/3+0.5/3=0.5.
Вторая задача, рассмотренная здесь. Мы знаем меткость стрелка и на основе нее делаем выбор: брать или отказать. Стратегия пороговая: берем того, кто лучше порога для данного претендента. Порог для первого 0.69, для второго 0.5, третьего берем любого. Вероятность считается немного муторно, но считается: 0.614.
По поводу пари Сильвера. Он спорит на равных, что возьмет лучшего. Независимо от числа претендентов, Сильвер имеет шанс выиграть выше 0.5; поэтому игра за него. Кто бы сомневался!
Путеводитель по каналу и оглавление рубрики
Для дальнейшего чтения:
- Березовский А.Б. ( тот самый: был когда-то полезным человеком... ) Задача наилучшего выбора. М.: Наука, 1984.
- Гусейн-Заде С.М. Разборчивая невеста. 2003.
- Мазалов В.В. Моменты остановки и управляемые случайные блуждания. 1992.
- Ивашко А.А. Дискретные задачи оптимальной остановки. 2017.
- Роббинс Г. Теория оптимальных правил остановки. 1977.