§ 13.2. Вознаграждение статистика

Исследуемая здесь задача имеет много названий, среди прочих такие, как задача о выборе жениха или невесты, задача о секретаре, задача о конкурсе красоты. Мы предпочли более нейтральный контекст, но читатель при желании сам без труда сможет перевести все на более созвучный ему язык.

Предположим, что некий предприимчивый статистик в некой экзотической стране пользуется благосклонностью ее правителя» который позволяет ему просмотреть заданное число самых прекрасных произведений искусства и выбрать из них одно в качестве вознаграждения. Статистик последовательно наблюдает эти предметы в случайном порядке. Каждый раз после того, как просмотрены предметов, он может упорядочить их по рангам, от наиболее предпочтительного (ранг 1) до наименее предпочтительного (ранг ). По наблюдении очередного предмета статистик определяет его ранг, включая его в уже имеющуюся шкалу рангов. На каждом шаге он может либо остановить процесс наблюдения и выбрать последний просмотренный предмет, либо продолжать наблюдения. Однажды отказавшись избрать некоторый предмет, он уже не может вернуться назад и выбрать его впоследствии. Если же статистик ни на чем не остановится, он получает в награду предмет. Основным характеристическим свойством этой задачи является то, что единственной относящейся к делу информацией, получаемой статистиком о каждом предмете, является его относительный ранг среди уже просмотренных предметов.

При пусть обозначает полезность статистика, (проистекающую) от выбора предмета, имеющего ранг среди всех предметов. Мы предположим, что Пусть X обозначает случайную величину, представляющую собой ранг выбранного предмета при некотором правиле остановки. Задачей статистика является отыскание правила остановки, максимизирующего . В этой задаче рассматривать цену наблюдения нет необходимости.

Для обозначим через среднюю полезность от оптимального продолжения, когда было

просмотрено предметов, причем ранг предмета среди просмотренных равнялся а. Обозначим, далее, через среднюю полезность от выбора объекта и окончания наблюдений. Так как процесс наблюдения должен быть закончен самое позднее просмотром -го предмета, имеют место соотношения

Вычислим теперь вероятность того, что предмет, имеющий ранг а среди первых просмотренных, имеет ранг среди всех предметов. Это событие можно описать следующим образом. В случайном выборке объема из совокупности в предметов ровно предметов извлечены из множества предметов высших рангов, один предмет имеет ранг а оставшиеся а предметов принадлежат к множеству предметов низших рангов. Поэтому искомая вероятность равна

Ранг должен удовлетворять неравенствам

Из определения и из (2) следует, что при

В силу предположения о случайном порядке появления предметов ранг просматриваемого очередного предмета с одинаковой вероятностью примет значения среди рангов первых предметов. Если его ранг равен то средняя полезность от оптимального продолжения равна Так как каждому из значений отвечает вероятность то ясно, что после просмотра предметов средняя полезность от наблюдения еще одного предмета и последующего оптимального продолжения равна

Из (4) и из определения видно, что удовлетворяет следующему функциональному уравнению

Таким образом, значения можноопределять с помощью соотношений (1), (3) и (5), начиная с последнего шага, по методу индукции назад. Согласно оптимальной процедуре, наблюдения продолжаются, если и заканчиваются, когда