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

У теорії рішень алгоритм шансів (або алгоритм Брюсса) — це математичний метод обчислення оптимальних стратегій для класу задач, які належать до області задач оптимальної зупинки. Їх розв'язок випливає зі стратегії шансів, а важливість стратегії шансів полягає в її оптимальності, як пояснюється нижче.

Алгоритм шансів застосовується до класу проблем, які називаються проблемами останнього успіху. Формально метою цих задач є максимізація ймовірності ідентифікації в послідовності незалежних подій саме останньої події, яка задовольняє певному критерію («специфічна подія»). Ця ідентифікація повинна бути зроблена в момент спостереження. Повернення до попередніх спостережень не дозволяється. Зазвичай особлива подія визначається особою, яка приймає рішення, як подія, що становить справжній інтерес з погляду «зупинки» для здійснення чітко визначеної дії. Такі проблеми виникають у кількох ситуаціях.

Приклади

Дві різні ситуації є прикладами зацікавленості в максимізації ймовірності зупинитися на останній події.

1. Припустимо, що автомобіль виставлено на продаж тому, хто запропонує найвищу ціну (найкращу «пропозицію»). Нехай ${\displaystyle n}$ потенційних покупців відгукнулися і попросили показати їм машину. Кожен з них наполягає на негайному рішенні продавця прийняти пропозицію чи ні. Визначимо пропозицію як цікаву і закодуємо її 1, якщо вона краща за всі попередні пропозиції, і 0 в іншому випадку. Пропозиції формують ^[en] з 0 та 1. Тільки 1 цікавлять продавця, який може побоюватися, що кожна наступна 1 може стати останньою. З визначення випливає, що остання 1 є найвищою ставкою. Отже, максимізація ймовірності продажу за останньою одиницею означає максимізацію ймовірності продажу за найкращою ціною.
2. Лікар, застосовуючи спеціальне лікування, може використовувати код 1 для успішного лікування, 0 — у протилежному випадку. Лікар лікує послідовність з ${\displaystyle n}$ пацієнтів однаковим чином і хоче мінімізувати будь-які страждання, а також вилікувати кожного пацієнта, який реагує на лікування. Зупинившись на останній 1 у такій випадковій послідовності 0 і 1, він досягне цієї мети. Оскільки лікар не пророк, його мета — максимізувати ймовірність зупинки на останній 1 (див. розділ ^[en]).

Визначення

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

Нехай ${\displaystyle \,p_{k}=P(\,I_{k}\,=1)}$ ймовірність того, що k-та подія є цікавою. Далі нехай ${\displaystyle \,q_{k}=\,1-p_{k}}$ і ${\displaystyle \,r_{k}=p_{k}/q_{k}}$. Зауважимо, що ${\displaystyle \,r_{k}}$ представляє ^[en] на те, що 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. Якщо ${\displaystyle R_{s}\geq 1}$, ймовірність виграшу ${\displaystyle w}$ завжди принаймні 1/e = 0.367879.... і ця нижня межа є найкращою з можливих.

Особливості

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

Джерела

Алгоритм шансів розробив Брюсс, 2000 року, який і придумав його назву. Він також відомий як алгоритм (стратегія) Брюсса. Безкоштовні втілення можна знайти в Інтернеті.

Застосування

Застосування алгоритму шансів охоплюють медичні питання в клінічних випробуваннях, проблеми з продажем, секретарські проблеми, вибір портфоліо, (односторонні) стратегії пошуку, проблеми траєкторії та ^[en] до проблем онлайн-обслуговування тощо.

Також існує теорема шансів для безперервних процесів надходження з ^[en], таких як процес Пуассона (Брюсс, 2000). У деяких випадках шанси не обов'язково відомі заздалегідь (як у прикладі 2 вище), тому застосування алгоритму шансів безпосередньо неможливо. У цьому випадку кожен крок може використовувати шансів. Це має сенс, якщо кількість невідомих параметрів невелика порівняно з кількістю спостережень n. Питання оптимальності тоді є складнішим, однак, і вимагає додаткових досліджень. Узагальнення алгоритму шансів дозволяють отримати різну винагороду за невдалу і помилкову зупинку, а також замінити припущення про незалежність на слабші (Фергюсон, 2008).

Варіації

Брюсс та Пейндавейн, 2000 обговорювали проблему вибору останніх ${\displaystyle k}$ успіхів.

