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.

1. 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ší.
2. 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 ${displaystyle n}$ nezávislé události. Přiřaďte k této sekvenci jinou sekvenci ${displaystyle I_ {1} ,, I_ {2} ,, tečky ,, I_ {n}}$ s hodnotami 1 nebo 0. Zde ${displaystyle, I_ {k} = 1}$, 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 ${displaystyle, I_ {k} = 0}$ sledujeme nezávislé náhodné proměnné ${displaystyle I_ {1} ,, I_ {2} ,, tečky ,, I_ {n}}$ postupně a chcete vybrat poslední úspěch.

Nechat ${displaystyle, p_ {k} = P (, I_ {k}, = 1)}$ je pravděpodobnost, že k-ta událost je zajímavá. Dále nechte${displaystyle, q_ {k} =, 1-p_ {k}}$ a ${displaystyle, r_ {k} = p_ {k} / q_ {k}}$.Všimněte si, že ${displaystyle, r_ {k}}$ 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í

${displaystyle r_ {n} + r_ {n-1} + r_ {n-2}, + cdots ,,}$

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

${displaystyle R_ {s} =, r_ {n} + r_ {n-1} + r_ {n-2} + cdots + r_ {s}.,}$

Pokud součet kurzů nedosáhne 1, nastaví se s = 1. Zároveň se počítá

${displaystyle Q_ {s} = q_ {n} q_ {n-1} cdots q_ {s}.,}$

Výstup je

1. ${displaystyle, s}$mezní hodnota pro zastavení
2. ${displaystyle, w = Q_ {s} R_ {s}}$, 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á

1. Kurzová strategie je optimální, to znamená, že maximalizuje pravděpodobnost zastavení na poslední 1.
2. Pravděpodobnost výhry pravděpodobnostní strategie se rovná ${displaystyle, w = Q_ {s} R_ {s}}$
3. Li ${displaystyle, R_ {s} geq, 1}$, pravděpodobnost výhry ${displaystyle, w}$ je vždy alespoň ${displaystyle, 1 / e = 0,368 bodu}$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 ${displaystyle k}$ ú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 ${displaystyle ell}$ úspěchy. Pevnou spodní hranici pravděpodobnosti výhry získá Matsui & Ano 2014.

Matsui & Ano 2017 diskutovali o problému výběru ${displaystyle k}$ z posledního ${displaystyle ell}$ úspěchy a získal pevnou spodní hranici pravděpodobnosti výhry. Když ${displaystyle ell = k = 1,}$ problém je ekvivalentní Brussovu problému s pravděpodobností. Li ${displaystyle ell = kgeq 1,}$ problém je ekvivalentní problému v Bruss & Paindaveine 2000. Problém diskutovaný uživatelem Tamaki 2010 se získá nastavením ${displaystyle ell geq k = 1.}$

problém s výběrem odpovědí: Hráč je povolen ${displaystyle r}$ 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 ${displaystyle r = 2,3,4}$Problém s pravděpodobností ${displaystyle r = 2,3}$ 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 ${displaystyle (a_ {1}, a_ {2}, ..., a_ {r})}$, kde ${displaystyle a_ {1}$. První volba se použije u prvních kandidátů počínaje ${displaystyle a_ {1}}$th žadatel, a jakmile je použita první volba, druhá volba má být použita u prvního kandidáta počínaje ${displaystyle a_ {2}}$th žadatel, a tak dále.

Když ${displaystyle r = 2}$, Ano, Kakinuma a Miyoshi 2010 ukázal, že těsná dolní hranice pravděpodobnosti výhry se rovná ${displaystyle e ^ {- 1} + e ^ {- {frac {3} {2}}}.}$ Pro obecné kladné celé číslo ${displaystyle r}$, Matsui & Ano 2016 diskutovali o těsné spodní hranici pravděpodobnosti výhry ${displaystyle r = 3,4,5}$, těsné spodní hranice pravděpodobností výhry se rovná ${displaystyle e ^ {- 1} + e ^ {- {frac {3} {2}}} + e ^ {- {frac {47} {24}}}}$, ${displaystyle e ^ {- 1} + e ^ {- {frac {3} {2}}} + e ^ {- {frac {47} {24}}} + e ^ {- {frac {2761} {1152 }}}}$ a ${displaystyle e ^ {- 1} + e ^ {- {frac {3} {2}}} + e ^ {- {frac {47} {24}}} + e ^ {- {frac {2761} {1152 }}} + e ^ {- {frac {4162637} {1474560}}},}$ Pro další případy ${displaystyle r = 6, ..., 10}$viz Matsui & Ano 2016.

Viz také

• Kurzy
• Klinické hodnocení
• Rozšířený přístup
• Tajemník problém

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