Вы помните, как Сильвер стал квортермастером (квартирмейстером) у Флинта? Тогда было n претендентов на должность, причем Флинт беседовал с каждым и мог сравнить претендента с уже опрошенными, но не знал качества претендента: только "лучше-хуже". Пирата можно было либо нанять, либо отказать: обидчивые пираты ждать не могли себе позволить. Оптимальная стратегия дает необычно большую вероятность взять лучшего: в пределе при больших n это 1/e ≈ 0.37 (причем и при малых оценка хороша), а состоит стратегия в том, чтобы пропустить примерно 37% пиратов (n/e), набирая статистику, а потом взять первого, который лучше всех уже опрошенных. Предполагается, что качество пирата распределено равномерно на [0,1] и от качества других пиратов не зависит. Флинт, еще раз, этого качества не знает, а может только определить, выше оно или ниже, чем у другого.
Оглавление рубрики "Похождения Сильвера"
Сегодня я расскажу вам о другом выборе: судового врача. Сильвер все это организовывал, и вот как все происходило.
Претендентов тоже было заранее известное количество n. Однако теперь Сильвер, беседуя с претендентами на место, ставил им числовую оценку. То есть, в отличие от предыдущего случая, выбирающий знал оценку качества претендента (они по-прежнему распределены равномерно на [0,1] и Сильверу это известно). Второе отличие: Сильвер не гнался за лучшим претендентом, ему был нужен как можно более хороший хирург: в среднем.
Как действовать в случае, если надо как можно более высокую вероятность выбрать лучшего при наличии информации о качестве, я расскажу в другой раз (следите за публикациями))). А сегодня проследим за действиями Сильвера.
Что такое максимум в среднем? Допустим, что такая задача ставится часто: смертность у пиратов, увы, высокая. Каждый раз, действуя по схеме, Сильвер берет в команду кого-то с каким-то качеством. Потом, сложим эти оценки у тысячи, скажем, персон, мы делим на их количество и получаем оценку в среднем. Вот Сильвер и хотел, чтобы его схема доставляла максимум этой средней оценки.
Это важно понять. Максимум вероятности взять лучшего означает, что из тысячи (грубо) таких игр число случаев, когда удалось выбрать лучшего, больше, чем при любой другой схеме. В остальных случаях могли быть и дрянные персонажи. В среднем же важно избегать совсем отстойных, а лучшие и не обязательны, разве что для компенсации неудач.
Итак, какова же схема? Схема — это выбор порогов для каждого претендента: если он лучше, он принят. Пороги обозначим t(i), где i — номер претендента. Так вот, оптимальные пороги такие: t(n)=0 (последнего берем в любом случае, без хирурга в плавании нельзя),
Эта последовательность известна как последовательность Мозера. При этом среднее качество принятого доктора будет t(0). А доктора, принятого на шаге i, t(i-1).
Для n=12 пороги такие:
0.871 0.861 0.85 0.836 0.82 0.8 0.775 0.742 0.695 0.625 0.5 0.0, при этом среднее качество 0.879.
Вот однострочник на Перл, который это считает:
perl -E '$n=shift;$t=0;for(0..$n){unshift@t,sprintf "%.3f",$t;$t=(1+$t*$t)/2};say"v=",shift@t;say"@t" ' 42
Смотрите, как интересно выходит: чем больше претендентов, тем лучше, в среднем, выбранный претендент! Для 35 человек среднее качество выбранного больше 0.95! То есть, грубо говоря, мы либо берем всегда не менее, чем 0.9, либо очень редко попадается и ноль, но намного чаще 0.99.
Эта задача известна как "задача о продаже дома": в этом случае случайные величины — предложения цены. Их распределение может быть и не равномерным. Еще может действовать плата за ход, при которой выигрыш уменьшается за счет налогов, дисконтов, инфляции и т.п. постоянных "платежей". В этом случае выигрыш не растет монотонно с ростом числа n и можно даже рассматривать задачу с бесконечным горизонтом.
Теперь обсудим, как это получилось.
На последнем шаге порог нуль: мы берем последнего претендента, каков бы он ни был — по условию. Его среднее качество равно 0.5, просто потому что таково среднее по распределению: претендент с равными шансами может быть лучше или хуже, чем 0.5.
На шаге n-1 нам нет смысла брать человека хуже, чем 0.5, так как мы чаще будем получать лучшего, чем худшего, на последнем шаге. Так что порог равен 0.5, а среднее качество считается интегралом: по отрезку от 0 до 0.5 от числа 0.5, а по отрезку от 0.5 до 1 — от x. Интеграл по вероятности, но для равномерного распределения это просто dx. Получается 5/8, или (1+0.5²)/2, как и утверждается.
Далее по индукции. Мы знаем среднее качество t=t(i) претендента с номером i, так что на шаге i-1 мы отвергаем всякого, кто хуже. Отсюда сразу следует, что среднее качество претендента, взятого на после i-1 шага, равно порогу претендента i-1.
Если претендент от 0 до t, то он отвергается и мы в среднем получаем качество t на последующих шагах. Это дает вклад t² в среднее качество выбранного. Если же претендент лучше, то его среднее качество есть интеграл от t до 1 от xdx, то есть равен (1-t²)/2. Складывая, имеем доказываемую формулу.
Среднее качество хирурга есть результат после нуля шагов, что и требовалось доказать.
Этот метод, рассуждать с конца, называется динамическим программированием. Странное название, но так уж закрепилось.
Очень поучительно самостоятельно поразбирать варианты задачи. Дело не в том, как выбирать что-то, тем более что равномерное распределение качества встречается нечасто. Дело в принципе и в нетривиальных оценках и алгоритмах. Несколько вариантов обсудим в будущих публикациях.
До встречи!
Для дальнейшего чтения:
- Березовский А.Б. (тот самый: был когда-то полезным человеком...) Задача наилучшего выбора. М.: Наука, 1984.
- Гусейн-Заде С.М. Разборчивая невеста. 2003.
- Мазалов В.В. Моменты остановки и управляемые случайные блуждания. 1992.
- Ивашко А.А. Дискретные задачи оптимальной остановки. 2017.
- Роббинс Г. Теория оптимальных правил остановки. 1977.