Перегляд вихідного коду сторінки Алгоритм шансів

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

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

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

# Припустимо, що автомобіль виставлено на продаж тому, хто запропонує найвищу ціну (найкращу «пропозицію»). Нехай <math>n</math> потенційних покупців відгукнулися і попросили показати їм машину. Кожен з них наполягає на негайному рішенні продавця прийняти пропозицію чи ні. Визначимо пропозицію як цікаву і закодуємо її 1, якщо вона краща за всі попередні пропозиції, і 0 в іншому випадку. Пропозиції формують {{Нп|Випадкова послідовність|випадкову послідовність|en|Random sequence}} з 0 та 1. Тільки 1 цікавлять продавця, який може побоюватися, що кожна наступна 1 може стати останньою. З визначення випливає, що остання 1 є найвищою ставкою. Отже, максимізація ймовірності продажу за останньою одиницею означає максимізацію ймовірності продажу за ''найкращою'' ціною.
# Лікар, застосовуючи спеціальне лікування, може використовувати код 1 для успішного лікування, 0&nbsp;— у протилежному випадку. Лікар лікує послідовність з <math>n</math> пацієнтів однаковим чином і хоче мінімізувати будь-які страждання, а також вилікувати кожного пацієнта, який реагує на лікування. Зупинившись на останній 1 у такій випадковій послідовності 0 і 1, він досягне цієї мети. Оскільки лікар не пророк, його мета&nbsp;— максимізувати ймовірність зупинки на останній 1 (див. {{Нп|Милосердне застосування||en|Expanded access}}).

== Визначення ==
Розглянемо послідовність <math>n</math> [[Незалежність (теорія ймовірностей)|незалежних подій]]. Пов'яжемо із цією послідовністю іншу послідовність незалежних подій <math> I_1, I_2, \dots , I_n</math> зі значеннями 1 або 0. Тут <math>I_k =1</math>, що називається успіхом, означає подію, що <math>k</math>-те спостереження є цікавим (як визначено особою, яка приймає рішення), і <math>I_k=0</math> для нецікавих. Ці випадкові величини <math> I_1, I_2, \dots , I_n </math> спостерігаються послідовно, і мета полягає в тому, щоб правильно вибрати останній успіх, коли він спостерігається.

Нехай <math>p_k = P(I_k=1)</math> ймовірність того, що k-та подія є цікавою. Далі нехай <math>q_k = 1- p_k </math> і <math>r_k = p_k/q_k</math>. Зауважимо, що <math>r_k</math> представляє {{Нп|Шанси|шанси|en|Odds}} на те, що <math>k</math>-та подія виявиться цікавою, пояснюючи назву алгоритму шансів.

== Алгоритмічна процедура ==
Алгоритм шансів підсумовує шанси у зворотному порядку

: <math>r_n + r_{n-1} + r_{n-2}\, +\cdots</math>,

доки ця сума вперше не досягне або не перевищить значення 1. Якщо це відбувається з індексом ''s'', зберігається ''s'' і відповідна сума

: <math> R_s = \,r_n + r_{n-1} + r_{n-2} + \cdots + r_s</math>.

Якщо сума шансів не досягає 1, встановлюється ''s''&nbsp;=&nbsp;1. Водночас він обчислює

: <math> Q_{s}=q_n q_{n-1}\cdots q_s</math>.

Вихід є

# <math>\,s</math>, поріг зупинки
# <math>\,w = Q_s R_s</math>, ймовірність виграшу.

== Стратегія шансів ==
Стратегія шансів&nbsp;— це правило спостереження за подіями одна за одною та зупинка на першій цікавій події від індексу ''s'' (якщо є), де ''s''&nbsp;— поріг зупинки результату a.

Важливість стратегії шансів, а отже й алгоритму шансів, полягає в наступній теоремі шансів.

== Теорема шансів ==
Теорема шансів стверджує, що

# Стратегія шансів є ''оптимальною'', тобто вона максимізує ймовірність зупинки на останній 1.
# Імовірність виграшу стратегії шансів дорівнює <math>w= Q_s R_s</math>
# Якщо <math>R_s \geqslant 1</math>, ймовірність виграшу <math>w</math> завжди принаймні {{Math|1=1/[[e (число)|''e'']] = 0,367879...}}. і ця нижня межа є ''найкращою з можливих''.

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

