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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Приклади

[ред. | ред. код]

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

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

Визначення

[ред. | ред. код]

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

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

Алгоритмічна процедура

[ред. | ред. код]

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

,

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

.

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

.

Вихід є

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

Особливості

[ред. | ред. код]

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

Джерела

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

Варіації

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

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

Див. також

[ред. | ред. код]

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

[ред. | ред. код]

Посилання

[ред. | ред. код]