Odds algoritme - Odds algorithm

Den odds-algoritme er en matematisk metode til beregning optimale strategier for en klasse af problemer, der hører til domænet for optimale stoppe problemer. Deres løsning følger af oddsstrategien , og oddsstrategiens betydning ligger i dens optimalitet, som forklaret nedenfor.

Oddsalgoritmen gælder for en klasse af problemer kaldet last-succes- problemer. Formelt er formålet med disse problemer at maksimere sandsynligheden for i en sekvens af sekventielt observerede uafhængige begivenheder at identificere den sidste begivenhed, der opfylder et specifikt kriterium (en "specifik begivenhed"). Denne identifikation skal udføres på tidspunktet for observation. Ingen genbesøg af foregående observationer er tilladt. Normalt defineres en bestemt begivenhed af beslutningstageren som en begivenhed, der er af reel interesse med henblik på at "stoppe" for at tage en veldefineret handling. Sådanne problemer opstår i flere situationer.

Eksempler

To forskellige situationer eksemplificerer interessen for at maksimere sandsynligheden for at stoppe ved en sidst specifik begivenhed.

Antag at en bil annonceres til salg til højstbydende (bedste "tilbud"). Lad n potentielle købere svare og bede om at se bilen. Hver insisterer på en øjeblikkelig beslutning fra sælgeren om at acceptere budet eller ej. Definer et bud som interessant og kodet 1, hvis det er bedre end alle foregående bud, og ellers kodet 0. Budene danner en tilfældig sekvens på 0s og 1s. Kun 1'er interesserer sælgeren, som måske frygter, at hver efterfølgende 1 måske er den sidste. Det følger af definitionen, at den sidste 1 er det højeste bud. Maksimering af sandsynligheden for at sælge på den sidste 1 betyder derfor at maksimere sandsynligheden for at sælge bedst .
En læge, der bruger en særlig behandling, kan bruge koden 1 til en vellykket behandling, ellers 0. Lægen behandler en sekvens af n patienter på samme måde og ønsker at minimere enhver lidelse og behandle enhver lydhør patient i sekvensen. At stoppe på den sidste 1 i en sådan tilfældig rækkefølge på 0'er og 1'er ville nå dette mål. Da lægen ikke er nogen profet, er målet at maksimere sandsynligheden for at stoppe på sidste 1. (Se medfølende brug .)

Definitioner

Overvej en række uafhængige begivenheder . Associer med denne sekvens en anden sekvens med værdierne 1 eller 0. Her , kaldet en succes, står for begivenheden, at kth-observationen er interessant (som defineret af beslutningstageren) og for ikke-interessant. Vi observerer uafhængige tilfældige variabler sekventielt og ønsker at vælge den sidste succes. ${\ displaystyle n}$ ${\ displaystyle I_ {1}, \, I_ {2}, \, \ dots, \, I_ {n}}$ ${\ displaystyle \, I_ {k} = 1}$ ${\ displaystyle \, I_ {k} = 0}$ ${\ displaystyle I_ {1}, \, I_ {2}, \, \ dots, \, I_ {n}}$

Lad være sandsynligheden for, at kth-begivenheden er interessant. Yderligere lad og .Bemærk, der repræsenterer oddsene for, at kth-begivenheden viser sig at være interessant, og forklarer navnet på oddsalgoritmen. ${\ displaystyle \, p_ {k} = P (\, I_ {k} \, = 1)}$ ${\ displaystyle \, q_ {k} = \, 1-p_ {k}}$ ${\ displaystyle \, r_ {k} = p_ {k} / q_ {k}}$ ${\ displaystyle \, r_ {k}}$

Algoritmisk procedure

Oddsalgoritmen opsummerer oddsene i omvendt rækkefølge

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

indtil denne sum når eller overstiger værdien 1 for første gang. Hvis dette sker ved indeks s , gemmer det s og den tilsvarende sum

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

Hvis summen af odds ikke når 1, indstiller den s = 1. Samtidig beregnes den

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

Outputtet er

${\ displaystyle \, s}$ , stoppetærsklen
${\ displaystyle \, w = Q_ {s} R_ {s}}$ , vindersandsynligheden.

Odds-strategi

Oddsstrategien er reglen om at observere begivenhederne efter hinanden og stoppe ved den første interessante begivenhed fra indeks s og fremefter (hvis nogen), hvor s er stoppetærsklen for output a.

Betydningen af oddsstrategien og dermed oddsalgoritmen ligger i følgende odds-sætning.

Odds sætning

Oddssætningen siger det

Oddsstrategien er optimal , dvs. den maksimerer sandsynligheden for at stoppe på den sidste 1.
Vindersandsynligheden for oddsstrategien er lig ${\ displaystyle \, w = Q_ {s} R_ {s}}$
Hvis vindersandsynligheden altid er mindst , og denne nedre grænse er bedst mulig . ${\ displaystyle \, R_ {s} \ geq \, 1}$ ${\ displaystyle \, w}$ ${\ displaystyle \, 1 / e = 0,368 \ dots}$