== Джерела ==
Алгоритм шансів розробив {{Harvnb|Брюсс|2000}} року, який і придумав його назву. Він також відомий як алгоритм (стратегія) Брюсса. Реалізації з відкритим кодом можна знайти в Інтернеті.

== Застосування ==
Застосування алгоритму шансів охоплюють медичні питання в [[Клінічне випробування|клінічних випробуваннях]], проблеми з продажем, [[Задача про перебірливу наречену|задачі пошуку співробітника]], вибір [[Інвестиційний портфель|портфоліо]], (односторонні) стратегії пошуку, проблеми траєкторії та {{Нп|Проблема паралельного паркування|проблеми паркування|en|Parallel parking problem}} до проблем онлайн-обслуговування тощо.

Також існує теорема шансів для безперервних процесів надходження з {{Нп|Незалежні прирости|незалежними приростами|en|Independent increments}}, таких як [[Пуассонівський процес|процес Пуассона]] {{Harv|Брюсс|2000}}. У деяких випадках шанси не обов'язково відомі заздалегідь (як у прикладі 2 вище), тому застосування алгоритму шансів безпосередньо неможливо. У цьому випадку кожен крок може використовувати {{нпні|Послідовна оцінка|послідовні оцінки||Sequential estimate}} шансів. Це має сенс, якщо кількість невідомих параметрів невелика порівняно з кількістю спостережень ''n''. Питання оптимальності тоді є складнішим, однак, і вимагає додаткових досліджень. Узагальнення алгоритму шансів дозволяють отримати різну винагороду за невдалу і помилкову зупинку, а також замінити припущення про незалежність на слабші {{harv|Фергюсон|2008}}.

== Варіації ==
{{Harvnb|Брюсс|Пейндавейн|2000}} обговорювали проблему вибору останніх <math> k </math> успіхів.

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

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

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

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

Оптимальна стратегія для цієї задачі належить до класу стратегій, визначених набором порогових чисел <math>(a_1, a_2, ..., a_r)</math>, де <math>a_1 > a_2 > \cdots > a_r</math>.

Зокрема, уявіть, що у вас є <math>r</math> листів-зобов'язань, позначених від <math>1</math> до <math>r</math>. У вас буде <math>r</math> працівників, кожен з яких тримає одну літеру. Ви продовжуєте проводити співбесіди з кандидатами й заносите їх у таблицю, яку бачить кожен з них. Зараз працівник <math>i</math> надсилає лист-відповідь про прийняття на роботу першому кандидату, який виявився кращим за всіх інших кандидатів <math>1</math> до <math>a_i</math>. (Невідправлені листи про прийняття за замовчуванням віддаються останнім заявникам, так само як і у стандартній задачі про секретаря).

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

Коли <math> r=3,4,5 </math>, нижні межі ймовірностей виграшу дорівнюють <math> e^{-1}+ e^{-\frac{3}{2}}+e^{-\frac{47}{24}} </math>, <math> e^{-1}+e^{-\frac{3}{2}}+e^{-\frac{47}{24}}+e^{-\frac{2761}{1152}} </math> і <math> e^{-1}+e^{-\frac{3}{2}}+e^{-\frac{47}{24}}+e^{-\frac{2761}{1152}}+e^{-\frac{4162637}{1474560}}, </math> відповідно.

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

== Див. також ==
* {{Нп|Шанси|||Odds}}
* [[Клінічне випробування]]
* [[Задача про перебірливу наречену]]

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

