Algoritmul cotelor - Odds algorithm

Cote-Algoritmul este o metodă matematică de calcul a strategiilor optime pentru o clasă de probleme care aparțin domeniului optim de oprire probleme. Soluția lor rezultă din strategia-cote , iar importanța strategiei-cote constă în optimitatea acesteia, așa cum se explică mai jos.

Algoritmul cotei se aplică unei clase de probleme numite probleme de ultimul succes . În mod formal, obiectivul acestor probleme este de a maximiza probabilitatea de a identifica într-o secvență de evenimente independente observate secvențial ultimul eveniment care îndeplinește un criteriu specific (un „eveniment specific”). Această identificare trebuie făcută în momentul observării. Nu este permisă revizuirea observațiilor precedente. De obicei, un eveniment specific este definit de factorul de decizie ca un eveniment care prezintă un adevărat interes în vederea „opririi” de a lua o acțiune bine definită. Astfel de probleme sunt întâlnite în mai multe situații.

Exemple

Două situații diferite exemplifică interesul pentru maximizarea probabilității de oprire la un ultim eveniment specific.

Să presupunem că o mașină este promovată spre vânzare către cel mai mare ofertant (cea mai bună „ofertă”). Să nu răspundă potențialilor cumpărători și să ceară să vadă mașina. Fiecare insistă asupra unei decizii imediate din partea vânzătorului de a accepta sau nu oferta. Definiți o sumă licitată ca interesantă și codificați 1 dacă este mai bună decât toate ofertele precedente și codificați 0 altfel. Ofertele vor forma o secvență aleatorie de 0s și 1s. Doar 1 interesează vânzătorul, care se poate teme că fiecare 1 succesiv ar putea fi ultimul. Din definiție rezultă că ultima 1 este cea mai mare ofertă. Maximizarea probabilității de a vinde pe ultimele 1 înseamnă, prin urmare, maximizarea probabilității de a vinde cel mai bine .
Un medic, utilizând un tratament special, poate folosi codul 1 pentru un tratament de succes, 0 altfel. Medicul tratează o secvență de n pacienți în același mod și dorește să minimizeze orice suferință și să trateze fiecare pacient receptiv din secvență. Oprirea pe ultimul 1 într-o astfel de secvență aleatorie de 0 și 1 ar atinge acest obiectiv. Deoarece medicul nu este profet, obiectivul este de a maximiza probabilitatea de a se opri pe ultimele 1. (A se vedea Utilizarea cu compasiune .)

Definiții

Luați în considerare o succesiune de evenimente independente . Asociați cu această secvență o altă secvență cu valorile 1 sau 0. Aici , numită succes, reprezintă evenimentul în care a k-a observație este interesantă (așa cum este definită de factorul de decizie) și pentru neinteresantă. Observăm secvențial variabile aleatoare independente și dorim să selectăm ultimul 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}}$

Fie probabilitatea ca al cincilea eveniment să fie interesant. În continuare, să luăm și. Notă care reprezintă șansele celui de-al cincilea eveniment care sa dovedit a fi interesant, explicând numele algoritmului de șanse. ${\ displaystyle \, p_ {k} = P (\, I_ {k} \, = 1)}$ ${\ displaystyle \, q_ {k} = \, 1-p_ {k}}$ ${\ displaystyle \, r_ {k} = p_ {k} / q_ {k}}$ ${\ displaystyle \, r_ {k}}$

Procedura algoritmică

Algoritmul cote rezumă cotele în ordine inversă

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

până când această sumă atinge sau depășește valoarea 1 pentru prima dată. Dacă acest lucru se întâmplă la indexul s , se salvează s și suma corespunzătoare

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

Dacă suma cotelor nu ajunge la 1, se stabilește s = 1. În același timp calculează

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

Ieșirea este

${\ displaystyle \, s}$ , pragul de oprire
${\ displaystyle \, w = Q_ {s} R_ {s}}$ , probabilitatea de câștig.

Cota-strategie

Strategia de cote este regula de a observa evenimentele unul după altul și de a opri primul eveniment interesant de la indexul s mai departe (dacă există), unde s este pragul de oprire a ieșirii a.

Importanța strategiei odds și, prin urmare, a algoritmului odds, stă în următoarea teoremă odds.

Teorema cotelor

Teorema cotelor afirmă că

