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

Метод вычисления оптимальных стратегий для задач последнего успеха

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

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

Примеры

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

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

Определения

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

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

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

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

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

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

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

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

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

Результат:

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

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

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

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

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

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

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

Функции

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

Источники

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

Приложения

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

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

Вариации

Bruss & Paindaveine 2000 обсуждали проблему отбора последних успехов. ${\displaystyle k}$

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

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

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

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

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

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

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

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

Дополнительные числовые случаи для и алгоритм для общих случаев см. в Matsui & Ano 2016. ${\displaystyle r=6,...,10}$

Смотрите также

• Шансы
• Клиническое исследование
• Расширенный доступ
• Проблема с секретарем

Рекомендации

• Ано, К.; Какинума, Х.; Миёси, Н. (2010). «Теорема о шансах с множественными шансами выбора». Журнал прикладной вероятности . 47 (4): 1093–1104. дои : 10.1239/яп/1294170522 . S2CID  17598431.
• Брюсс, Ф. Томас (2000). «Суммируйте шансы к единице и остановитесь». Анналы вероятности . 28 (3). Институт математической статистики: 1384–1391. дои : 10.1214/aop/1019160340 . ISSN  0091-1798.
  • «Заметка об границах теоремы об оптимальной остановке о шансах», Annals of Probability Vol. 31, 1859–1862 (2003).
  • «Искусство правильного решения», Информационный бюллетень Европейского математического общества , выпуск 62, 14–20, (2005).
• Т.С. Фергюсон : (2008, неопубликовано)
• Брусс, FT; Пайндавейн, Д. (2000). «Выбор последовательности последних успехов в независимых испытаниях» (PDF) . Журнал прикладной вероятности . 37 (2): 389–399. дои : 10.1239/яп/1014842544.
• Гилберт, Дж; Мостеллер, Ф (1966). «Распознавание максимума последовательности». Журнал Американской статистической ассоциации . 61 (313): 35–73. дои : 10.2307/2283044. JSTOR  2283044.
• Мацуи, Т; Ано, К. (2014). «Заметка о нижней оценке теоремы мультипликативных шансов оптимальной остановки». Журнал прикладной вероятности . 51 (3): 885–889. дои : 10.1239/яп/1409932681 .
• Мацуи, Т; Ано, К. (2016). «Нижние оценки проблемы шансов Брусса с несколькими остановками». Математика исследования операций . 41 (2): 700–714. arXiv : 1204.5537 . дои : 10.1287/moor.2015.0748. S2CID  31778896.
• Мацуи, Т; Ано, К. (2017). «Сравнить отношение симметричных многочленов шансов к единице и остановиться». Журнал прикладной вероятности . 54 : 12–22. дои : 10.1017/января 2016.83. S2CID  41639968.
• Шу-Рен Сяо и Цзиинг-Ру. Ян: «Выбор последнего успеха в марково-зависимых испытаниях», Journal of Applied Probability , Vol. 93, 271–281 (2002).
• Тамаки, М. (2010). «Суммируйте мультипликативные шансы до единицы и остановитесь». Журнал прикладной вероятности . 47 (3): 761–777. дои : 10.1239/яп/1285335408 . S2CID  32236265.
• Мицуши Тамаки: «Оптимальная остановка на траекториях и проблема голосования», Journal of Applied Probability Vol. 38, 946–959 (2001).
• Э. Томас, Э. Леврат, Б. Юнг: «Алгоритм Брюса как вклад в предотвращение технического обслуживания», Sciences et Technologies de l'automation , Vol. 4, 13–18 (2007).

Внешние ссылки

• Алгоритм Брюсса http://www.p-roesler.de/odds.html