* {{Cite journal|last=Ano|first=K.|last2=Kakinuma|first2=H.|last3=Miyoshi|first3=N.|year=2010|title=Odds theorem with multiple selection chances|journal=Journal of Applied Probability|volume=47|issue=4|pages=1093–1104|doi=10.1239/jap/1294170522|doi-access=free|ref={{SfnRef|Ано|Какінума|Мійоші|2010}}}}
* {{Cite journal|last=Bruss|first=F. Thomas|authorlink=Франц Томас Брюсс|year=2000|title=Sum the odds to one and stop|url=https://archive.org/details/sim_annals-of-probability_2000-07_28_3/page/1384|journal=The Annals of Probability|publisher=Institute of Mathematical Statistics|volume=28|issue=3|pages=1384–1391|doi=10.1214/aop/1019160340|issn=0091-1798|doi-access=free|ref={{SfnRef|Брюсс|2000}}}}
** «[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/note-on-a-lower-bound-for-the-multiplicative-odds-theorem-of-optimal-stopping/B759B6E4A9D83DB84D6EE1B4C827785B A note on Bounds for the Odds Theorem of Optimal Stopping]», ''{{нп|Аннали ймовірності|Annals of Probability||Annals of Probability}}'' Vol. 31, 1859—1862, (2003).
** «[https://web.archive.org/web/20230409100437/https://www.ems-ph.org/journals/newsletter/pdf/2006-12-62.pdf The art of a right decision]», ''Newsletter of the [[Європейське математичне товариство|European Mathematical Society]]'', Issue 62, 14–20, (2005).
* {{SfnRef inline|Фергюсон|2008}}{{нп|Томас С. Фергюсон|T. S. Ferguson||Thomas S. Ferguson}}: (2008, unpublished)
* {{Cite journal|last=Bruss|first=F. T.|last2=Paindaveine|first2=D.|year=2000|title=Selecting a sequence of last successes in independent trials|url=https://mpra.ub.uni-muenchen.de/21166/1/MPRA_paper_21166.pdf|journal=Journal of Applied Probability|volume=37|issue=2|pages=389–399|doi=10.1239/jap/1014842544|ref={{SfnRef|Брюсс|Пейндавейн|2000}}}}
* {{Cite journal|last=Gilbert|first=J|last2=Mosteller|first2=F|year=1966|title=Recognizing the Maximum of a Sequence|url=https://archive.org/details/sim_journal-of-the-american-statistical-association_1966-03_61_313/page/35|journal=Journal of the American Statistical Association|volume=61|issue=313|pages=35–73|doi=10.2307/2283044|jstor=2283044|ref={{SfnRef|Гілберт|Мостеллер|1966}}}}
* {{Cite journal|last=Matsui|first=T|last2=Ano|first2=K|year=2014|title=A note on a lower bound for the multiplicative odds theorem of optimal stopping|journal=Journal of Applied Probability|volume=51|issue=3|pages=885–889|doi=10.1239/jap/1409932681|doi-access=free|ref={{SfnRef|Мацуї|Ано|2014}}}}
* {{Cite journal|last=Matsui|first=T|last2=Ano|first2=K|year=2016|title=Lower bounds for Bruss' odds problem with multiple stoppings|journal={{нп|Mathematics of Operations Research}}|volume=41|issue=2|pages=700–714|arxiv=1204.5537|doi=10.1287/moor.2015.0748|ref={{SfnRef|Мацуї|Ано|2016}}}}
* {{Cite journal|last=Matsui|first=T|last2=Ano|first2=K|year=2017|title=Compare the ratio of symmetric polynomials of odds to one and stop|url=http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100773751|journal=Journal of Applied Probability|volume=54|pages=12–22|doi=10.1017/jpr.2016.83|ref={{SfnRef|Мацуї|Ано|2017}}}}
* Shoo-Ren Hsiao and Jiing-Ru. Yang: «[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/selecting-the-last-success-in-markovdependent-trials/09D192C389B4BA5D4E2CA678E11B31CC Selecting the Last Success in Markov-Dependent Trials]», ''{{нп|Журнал прикладної ймовірності|Journal of Applied Probability||Journal of Applied Probability}}'', Vol. 93, 271—281, (2002).
* {{Cite journal|last=Tamaki|first=M|year=2010|title=Sum the multiplicative odds to one and stop|journal=Journal of Applied Probability|volume=47|issue=3|pages=761–777|doi=10.1239/jap/1285335408|doi-access=free|ref={{SfnRef|Тамакі|2010}}}}
* Mitsushi Tamaki: «[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/optimal-stopping-on-trajectories-and-the-ballot-problem/4DEDE2A52A75420648C0DF39797E4A64 Optimal Stopping on Trajectories and the Ballot Problem]», ''{{нп|Журнал прикладної ймовірності|Journal of Applied Probability||Journal of Applied Probability}}'' Vol. 38, 946—959 (2001).
* E. Thomas, E. Levrat, B. Iung: «[https://hal.archives-ouvertes.fr/hal-00149994/document L'algorithme de Bruss comme contribution à une maintenance préventive]», ''{{нпні|Sciences et Technologies de l'automation}}'', Vol. 4, 13-18 (2007).
{{Reflist}}

== Посилання ==

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

[[Категорія:Оптимальні рішення]]
[[Категорія:Статистичні алгоритми]]
[[Категорія:Алгоритми оптимізації]]