Luka korelacyjna

W programowaniu stochastycznym luka korelacji to najgorszy przypadek stosunku między kosztem, gdy zmienne losowe są skorelowane z kosztem, gdy zmienne losowe są niezależne .

Jako przykład rozważmy następujący problem optymalizacyjny. Nauczyciel chce wiedzieć, czy przyjść na zajęcia, czy nie. Jest n potencjalnych studentów. Dla każdego ucznia istnieje prawdopodobieństwo 1/ n , że uczeń będzie uczęszczał na zajęcia. Jeśli przynajmniej jeden uczeń uczęszcza, wtedy musi przyjść nauczyciel, a jego koszt wynosi 1. Jeśli żaden uczeń nie przychodzi, nauczyciel może zostać w domu, a jego koszt wynosi 0. Celem nauczyciela jest zminimalizowanie jego kosztów. Jest to problem programowania stochastycznego, ponieważ ograniczenia nie są znane z góry – znane są tylko ich prawdopodobieństwa. Teraz są dwa przypadki dotyczące korelacji między uczniami:

$są ze sobą skorelowani: każdy$ czy przyjść na zajęcia, czy nie, rzucając monetą z prawdopodobieństwem niezależnie od innych. Oczekiwany koszt w tym przypadku to ${\ Displaystyle 1- (1-1/n) ^ {n} \ około 1-1/e}$ . ^{[ wymagane wyjaśnienie ]}
Przypadek 2: uczniowie są skorelowani: jeden uczeń jest wybierany losowo i przychodzi na zajęcia, podczas gdy pozostali zostają w domu. Zauważ, że prawdopodobieństwo przyjścia każdego ucznia nadal wynosi ${\ displaystyle 1/n}$ . Jednak teraz koszt wynosi 1.

Luka korelacyjna to koszt w przypadku nr 2 podzielony przez koszt w przypadku nr 1, czyli ${\ Displaystyle e / (e-1)}$ .

udowodnić, że luka korelacji jest ograniczona w kilku przypadkach. Na przykład, gdy funkcja kosztu jest submodułową funkcją zbioru (jak w powyższym przykładzie), luka korelacji wynosi co najwyżej (więc powyższy przykład to ${\ Displaystyle e / (e-1)}$ najgorszy przypadek).

Górna granica luki korelacji implikuje górną granicę straty wynikającej z ignorowania korelacji. Załóżmy na przykład, że mamy problem programowania stochastycznego z submodułową funkcją kosztu. Znamy krańcowe prawdopodobieństwa zmiennych, ale nie wiemy, czy są one skorelowane, czy nie. $,$ jakby zmienne były niezależne, wynikowe .

Aplikacje

Luka korelacji została wykorzystana do powiązania utraty przychodów w przypadku zastosowania ceny optymalnej pod względem bayesowskim zamiast aukcji optymalnej pod względem bayesowskim .

Zobacz też