Тамакі, 2010 довів теорему про мультиплікативні шанси, яка розглядає проблему зупинки на будь-якому з останніх ${\displaystyle \ell }$ успіхів.

Жорстка нижня межа ймовірності виграшу отримана за формулою Мацуї та Ано, 2014.

Мацуї та Ано, 2017 обговорили проблему вибору ${\displaystyle k}$ з останніх ${\displaystyle \ell }$ і отримали жорстку нижню межу ймовірності виграшу. Коли ${\displaystyle \ell =k=1,}$ задача еквівалентна задачі Брюсса про шанси. Якщо ${\displaystyle \ell =k\geq 1,}$ задача еквівалентна задачі в Брюсс та Пейндавейн, 2000. Задача, що розглядається в Тамакі, 2010 отримується за умови, що ${\displaystyle \ell \geq k=1.}$

Проблема множинного вибору

Гравцеві дозволено ${\displaystyle r}$ виборів, і він виграє, якщо будь-який вибір є останнім успішним. Для класичної проблеми секретаря Гілберт та Мостеллер, 1966 обговорили випадки ${\displaystyle r=2,3,4}$. Проблема шансів з ${\displaystyle r=2,3}$ обговорюється Ано, Какінума та Мійоші, 2010. Додаткові випадки проблеми шансів див. у Мацуї та Ано, 2016.

Оптимальна стратегія для цієї задачі належить до класу стратегій, визначених набором порогових чисел ${\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}}$. (Невідправлені листи про прийняття за замовчуванням віддаються останнім заявникам, так само як і у стандартній задачі про секретаря).

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

Коли ${\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}}},}$ відповідно.

Щодо подальших числових випадків для ${\displaystyle r=6,...,10}$, а також алгоритму для загальних випадків, див. Мацуї та Ано, 2016.

Див. також

• ^[en]
• Клінічне випробування
• Задача про перебірливу наречену

Список літератури

• Ano, K.; Kakinuma, H.; Miyoshi, N. (2010). Odds theorem with multiple selection chances. Journal of Applied Probability. 47 (4): 1093—1104. doi:10.1239/jap/1294170522.
• (2000). Sum the odds to one and stop. The Annals of Probability. Institute of Mathematical Statistics. 28 (3): 1384—1391. doi:10.1214/aop/1019160340. ISSN 0091-1798.
  • «A note on Bounds for the Odds Theorem of Optimal Stopping», ^[en] Vol. 31, 1859—1862, (2003).
  • «», Newsletter of the European Mathematical Society, Issue 62, 14–20, (2005).
• ^[en]: (2008, unpublished)
• Bruss, F. T.; Paindaveine, D. (2000). Selecting a sequence of last successes in independent trials (PDF). Journal of Applied Probability. 37 (2): 389—399. doi:10.1239/jap/1014842544.
• Gilbert, J; Mosteller, F (1966). Recognizing the Maximum of a Sequence. Journal of the American Statistical Association. 61 (313): 35—73. doi:10.2307/2283044. JSTOR 2283044.
• Matsui, T; Ano, K (2014). A note on a lower bound for the multiplicative odds theorem of optimal stopping. Journal of Applied Probability. 51 (3): 885—889. doi:10.1239/jap/1409932681.
• Matsui, T; Ano, K (2016). Lower bounds for Bruss' odds problem with multiple stoppings. ^[en]. 41 (2): 700—714. arXiv:1204.5537. doi:10.1287/moor.2015.0748.
• Matsui, T; Ano, K (2017). Compare the ratio of symmetric polynomials of odds to one and stop. Journal of Applied Probability. 54: 12—22. doi:10.1017/jpr.2016.83.
• Shoo-Ren Hsiao and Jiing-Ru. Yang: «Selecting the Last Success in Markov-Dependent Trials», ^[en], Vol. 93, 271—281, (2002).
• Tamaki, M (2010). Sum the multiplicative odds to one and stop. Journal of Applied Probability. 47 (3): 761—777. doi:10.1239/jap/1285335408.
• Mitsushi Tamaki: «Optimal Stopping on Trajectories and the Ballot Problem», ^[en] Vol. 38, 946—959 (2001).
• E. Thomas, E. Levrat, B. Iung: «L'algorithme de Bruss comme contribution à une maintenance préventive», , Vol. 4, 13-18 (2007).

Посилання

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