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

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

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

Приклади

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

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

Визначення

Розглянемо послідовність $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$.

Вихід є

1. $s$, поріг зупинки
2. $w=Q_s{R}_s$, ймовірність виграшу.

Стратегія шансів

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

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

Теорема шансів

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

1. Стратегія шансів є оптимальною, тобто вона максимізує ймовірність зупинки на останній 1.
2. Імовірність виграшу стратегії шансів дорівнює $w=Q_s{R}_s$
3. Якщо $R_s⩾1$, ймовірність виграшу $w$ завжди принаймні Шаблон:Math. і ця нижня межа є найкращою з можливих.

Особливості

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

Джерела

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

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

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

Також існує теорема шансів для безперервних процесів надходження з Шаблон:Нп, таких як процес Пуассона Шаблон:Harv. У деяких випадках шанси не обов'язково відомі заздалегідь (як у прикладі 2 вище), тому застосування алгоритму шансів безпосередньо неможливо. У цьому випадку кожен крок може використовувати Шаблон:Нпні шансів. Це має сенс, якщо кількість невідомих параметрів невелика порівняно з кількістю спостережень n. Питання оптимальності тоді є складнішим, однак, і вимагає додаткових досліджень. Узагальнення алгоритму шансів дозволяють отримати різну винагороду за невдалу і помилкову зупинку, а також замінити припущення про незалежність на слабші Шаблон:Harv.

Варіації

Шаблон:Harvnb обговорювали проблему вибору останніх $k$ успіхів.

Шаблон:Harvnb довів теорему про мультиплікативні шанси, яка розглядає проблему зупинки на будь-якому з останніх $\ell$ успіхів.

Жорстка нижня межа ймовірності виграшу отримана за формулою Шаблон:Harvnb.

Шаблон:Harvnb обговорили проблему вибору $k$ з останніх $\ell$ і отримали жорстку нижню межу ймовірності виграшу. Коли $\ell =k=1,$ задача еквівалентна задачі Брюсса про шанси. Якщо $\ell =k\ge 1,$ задача еквівалентна задачі в Шаблон:Harvnb. Задача, що розглядається в Шаблон:Harvnb отримується за умови, що $\ell \ge k=1.$

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

Гравцеві дозволено $r$ виборів, і він виграє, якщо будь-який вибір є останнім успішним. Для класичної проблеми секретаря Шаблон:Harvnb обговорили випадки $r=2,3,4$. Проблема шансів з $r=2,3$ обговорюється Шаблон:Harvnb. Додаткові випадки проблеми шансів див. у Шаблон:Harvnb.

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

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

Коли $r=2$, Шаблон:Harvnb показали, що нижня межа ймовірності виграшу дорівнює $e^{-1}+e^{-\frac{3}{2}}.$ Для загального натурального числа $r$, Шаблон:Harvnb довели, що нижня межа ймовірності виграшу є ймовірністю виграшу у варіанті задачі секретаря, де потрібно вибрати 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}},$ відповідно.

Щодо подальших числових випадків для $r=6,...,10$, а також алгоритму для загальних випадків, див. Шаблон:Harvnb.

Див. також

• Шаблон:Нп
• Клінічне випробування
• Задача про перебірливу наречену

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

• Шаблон:Cite journal
• Шаблон:Cite journal
  • «A note on Bounds for the Odds Theorem of Optimal Stopping», Шаблон:Нп Vol. 31, 1859—1862, (2003).
  • «The art of a right decision», Newsletter of the European Mathematical Society, Issue 62, 14–20, (2005).
• Шаблон:SfnRef inlineШаблон:Нп: (2008, unpublished)
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Shoo-Ren Hsiao and Jiing-Ru. Yang: «Selecting the Last Success in Markov-Dependent Trials», Шаблон:Нп, Vol. 93, 271—281, (2002).
• Шаблон:Cite journal
• Mitsushi Tamaki: «Optimal Stopping on Trajectories and the Ballot Problem», Шаблон:Нп 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