Profetens ojämlikhet

I teorin om onlinealgoritmer och optimalt stopp är en profetojämlikhet en gräns för det förväntade värdet av en beslutsprocess som hanterar en sekvens av slumpmässiga indata från kända sannolikhetsfördelningar , i förhållande till det förväntade värdet som skulle kunna uppnås med en " profet" som känner till alla ingångar (och inte bara deras distributioner) i förväg. Dessa ojämlikheter har tillämpningar i teorin om algoritmisk mekanismdesign och matematisk finansiering .

Enstaka föremål

Den klassiska ojämlikheten i profeten med ett föremål publicerades av Krengel & Sucheston (1978), och krediterade DJH (Ben) Garling sin strama form. Det handlar om en process där en sekvens av slumpvariabler $X_{i}$ kommer från kända distributioner ${\mathcal {D}}_{i}$ . När varje $X_{i}$ anländer måste beslutsprocessen bestämma om den ska accepteras och stoppa processen, eller om den ska avvisas och gå vidare till nästa variabel i sekvensen. Värdet på processen är den enda accepterade variabeln, om det finns en, eller noll annars. Det kan antas att alla variabler är icke-negativa; Annars förändras inte resultatet av att ersätta negativa värden med noll. Detta kan till exempel modellera ekonomiska situationer där variablerna är erbjudanden om att köpa någon odelbar vara till ett visst pris, och säljaren måste bestämma vilket (om något) erbjudande som ska accepteras. En profet, som känner till hela sekvensen av variabler, kan uppenbarligen välja den största av dem, och uppnå värdet ${\textstyle \max _{i}X_{i}}$ för varje specifik instans av denna process, och förväntat värde ${\textstyle \mathbb {E} [\max _{i}X_{i}]}$ . Profetens ojämlikhet anger att det finns en onlinealgoritm för denna process vars förväntade värde är minst hälften av profetens: ${\textstyle {\tfrac {1}{2}}\mathbb { E} [\max _{i}X_{i}]}$ . Ingen algoritm kan uppnå ett större förväntat värde för alla distributioner av indata.

En metod för att bevisa ojämlikheten i enstaka objekt är att använda en "tröskelalgoritm" som ställer in en parameter $\tau$ och sedan accepterar den första slumpmässiga variabeln som är minst lika stor som $\tau$ . Om sannolikheten att denna process accepterar ett objekt är $p$ , då är dess förväntade värde $p\tau$ plus det förväntade överskottet över $\tau$ att den valda variabeln (om det finns är en) har. Varje variabel $X_{i}$ kommer att beaktas av tröskelalgoritmen med sannolikhet minst ${\displaystyle 1-p} ,$ och om den övervägs kommer den att bidra med ${ \textstyle \max(X_{i}-\tau ,0)}$ till överskottet, så genom förväntanslinjäritet är det förväntade överskottet minst

$$\mathbb {E} {\Bigl [}\sum _{i}(1-p)\max(X_{i}-\tau ,0){\Bigr ]}\geq (1-p){ \bigl (}\mathbb {E} [\max _{i}X_{i}]-\tau ).$$

Inställning av $\tau$ till medianen för fördelningen av ${\textstyle \max _{i}X_{i}} ,$ så att $p={\tfrac {1 }{2}}$ , och lägga till $p\tau$ till denna gräns för förväntat överskott, orsakar $p\tau$ och $( 1-p)(-\tau )$ termer för att ta bort varandra, vilket visar att för denna inställning av $\tau$ uppnår tröskelalgoritmen ett förväntat värde på minst ${\ textstil {\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$ . En annan tröskel, ${\textstyle \tau ={\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$ , uppnår också åtminstone samma förväntade värde.

Generaliseringar

Olika generaliseringar av profetojämlikheten med en enda punkt till andra onlinescenarier är kända, och kallas även profetojämlikheter.

Jämförelse med konkurrensanalys

Profetens ojämlikheter är relaterade till konkurrensanalys av onlinealgoritmer, men skiljer sig på två sätt. För det första antar mycket av konkurrensanalyser värsta tänkbara indata, valda för att maximera förhållandet mellan det beräknade värdet och det optimala värdet som kunde ha uppnåtts med kunskap om framtiden, medan det för profetojämlikheter antas viss kunskap om indata, dess fördelning, att vara känd. Och för det andra, för att uppnå ett visst konkurrensförhållande måste en onlinealgoritm prestera inom det förhållandet av optimal prestanda på alla ingångar. Istället begränsar en profetojämlikhet bara prestandan i förväntan, vilket gör att vissa inmatningssekvenser kan ge sämre prestanda så länge som genomsnittet är bra.

externa länkar

• Matroid Profet Ojämlikheter och Mechanism Design , The Matroid Union