Funktioner

Oddsalgoritmen beregner den optimale strategi og den optimale vindersandsynlighed på samme tid. Antallet af operationer for oddsalgoritmen er også (sub) lineær i n. Derfor kan ingen hurtigere algoritme muligvis eksistere for alle sekvenser, således at oddsalgoritmen samtidig er optimal som en algoritme.

Kilder

Bruss 2000 udtænkte den ulige algoritme og opfandt sit navn. Det er også kendt som Bruss-algoritme (strategi). Gratis implementeringer kan findes på internettet.

Ansøgninger

Ansøgninger strækker sig fra medicinske spørgsmål i kliniske forsøg med salgsproblemer, sekretærproblemer , porteføljevalg , (envejs) søgestrategier, bane problemer og parkeringsproblemer til problemer i online vedligeholdelse og andre.

Der eksisterer i samme ånd et Odds-sætning til kontinuerlige ankomstprocesser med uafhængige trin som Poisson-processen ( Bruss 2000 ). I nogle tilfælde er oddsene ikke nødvendigvis kendt på forhånd (som i eksempel 2 ovenfor), så anvendelsen af oddsalgoritmen ikke er direkte mulig. I dette tilfælde kan hvert trin bruge sekventielle estimater af oddsene. Dette er meningsfuldt, hvis antallet af ukendte parametre ikke er stort sammenlignet med antallet n af observationer. Spørgsmålet om optimitet er dog mere kompliceret og kræver yderligere undersøgelser. Generaliseringer af oddsalgoritmen giver mulighed for forskellige belønninger for ikke at stoppe og forkerte stop samt erstatte uafhængighedsantagelser med svagere (Ferguson (2008)).

Variationer

Bruss & Paindaveine 2000 diskuterede et problem med at udvælge de sidste succeser. ${\ displaystyle k}$

Tamaki 2010 viste sig at være et multiplikativ odds sætning, der beskæftiger sig med et problem med at stoppe ved en af de sidste succeser. En stram nedre grænse for vindersandsynlighed opnås af Matsui & Ano 2014 . ${\ displaystyle \ ell}$

Matsui & Ano 2017 diskuterede et problem med at udvælge blandt de sidste succeser og opnåede en tæt nedre grænse for vindersandsynlighed. Når problemet svarer til Bruss 'oddsproblem. Hvis problemet svarer til det i Bruss & Paindaveine 2000 . Et problem diskuteret af Tamaki 2010 opnås ved at indstille ${\ displaystyle k}$ ${\ displaystyle \ ell}$ ${\ displaystyle \ ell = k = 1,}$ ${\ displaystyle \ ell = k \ geq 1,}$ ${\ displaystyle \ ell \ geq k = 1.}$

multiple choice problem : En spiller har tilladte valg, og han vinder, hvis et valg er den sidste succes. For problem med klassisk sekretær drøftede Gilbert & Mosteller 1966 sagerne . Oddsproblemet med diskuteres af Ano, Kakinuma & Miyoshi 2010 . For yderligere tilfælde af oddsproblem, se Matsui & Ano 2016 . ${\ displaystyle r}$ ${\ displaystyle r = 2,3,4}$ ${\ displaystyle r = 2,3}$

En optimal strategi tilhører den klasse af strategier, der er defineret af et sæt tærskelværdier , hvor . Førstevalg skal bruges på de første kandidater, der starter med ansøgeren, og når førstevalget er brugt, skal andet valg bruges på den første kandidat, der starter med ansøgeren, og så videre. ${\ displaystyle (a_ {1}, a_ {2}, ..., a_ {r})}$ ${\ displaystyle a_ {1} <a_ {2} <\ cdots <a_ {r}}$ ${\ displaystyle a_ {1}}$ ${\ displaystyle a_ {2}}$

Når , Ano, Kakinuma & Miyoshi 2010 viste, at den stramme nedre grænse af win sandsynlighed er lig med For generel positivt heltal , Matsui & Ano 2016 drøftede den stramme nedre grænse af win sandsynlighed. Når , stram nedre grænser for win sandsynligheder er lig med , og henholdsvis. For yderligere sager , se Matsui & Ano 2016 . ${\ displaystyle r = 2}$ ${\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}}.}$ ${\ displaystyle r}$ ${\ displaystyle r = 3,4,5}$ ${\ 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}}}}$ ${\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} + e ^ {- {\ frac {47} {24}}} + e ^ {- {\ frac { 2761} {1152}}} + e ^ {- {\ frac {4162637} {1474560}}},}$ ${\ displaystyle r = 6, ..., 10}$