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

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

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

Застосування алгоритму простягається на багато областей через допустимість довільного визначення «можливості» («особливої події») таким чином дозволяючи оптимізацію загальних цільових функцій (див. Застосування). Наприклад, під час клінічних випробувань з єтичних міркувань є необхідним «оптимально» зупинитися, якщо в ряді випробувань з послідовно фіксованою кількістю пацієнтів з максимальною вірогідністю успіху у лікуванні останнього випробування був досягнутий. При такому випробуванні кожне успішне лікування — можливість. Можливості не порівнюються кількісно, але з моменту останньої можливості усі успіхи у лікуванні досягли рівня за якого усі подальші пацієнти можуть утриматися від подальшого лікування в рамках дослідження https://www.bfarm.de/EN/Medicinal-products/Clinical-trials/Compassionate-Use/_node.htmlhttps://www.researchgate.net/publication/268891237_Die_Kunst_der_richtigen_Entscheidung.

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

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

Задача про перебірливу наречену 160,06250,93750,06670,0667150,06670,93330,07140,1381140,07140,92860,07690,2150130,07690,92310,08330,2984120,08330,91670,09090,3893110,09090,90910,10000,4893100,10000,90000,11110,6004 90,11110,88890,12500,7254 80,12500,87500,14290,8682 70,14290,85710,16671,0349 Припустимо, що продавць уживаних машин розуміє, що у середньому в місяць 16 клієнтів цікавляться однією певною автівкою, яку він хоче продати лише тому клієнту, який запропонує найвищу ціну. Подія, яку буде розглядати торговець - вірогідність того, що ціна, яка була запропонована, є кращою аніж усі раніше запропоновані.

Для першої пропозиції така вірогідіність . Для другої пропозиції , за умови що кожна пропозиція піддається рівномірному розподілу, взагалі визначення вірогідності піддається правилу . З цього випливає та .

Так як торговець у середньому має 16 клієнтів в місяць . У таблиці вищче можна побачити, що індексом запунки є через те, що при сума сумування шансів в зворотньому порядку досягне значення 1 в перше, або ж перевищіть його. У цьому випадку все що залишається торговцю це чекати рівно до сьомої пропозиції, а потім узяти першу ж пропозицію, яка є кращою аніж усі інші.

Вірогідність того що угода буде виграшною (успішною) , або ж приблизно 39 відсотків. Іншими словами, торговець продасть авто за найкращу ціну у 39-ти відсотках випадків.

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

Визначення Розглянемо послідовність незалежних подій. Пов'яжемо із цією послідовністю іншу послідовність незалежних подій зі значеннями 1 або 0. Тут , що називається успіхом, означає подію, що -те спостереження є цікавим (як визначено особою, яка приймає рішення), і для нецікавих. Ці випадкові величини спостерігаються послідовно, і мета полягає в тому, щоб правильно вибрати останній успіх, коли він спостерігається.

Нехай ймовірність того, що k-та подія є цікавою. Далі нехай і . Зауважимо, що представляє шанси на те, що -та подія виявиться цікавою, пояснюючи назву алгоритму шансів.

Алгоритмічна процедура Стратегія є оптимальною при умові, що з усіх можливостей з високою вірогідністю буде вибрана остання. На практиці, під можливістю мається на увазі «подія», яка за певним критерієм є кращою аніж усі минулі події — наприклад, краща пропозиція ніж подальші пропозиції. У такому контексті стратегія обирає найкращу пропозицію з високою вірогідністю порівнянно з іншими стратегіями.

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

,

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

.

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

.

Вихід є

, поріг зупинки , ймовірність виграшу.

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

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

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

Стратегія шансів є оптимальною, тобто вона максимізує ймовірність зупинки на останній 1. Імовірність виграшу стратегії шансів дорівнює Якщо , ймовірність виграшу завжди принаймні . і ця нижня межа є найкращою з можливих.

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

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

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

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

Варіації обговорювали проблему вибору останніх успіхів.

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

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

обговорили проблему вибору з останніх і отримали жорстку нижню межу ймовірності виграшу. Коли задача еквівалентна задачі Брюсса про шанси. Якщо задача еквівалентна задачі в . Задача, що розглядається в отримується за умови, що

Проблема множинного вибору Гравцеві дозволено виборів, і він виграє, якщо будь-який вибір є останнім успішним. Для класичної проблеми секретаря обговорили випадки . Проблема шансів з обговорюється . Додаткові випадки проблеми шансів див. у .

Оптимальна стратегія для цієї задачі належить до класу стратегій, визначених набором порогових чисел , де .

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

Коли , показали, що нижня межа ймовірності виграшу дорівнює Для загального натурального числа , довели, що нижня межа ймовірності виграшу є ймовірністю виграшу у варіанті задачі секретаря, де потрібно вибрати k кращих кандидатів, використовуючи лише k спроб.

Коли , нижні межі ймовірностей виграшу дорівнюють , і відповідно.

Щодо подальших числових випадків для , а також алгоритму для загальних випадків, див. .

Див. також Шанси Клінічне випробування Задача про перебірливу наречену Прикладні теми, де у деякій частині інформації можна зустріти оптимальний розв'язок проблеми:

Задача про два конверти Парадокс Монті Голла

Примітки

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

«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). : (2008, unpublished)

Shoo-Ren Hsiao and Jiing-Ru. Yang: «Selecting the Last Success in Markov-Dependent Trials», , Vol. 93, 271—281, (2002).

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