Nierówność typu Chernoffa dla niezależnych zmiennych losowych parami

Nierówności typu Chernoffa służą do wykazania, że ​​prawdopodobieństwo, że suma niezależnych zmiennych losowych znacznie odbiega od wartości oczekiwanej, jest wykładniczo małe w wartości oczekiwanej i odchyleniu. Czy istnieje jakakolwiek nierówność typu Chernoffa dla dowolnej sumy niezależnych parami zmiennych losowych? Innymi słowy, czy istnieje wynik, który pokazuje, co następuje: prawdopodobieństwo, że suma par zmiennych niezależnych losowych odbiega od wartości oczekiwanej, jest wykładniczo mała w wartości oczekiwanej i odchyleniu?

Niezależność parowa nie wystarcza, aby typ Chernoffa był związany z oczekiwaniami.

Wynika to z faktu, że istnieje -size przestrzenie reprezentatywne n 0-1 zmiennych losowych, gdzie wszystkie zmienne są parami niezależne i każdy z nich jest zmienna jest jednorodny (jest to jeden z prawdopodobieństwem 1 / 2 ). Zatem oczekiwana wartość ich sumy wynosi n / 2 . Ponieważ jednak w przestrzeni próbki występują tylko p o l y ( n ) możliwe zdarzenia, nawet prawdopodobieństwo, że suma jest dokładnie określoną wartością v wynosi co najmniej 1 / p $poly(n)$$n$$1$$1/2$$n/2$$poly(n)$$v$ (stąd nie może być co najwyżej 1 / e x p ( n ) ).$1/poly(n)$$1/exp(n)$

Odniesienie do tej przykładowej konstrukcji przestrzeni znajduje się na stronach 11-12 w tej ankiecie .

Jeśli masz niezależność parami, możesz ograniczyć wariancję sumy, a tym samym uzyskać koncentrację związaną za pomocą nierówności Czebyszewa.

Istnieje wiele tego rodzaju wyników w książce Dubhashi-Panconesi . Jednym ze standardowych odniesień tego rodzaju jest praca Schmidta, Siegela i Srinivasana z 1993 r., Zatytułowana (odpowiednio): „ Granice Chernoffa-Hoeffdinga dla aplikacji o ograniczonej niezależności ”