Я вам уже рассказывал про задачи о выборе: как Сильвер был избран квотермейстером и как сам Сильвер выбирал хирурга и, позже, стрелка. Давайте приведем в систему эти и другие задачи, известные как задачи о секретаре или "разборчивая невеста".
Есть несколько претендентов, о которых почти ничего не известно. Они обладают числовым значением качества, которое случайно и имеет какое-то распределение; его мы знаем.
Количество претендентов также известно. Потестировав претендента, можно его взять, потеряв всех еще нетестированных, либо отказать, потеряв самого претендента.
Вопрос в оптимальной остановке: имея вот такого, брать или не брать? Возьмешь слишком рано — рискуешь потерять более хорошего. Слишком поздно — рискуешь пропустить всех годных.
Разные варианты задачи возникают из-за, во-первых, наличия или отсутствия информации о качестве, а во-вторых, из-за разных критериев.
Тестирование претендента может дать нам значение его качества. Тогда известен и относительный ранг, то есть положение среди других протестированных: первый (лучший), второй, третий, ..., последний. В конце, перепробовав всех, мы будем знать абсолютные ранги... но это уже бесполезно.
А может быть так, что известен только текущий ранг, то есть мы можем сравнить претендентов на уровне "лучше-хуже" и расставить их по рангу, но оценить качество каждого числом не способны. Первый случай — игра с полной информацией, второй — с неполной.
Критерии тоже могут быть разные: можно стремиться взять самого лучшего (игра на максимум); или максимум качества в среднем (игра на среднее); а можно стремиться к минимальному среднему рангу (игра на средний ранг).
В первом случае надо почаще брать лучшего, а если не получилось, то уже без разницы, кто попался. Во втором можно лучшего брать не так часто, но и совсем отстойных следует избегать. В третьем случае тоже, но есть отличие: если уже был претендент с качеством 0.91, и его не взяли, а позже пришел 0.9, то для среднего это почти одно и то же; а вот ранг у второго никак не меньше двух, а то и трех. Возможно, следует рисковать и отказывать и ему, надеясь, что лучший еще впереди.
Задача с неполной информацией и игрой на максимум — это задача о секретаре (1960 г., если не считать Сильвера). С полной информацией — тоже разобрана. 1966 г., см. Мозер.
С полной информацией и игрой на среднее стоит особняком, она проще других. Ее обычно усложняют, дисконтом, например. Это задача о продаже дома. 1956 г.
С неполной — такую задачу не встречал, надо подумать. Мне кажется, что это то же, что и минимизировать средний ранг. Но это не точно.
Остались задачи на средний ранг, с неполной информацией и с полной. Первая сложнее всех вышеперечисленных, но решена (1964), о чем далее. Вторая, задача Роббинса (1990), пока не решена никем. Во всяком случае, не была решена в обозримом прошлом и я ничего про это не слышал.
Во всех задачах обычно интересна асимптотическая оценка: при большом числе претендентов. В классической задаче о секретаре вероятность взять лучшего стремится к 1/е, и надо пропускать N/e претендентов, набирая статистику. Полная информация дает возможность повысить вероятность на 58%: до 0.58.
Это же удивительно, разве нет? У вас тысяча человек, вы можете поговорить с каждым лишь один раз. И вероятность взять лучшего более 50%, то есть в половине всех наймов вы будете брать лучшего из тысячи. Шанс на то, чтобы случайно выбранный был лучшим, стремится к нулю.
Теперь давайте обсудим задачи на средний ранг.
Дон Роббинс*, губернатор Острова, устроил турнир стрелков. Флинт и Сильвер, независимо, должны были постараться выбрать себе на корабль нового стрелка. Флинт знал ранги, то есть место стрелка среди уже стрелявших: лучший он (пока) или второй и т.п. Сильвер же использовал оценку меткости. Оба стремились с минимальному среднему рангу: почаще брать первого (из всех!), но если не выходит первого, то второго, и так далее, в порядке убывания.
К примеру, средний ранг 2 может означать:
- Сильвер всегда берет второго, ну так уж ему везет.
- Сильвер никогда не берет второго, но в половине случаев берет лучшего, а в другой половине — третьего.
- Сильвер берет первого, второго и третьего одинаково часто.
- И много других вариантов.
Однако Сильвер должен брать первого достаточно часто, чтобы компенсировать неудачи в других попытках. Под попыткой подразумевается весь турнир: они каждый месяц проходят. Вероятностную задачу можно решать один раз, но подразумевается повторяемость, иначе вероятность не работает. Про это есть шутка: все, игравшие в русскую рулетку, сообщают, что она безопасна.
При этом средний ранг 2 означает, что он берет первых двух не менее, чем с вероятностью 0.5. Это легко доказать, рассмотрев неравенство
найм третьего надо компенсировать наймом первого (иначе в среднем 2 не получить), стало быть, первый идет не реже, чем все, кроме второго. Прибавим p(2) и получим, что
К чему это я? Среднее в таких задачах бывает лукавым. Среднее интересно в связи с законом больших чисел (среднее по истории стремится к теоретическому среднему), но он имеет свои ограничения. Но в данном случае все хорошо: если среднее 2, то первого и второго будут нанимать достаточно часто! А вот если качество сверху не ограничено, то возможны интересные варианты)) Впрочем, это уже тема для диссертации, а не заметки на Дзене.
Задача, которую решал Флинт, сложна, но решена. Асимптотическое значение среднего ранга
То есть, Флинт в среднем берет следующего за бронзовым медалистом. Иногда медалистов, иногда нет, но "поровну". Может быть, я расскажу о стратегии в другой раз. Или читайте (Chow et al , 1964). Кстати, Роббинс соавтор этой статьи.
Интересно, что полная информация дает в задачах на максимум добавку в 58%: с 1/е до 0.58 (поделите и получите 1.58 примерно). Если предположить, что в задаче на средний ранг полная информация снизит (улучшит) результат тоже на 1.58 (с 3.8695), то получим 2.44. Точное решение задачи неизвестно, но оценки есть, так вот: они лучше, чем это значение. Иными словами, выжать можно больше. И это реально удивительно.
Хотя... взять самого лучшего трудно, владение информацией дает кое-что, но меньше, чем если надо брать получше в среднем.
Оценки сверху были получены разными авторами. Лучшая 2.3267: это значит, что точное решение еще меньше. Чуть проще получить оценку 2.333. Оценка снизу тоже есть: 1.908. Сам Роббинс считал, что оптимум равен двум и я тоже так думаю.
Обзор того, то известно о задаче Роббинса (на базе Bruss F.T. What is known about Robbins' problem // J.Appl.Prob. 42, 108-120, 2005.), я перескажу в другой заметке.
Подписывайтесь!
* Придуманный мною дон Роббинс не имеет никакого отношения к Герберту Эллису Роббинсу!