Strategia de cote este optimă , adică maximizează probabilitatea de oprire pe ultima 1.
Probabilitatea de câștig a strategiei cote este egală ${\ displaystyle \, w = Q_ {s} R_ {s}}$
Dacă , probabilitatea de câștig este întotdeauna cel puțin , iar această limită inferioară este cel mai bine posibilă . ${\ displaystyle \, R_ {s} \ geq \, 1}$ ${\ displaystyle \, w}$ ${\ displaystyle \, 1 / e = 0,368 \ dots}$

Caracteristici

Algoritmul cote calculează strategia optimă și probabilitatea optimă de câștig în același timp. De asemenea, numărul de operații al algoritmului cote este (sub) liniar în n. Prin urmare, nu poate exista un algoritm mai rapid pentru toate secvențele, astfel încât algoritmul cote este, în același timp, optim ca un algoritm.

Surse

Bruss 2000 a conceput algoritmul ciudat și i-a inventat numele. Este, de asemenea, cunoscut sub numele de algoritm Bruss (strategie). Implementări gratuite pot fi găsite pe web.

Aplicații

Aplicațiile ajung de la întrebări medicale în studiile clinice la probleme de vânzări, probleme de secretar , selectarea portofoliului , strategii de căutare (într-un singur sens), probleme de traiectorie și de parcare, până la probleme de întreținere on-line și altele.

Există, în același spirit, o Teoremă-Cote pentru procesele de sosire în timp continuu cu creșteri independente, cum ar fi procesul Poisson ( Bruss 2000 ). În unele cazuri, cotele nu sunt neapărat cunoscute în avans (ca în Exemplul 2 de mai sus), astfel încât aplicarea algoritmului cote nu este direct posibilă. În acest caz, fiecare pas poate utiliza estimări secvențiale ale cotelor. Acest lucru este semnificativ, dacă numărul parametrilor necunoscuți nu este mare în comparație cu numărul n de observații. Cu toate acestea, problema optimității este mai complicată și necesită studii suplimentare. Generalizările algoritmului cote permit recompense diferite pentru eșecul opririi și opririle greșite, precum și înlocuirea ipotezelor de independență cu cele mai slabe (Ferguson (2008)).

Variații

Bruss & Paindaveine 2000 au discutat despre o problemă a selectării ultimelor succese. ${\ displaystyle k}$

Tamaki 2010 s-a dovedit a fi o teoremă a cotelor multiplicative care tratează o problemă a opririi la oricare dintre ultimele succese. O limită inferioară strânsă a probabilității de câștig este obținută de Matsui & Ano 2014 . ${\ displaystyle \ ell}$

Matsui & Ano 2017 au discutat o problemă a selectării dintre ultimele succese și au obținut o limită inferioară strânsă a probabilității de câștig. Când problema este echivalentă cu problema cotelor lui Bruss. Dacă problema este echivalentă cu cea din Bruss & Paindaveine 2000 . O problemă discutată de Tamaki 2010 este obținută prin setare ${\ displaystyle k}$ ${\ displaystyle \ ell}$ ${\ displaystyle \ ell = k = 1,}$ ${\ displaystyle \ ell = k \ geq 1,}$ ${\ displaystyle \ ell \ geq k = 1.}$

problemă cu alegere multiplă : unui jucător i se permit alegeri și câștigă dacă orice alegere este ultimul succes. Pentru problema secretarului clasic, Gilbert & Mosteller 1966 au discutat cazurile . Problema cu cotele este discutată de Ano, Kakinuma și Miyoshi 2010 . Pentru alte cazuri de probleme de cote, consultați Matsui & Ano 2016 . ${\ displaystyle r}$ ${\ displaystyle r = 2,3,4}$ ${\ displaystyle r = 2,3}$

O strategie optimă aparține clasei de strategii definite de un set de numere de prag , unde . Prima alegere trebuie utilizată pentru primii candidați începând cu cel care solicită și, odată ce prima alegere este utilizată, a doua alegere trebuie să fie utilizată pentru primul candidat care începe cu cel care solicită și așa mai departe. ${\ displaystyle (a_ {1}, a_ {2}, ..., a_ {r})}$ ${\ displaystyle a_ {1} <a_ {2} <\ cdots <a_ {r}}$ ${\ displaystyle a_ {1}}$ ${\ displaystyle a_ {2}}$

Când , Ano, Kakinuma & Miyoshi 2010 au arătat că limita inferioară strânsă a probabilității de câștig este egală cu Pentru întregul pozitiv general , Matsui și Ano 2016 au discutat despre limita inferioară strânsă a probabilității de câștig. Atunci când , strâns limite inferioare de probabilități de câștig sunt egale , și respectiv. Pentru alte cazuri , a se vedea 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}$