Kurzový algoritmus - Odds algorithm
The pravděpodobnostní algoritmus je matematická metoda pro výpočet optimálních strategií pro třídu problémů, které patří do domény optimální zastavení problémy. Jejich řešení vyplývá z pravděpodobnostní strategiea důležitost strategie pravděpodobnosti spočívá v její optimálnosti, jak je vysvětleno níže.
Algoritmus pravděpodobnosti se vztahuje na třídu volaných problémů poslední úspěch- problémy. Formálně je cílem těchto problémů maximalizovat pravděpodobnost identifikace v posloupnosti sekvenčně pozorovaných nezávislých událostí poslední událost splňující určité kritérium („konkrétní událost“). Tato identifikace musí být provedena v době pozorování. Přehodnocení předchozích pozorování není povoleno. Obvykle je určitá událost definována rozhodovacím orgánem jako událost, která je skutečně zajímavá z pohledu „zastavení“, aby bylo možné provést přesně definovanou akci. S takovými problémy se setkáváme v několika situacích.
Příklady
Dvě různé situace ilustrují zájem na maximalizaci pravděpodobnosti zastavení na poslední konkrétní události.
- Předpokládejme, že je auto inzerováno k prodeji nejvyšší nabídce (nejlepší „nabídka“). Nechte n potenciálních kupujících reagovat a požádejte o prohlídku vozu. Každý trvá na okamžitém rozhodnutí prodávajícího nabídku přijmout, či nikoli. Definujte nabídku jako zajímavýa kódováno 1, pokud je lepší než všechny předchozí nabídky, a jinak kódováno 0. Nabídky budou tvořit a náhodná sekvence 0 a 1 s. Prodejce zajímá pouze 1 s. Může se bát, že každá následující 1 může být poslední. Z definice vyplývá, že úplně poslední 1 je nejvyšší nabídka. Maximalizace pravděpodobnosti prodeje na poslední 1 proto znamená maximalizaci pravděpodobnosti prodeje nejlepší.
- Lékař, který používá speciální léčbu, může použít kód 1 pro úspěšnou léčbu, jinak 0. Lékař zachází se sekvencí n pacientů stejným způsobem a chce minimalizovat jakékoli utrpení a zacházet s každým pacientem reagujícím v této sekvenci. Zastavení na poslední 1 v takovém náhodném pořadí 0 s a 1 s by dosáhlo tohoto cíle. Jelikož lékař není prorokem, cílem je maximalizovat pravděpodobnost zastavení na posledním 1. (Viz Soucitné použití.)
Definice
Zvažte posloupnost nezávislé události. Přiřaďte k této sekvenci jinou sekvenci s hodnotami 1 nebo 0. Zde , označovaný jako úspěch, stojí za událostí, že k-té pozorování je zajímavé (jak je definováno osobou s rozhodovací pravomocí), a sledujeme nezávislé náhodné proměnné postupně a chcete vybrat poslední úspěch.
Nechat je pravděpodobnost, že k-ta událost je zajímavá. Dále nechte a .Všimněte si, že představuje šance k-té události se ukázalo být zajímavou, vysvětlující název pravděpodobnostního algoritmu.
Algoritmický postup
Kurzový algoritmus shrnuje kurzy v opačném pořadí
dokud tento součet poprvé nedosáhne nebo nepřekročí hodnotu 1. Pokud k tomu dojde u indexu s, šetří to s a odpovídající částka
Pokud součet kurzů nedosáhne 1, nastaví se s = 1. Zároveň se počítá
Výstup je
- mezní hodnota pro zastavení
- , pravděpodobnost výhry.
Kurzová strategie
Kurzová strategie je pravidlem sledovat události jeden po druhém a zastavit se na první zajímavé události z indexu s dále (pokud existují), kde s je mezní hodnota pro zastavení výstupu a.
Důležitost pravděpodobnostní strategie, a tedy i pravděpodobnostního algoritmu, spočívá v následující větě o pravděpodobnostech.
Věta o kurzech
Věta o pravděpodobnosti to říká
- Kurzová strategie je optimální, to znamená, že maximalizuje pravděpodobnost zastavení na poslední 1.
- Pravděpodobnost výhry pravděpodobnostní strategie se rovná
- Li , pravděpodobnost výhry je vždy alespoň a tato dolní mez je nejlepší možné.
Funkce
Kurzový algoritmus vypočítá optimální strategie a optimální pravděpodobnost výhry ve stejnou dobu. Také počet operací algoritmu pravděpodobnosti je (sub) lineární v n. Pro všechny sekvence tedy nemůže existovat rychlejší algoritmus, takže algoritmus pravděpodobnosti je současně optimální jako algoritmus.
Zdroje
Bruss 2000 vymyslel lichý algoritmus a vytvořil jeho jméno. Je také známý jako Brussův algoritmus (strategie). Zdarma implementace lze nalézt na webu.
Aplikace
Aplikace dosahují od lékařských otázek v klinické testy přes problémy s prodejem, problémy se sekretářkou, portfolio výběr, (jednosměrné) vyhledávací strategie, problémy trajektorie a problém s parkováním k problémům v on-line údržbě a dalším.
Ve stejném duchu existuje věta o kurzech pro procesy příchodu v nepřetržitém čase s nezávislé přírůstky tak jako Poissonův proces Brusse. V některých případech nejsou kurzy nutně známy předem (jako v příkladu 2 výše), takže použití algoritmu kurzů není přímo možné. V tomto případě lze použít každý krok postupné odhady šance. To má smysl, pokud počet neznámých parametrů není velký ve srovnání s počtem n pozorování. Otázka optimality je pak komplikovanější a vyžaduje další studie. Zobecnění algoritmu pravděpodobnosti umožňuje různé odměny za nezastavení a nesprávné zastávky, stejně jako nahrazení předpokladů nezávislosti slabšími (Ferguson (2008)).
Variace
Bruss & Paindaveine 2000 diskutovali o problému výběru posledního úspěchy.
Tamaki 2010 se ukázala jako multiplikativní věta o pravděpodobnosti, která se zabývá problémem zastavení u kterékoli z posledních úspěchy. Pevnou spodní hranici pravděpodobnosti výhry získá Matsui & Ano 2014.
Matsui & Ano 2017 diskutovali o problému výběru z posledního úspěchy a získal pevnou spodní hranici pravděpodobnosti výhry. Když problém je ekvivalentní Brussovu problému s pravděpodobností. Li problém je ekvivalentní problému v Bruss & Paindaveine 2000. Problém diskutovaný uživatelem Tamaki 2010 se získá nastavením
problém s výběrem odpovědí: Hráč je povolen volby a on vyhraje, pokud je volba posledním úspěchem. U klasického problému s sekretářkou Gilbert & Mosteller 1966 projednal případy Problém s pravděpodobností projednává Ano, Kakinuma a Miyoshi 2010 Další případy problému s pravděpodobností viz Matsui & Ano 2016.
Optimální strategie patří do třídy strategií definovaných množinou prahových čísel , kde . První volba se použije u prvních kandidátů počínaje th žadatel, a jakmile je použita první volba, druhá volba má být použita u prvního kandidáta počínaje th žadatel, a tak dále.
Když , Ano, Kakinuma a Miyoshi 2010 ukázal, že těsná dolní hranice pravděpodobnosti výhry se rovná Pro obecné kladné celé číslo , Matsui & Ano 2016 diskutovali o těsné spodní hranici pravděpodobnosti výhry , těsné spodní hranice pravděpodobností výhry se rovná , a Pro další případy viz Matsui & Ano 2016.
Viz také
Reference
- Ano, K .; Kakinuma, H .; Miyoshi, N. (2010). „Věta o šancích s více šancemi na výběr“ (PDF). Journal of Applied Probability. 47 (4): 1093–1104. doi:10.1239 / jap / 1294170522.CS1 maint: ref = harv (odkaz)
- Bruss, F. Thomas (2000). "Sčítat šance na jednoho a zastavit". Letopisy pravděpodobnosti. Ústav matematické statistiky. 28 (3): 1384–1391. doi:10.1214 / aop / 1019160340. ISSN 0091-1798.CS1 maint: ref = harv (odkaz)
- —: "Poznámka k hranicím věty o kursu optimálního zastavení ", Annals of Probability Sv. 31, 1859-1862, (2003).
- -: "Umění správného rozhodnutí", Newsletter Evropská matematická společnost, Číslo 62, 14–20, (2005).
- T. S. Ferguson: (2008, nepublikováno)
- Bruss, F. T .; Paindaveine, D. (2000). „Výběr sekvence posledních úspěchů v nezávislých studiích“ (PDF). Journal of Applied Probability. 37 (2): 389–399. doi:10.1239 / jap / 1014842544.CS1 maint: ref = harv (odkaz)
- Gilbert, J; Mosteller, F (1966). Msgstr "Rozpoznávání maxima sekvence". Journal of the American Statistical Association. 61 (313): 35–73. doi:10.2307/2283044. JSTOR 2283044.CS1 maint: ref = harv (odkaz)
- Matsui, T; Ano, K (2014). „Poznámka k dolní hranici pro teorém multiplikativní pravděpodobnosti optimálního zastavení“. Journal of Applied Probability. 51 (3): 885–889. doi:10.1239 / jap / 1409932681.CS1 maint: ref = harv (odkaz)
- Matsui, T; Ano, K (2016). "Nižší hranice pro Brussův problém s pravděpodobností při více zastaveních". Matematika operačního výzkumu. 41 (2): 700–714. arXiv:1204.5537. doi:10,1287 / měsíc 2015.0748.CS1 maint: ref = harv (odkaz)
- Matsui, T; Ano, K (2017). Msgstr "Porovnejte poměr symetrických polynomů šance k jedné a zastavte". Journal of Applied Probability. 54: 12–22. doi:10.1017 / jpr.2016.83.CS1 maint: ref = harv (odkaz)
- Shoo-Ren Hsiao a Jiing-Ru. Yang: "Výběr posledního úspěchu ve studiích závislých na Markově ", Journal of Applied Probability, Sv. 93, 271–281, (2002).
- Tamaki, M (2010). „Sčítejte multiplikativní kurzy k jednomu a zastavte se“ (PDF). Journal of Applied Probability. 47 (3): 761–777. doi:10.1239 / jap / 1285335408.CS1 maint: ref = harv (odkaz)
- Mitsushi Tamaki: "Optimální zastavení na trajektoriích a problém s hlasováním ", Journal of Applied Probability Sv. 38, 946–959 (2001).
- E. Thomas, E. Levrat, B. Iung: "L'algorithme de Bruss přispívá jako preventivní opatření k údržbě ", Sciences et Technologies de l'automation, Sv. 4, 13-18 (2007).
externí odkazy
- Bruss-Algorithmus http://www.p-roesler.de/odds.html