Алгоритм шансов

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

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

Примеры

Две разные ситуации иллюстрируют заинтересованность в максимизации вероятности остановки на последнем конкретном событии.

Предположим, что автомобиль выставлен на продажу тому, кто предложит самую высокую цену (лучшее «предложение»). Позволять $n$ потенциальные покупатели откликаются и просят показать машину. Каждый настаивает на немедленном решении продавца принять предложение или нет. Определите ставку как интересную и присвойте ей код 1, если она лучше всех предыдущих ставок, и код 0 в противном случае. Ставки будут формировать случайную последовательность 0 и 1. Только единицы интересуют продавца, который может опасаться, что каждая последующая единица может оказаться последней. Из определения следует, что самая последняя 1 – это наибольшая ставка. Таким образом, максимизация вероятности продажи на последней единице означает максимизацию вероятности лучшей продажи .
Врач, применяющий специальное лечение, может использовать код 1 для успешного лечения, в противном случае — 0. Врач лечит последовательность $n$ пациентов таким же образом, и хочет свести к минимуму любые страдания и последовательно лечить каждого отзывчивого пациента. Остановка на последней единице в такой случайной последовательности нулей и единиц позволит достичь этой цели. Поскольку врач не пророк, цель состоит в том, чтобы максимизировать вероятность остановки на последней единице. (См. Сострадательное использование .)

Определения

Рассмотрим последовательность $n$ независимые мероприятия . Свяжите с этой последовательностью другую последовательность независимых событий. $I_{1},\,I_{2},\,\dots ,\,I_{n}$ со значениями 1 или 0. Здесь $\,I_{k}=1$ , называемый успехом, означаетсобытие, когда k-е наблюдение является интересным (как определено лицом, принимающим решение), и $\,I_{k}=0$ ибо неинтересно.Эти случайные величины $I_{1},\,I_{2},\,\dots ,\,I_{n}$ наблюдаются последовательно, и цель состоит в том, чтобы правильно выбрать последний успех, когда он наблюдается.

Позволять $\,p_{k}=P(\,I_{k}\,=1)$ — вероятность того, что k-е событие является интересным. Дальше пусть $\,q_{k}=\,1-p_{k}$ и $\,r_{k}=p_{k}/q_{k}$ . Обратите внимание, что $\,r_{k}$ представляет вероятность того, что k-е событие окажется интересным, что объясняет название алгоритма вероятности.

Алгоритмическая процедура

Алгоритм шансов суммирует шансы в обратном порядке.

r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,

до тех пор, пока эта сумма впервые не достигнет или не превысит значение 1. Если это происходит с индексом s , сохраняется s и соответствующая сумма.

R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,

Если сумма шансов не достигает 1, он устанавливает s = 1. В то же время он вычисляет

Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,

Результат:

$\,s$ , порог остановки
$\,w=Q_{s}R_{s}$ , вероятность победы.

Стратегия шансов

Стратегия шансов — это правило наблюдать события одно за другим и останавливаться на первом интересном событии, начиная с индекса s (если таковой имеется), где s — порог остановки выхода a.

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

Теорема о шансах

Теорема шансов утверждает, что

Стратегия шансов оптимальна , то есть максимизирует вероятность остановки на последней 1.
Вероятность выигрыша стратегии шансов равна $w=Q_{s}R_{s}$
Если $R_{s}\geq 1$ , вероятность выигрыша $w$ всегда не меньше $1/ e = 0,367879...$ , и эта нижняя граница является наилучшей из возможных .

Функции

Алгоритм шансов вычисляет оптимальную стратегию и оптимальную вероятность выигрыша одновременно . Кроме того, количество операций алгоритма шансов (суб)линейно по n. Следовательно, ни один более быстрый алгоритм не можетсуществуют для всех последовательностей, так что алгоритм шансов в то же время является оптимальным как алгоритм.

Источники

Брюсс в 2000 году разработал алгоритм шансов и придумал ему название. Он также известен как алгоритм (стратегия) Брюсса. Бесплатные реализации можно найти в Интернете.

Приложения

Приложения варьируются от медицинских вопросов в клинических испытаниях , проблем продаж, проблем секретаря , выбора портфеля , стратегий (одностороннего) поиска, проблем траектории и проблемы парковки , до проблем онлайн-обслуживания и других.

В том же духе существует теорема о шансах для непрерывных процессов прибытия с независимыми приращениями, таких как процесс Пуассона ( Bruss 2000 ). В некоторых случаях шансы не обязательно известны заранее (как в примере 2 выше), поэтому применение алгоритма шансов напрямую невозможно. В этом случае на каждом этапе можно использовать последовательные оценки шансов. Это имеет смысл, если количество неизвестных параметров не велико по сравнению с количеством наблюдений n. Однако в этом случае вопрос оптимальности более сложен и требует дополнительных исследований. Обобщения алгоритма шансов допускают различные вознаграждения за неспособность остановиться.и неправильные остановки, а также замена предположений о независимости более слабыми ( Ferguson 2008 ).

Вариации

Bruss & Paindaveine 2000 обсуждали проблему выбора последнего $k$ успехи.

Тамаки в 2010 году доказал теорему о мультипликативных шансах, которая решает проблему остановки на любом из последних чисел. $\ell$ успехи.Точная нижняя граница вероятности победы получена Мацуи и Ано в 2014 году .

Мацуи и Ано 2017 обсудили проблему выбора $k$ из последнего $\ell$ успехов и получил точную нижнюю границу вероятности победы. Когда $\ell =k=1,$ эта проблема эквивалентна проблеме шансов Брюсса. Если $\ell =k\geq 1,$ проблема эквивалентна проблеме Bruss & Paindaveine 2000 . Проблема, обсуждаемая Тамаки 2010, достигается путем установки $\ell \geq k=1.$

Проблема с множественным выбором

Игроку разрешено $r$ выбора, и он побеждает, если какой-либо выбор является последним успехом.Для классической задачи секретаря Гилберт и Мостеллер в 1966 г. обсудили случаи $r=2,3,4$ .Проблема шансов с $r=2,3$ обсуждается Ано, Какинумой и Миёси, 2010 г.Дополнительные случаи проблемы шансов см. в Matsui & Ano 2016 .

Оптимальная стратегия для этой задачи принадлежит к классу стратегий, определяемых набором пороговых чисел $(a_{1},a_{2},...,a_{r})$ , где $a_{1}>a_{2}>\cdots >a_{r}$ .

В частности, представьте, что у вас есть $r$ письма о приеме с пометкой $1$ к $r$ . У тебя было бы $r$ сотрудники, работающие с заявлениями, каждый из которых имеет по одному письму. Вы продолжаете проводить собеседования с кандидатами и ранжировать их в таблице, которую может видеть каждый специалист по подаче заявлений. Теперь офицер $i$ отправит письмо о принятии первому кандидату, который лучше всех кандидатов $1$ к $a_{i}$ . (Неотправленные письма о зачислении по умолчанию передаются последним претендентам, как и в стандартной задаче о секретаре.)

Когда $r=2$ , Ano, Kakinuma & Miyoshi 2010 показали, что точная нижняя граница вероятности победы равна $e^{-1}+e^{-{\frac {3}{2}}}.$ Для общего положительного целого числа $r$ , Мацуи и Ано 2016 доказали, что точная нижняя граница вероятности победы — это вероятность победы варианта задачи о секретаре, где нужно выбрать k лучших кандидатов, используя всего k попыток .

Когда $r=3,4,5$ , точные нижние границы вероятностей выигрыша равны $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}$ , $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$ и $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},$ соответственно.