Nierówność proroka

W teorii algorytmów online i optymalnego zatrzymywania nierówność proroka jest ograniczona wartością oczekiwaną procesu decyzyjnego, który obsługuje sekwencję losowych danych wejściowych ze znanych rozkładów prawdopodobieństwa , w stosunku do oczekiwanej wartości, którą można osiągnąć poprzez „ prorok”, który zna z wyprzedzeniem wszystkie dane wejściowe (a nie tylko ich rozkład). Nierówności te mają zastosowanie w teorii projektowania mechanizmów algorytmicznych i finansach matematycznych .

Pojedynczy przedmiot

Klasyczna jednoelementowa nierówność proroka została opublikowana przez Krengela i Suchestona (1978) , przypisując jej zwartą formę DJH (Benowi) Garlingowi. Dotyczy procesu $,$ którym sekwencja zmiennych $rozkładów$ ze . Kiedy pojawia się każdy $,$ decyzyjny musi zdecydować, czy go zaakceptować i zatrzymać proces, czy też go odrzucić i przejść do następnej zmiennej w sekwencji Wartością procesu jest pojedyncza akceptowana zmienna, jeśli taka istnieje, lub zero w przeciwnym razie. Można założyć, że wszystkie zmienne są nieujemne; w przeciwnym razie zastąpienie wartości ujemnych przez zero nie zmienia wyniku. Może to na przykład modelować sytuacje finansowe, w których zmiennymi są oferty zakupu niepodzielnego dobra po określonej cenie, a sprzedawca musi zdecydować, którą (jeśli w ogóle) ofertę przyjąć. Prorok, znając cały ciąg zmiennych, może oczywiście wybrać największą z nich, osiągając wartość ${\textstyle \max _{i}X_{i}}$ dla dowolnego konkretnego wystąpienia tego procesu i wartość oczekiwana mi $\textstyle \mathbb {E} [\max _{i }X_{i}]}$ . Nierówność proroka stwierdza istnienie algorytmu online dla tego procesu, którego oczekiwana wartość jest co najmniej o połowę mniejsza niż wartość proroka: ${\textstyle {\tfrac {1} {2}}\mathbb { E} [\max _{i}X_{i}]}$ . Żaden algorytm nie jest w stanie osiągnąć większej wartości oczekiwanej dla wszystkich rozkładów danych wejściowych.

Jedną z metod udowodnienia nierówności proroka pojedynczego elementu jest użycie „algorytmu progowego”, który ustawia parametr, $następnie$ akceptuje pierwszą zmienną losową, która jest co najmniej tak duża jak ${\ displaystyle \ tau}$ . Jeśli prawdopodobieństwo, że w tym procesie zostanie przyjęty element, $\ tau}$ $,$ jego oczekiwana wartość wynosi $displaystyle$ oczekiwana nadwyżka ponad jaką posiada wybrana zmienna (jeśli taka istnieje). Każda zmienna zostanie uwzględniona przez algorytm progowy z prawdopodobieństwem co ${ \textstyle \max(X_{i}-\tau ,0)}$ $,$ , $wniesie$ maksymalny do nadmiaru, więc zgodnie z liniowością oczekiwań oczekiwany nadmiar wynosi co najmniej

{\ Displaystyle \ mathbb {E} {\ Bigl [} \ suma _ {i} (1-p) \ max (X_ {i} - \ tau, 0) {\ Biggr]} \ geq (1-p) { \bigl (}\mathbb {E} [\max _{i}X_{i}]-\tau ).}

Ustawienie

textstyle

rozkładu

\max _{i}X_{i}}

, tak że

{\ displaystyle p = {\ tfrac {1 }

i dodanie do granicy oczekiwanego nadmiaru powoduje, że

\ displaystyle p \ tau

}

i

nawzajem ,

pokazując

, że dla tego ustawienia algorytm osiąga oczekiwaną wartość co najmniej

{\ Textstyle {\ tfrac {1} {2}} \ mathbb {E} [\ max _ {i} X_ {i}]}

. Inny próg,

{\ Textstyle \ tau = {\ tfrac {1} {2}} \ mathbb {E} [\ max _ {i} X_ {i}]}

, również osiąga co najmniej tę samą oczekiwaną wartość.

Uogólnienia

Znane są różne uogólnienia jednoelementowej nierówności proroka na inne scenariusze online i nazywane są one również nierównościami proroka.

Porównanie z analizą konkurencji

Nierówności proroka są związane z analizą konkurencyjną algorytmów online , ale różnią się na dwa sposoby. Po pierwsze, w większości analiz konkurencyjnych zakłada się najgorszego przypadku , wybrane tak, aby maksymalizować stosunek między wartością obliczoną a wartością optymalną, jaką można osiągnąć, mając wiedzę o przyszłości, podczas gdy w przypadku nierówności prognostycznych zakłada się pewną wiedzę o danych wejściowych i ich rozkładzie być znanym. Po drugie, aby osiągnąć określony współczynnik konkurencyjności , algorytm online musi działać w ramach tego stosunku optymalnej wydajności na wszystkich wejściach. Zamiast tego nierówność proroka ogranicza jedynie oczekiwaną wydajność, pozwalając niektórym sekwencjom wejściowym dawać gorszą wydajność, o ile średnia jest dobra.

Linki zewnętrzne

Matroid Prorok Nierówności i projekt mechanizmu , Unia Matroidów