Chernoff wyznaczył sumy ważone

Rozważ , gdzie lambda_i> 0 i Y_i są rozłożone jako normalna norma. Jakie granice koncentracji można udowodnić na X, jako funkcję (stałych) współczynników lambda_i? $X = \sum_i \lambda_i Y_i^2$

Jeśli wszystkie lambda_i są równe, oznacza to ograniczenie Chernoffa. Jedyny inny wynik, jaki znam, to lemat z pracy Arory i Kannana („Uczenie się mieszanin arbitralnych Gaussów”, STOC'01, Lemma 13), który dowodzi koncentracji formy , tzn. Granica zależy od sumy kwadratów współczynników. $Prob(X < E[X] - t) < exp(-t^2/(4 \sum_i \lambda_i^2)$

Dowód ich lematu jest analogiczny do zwykłego dowodu związanego z Chernoffem. Czy istnieją inne „kanoniczne” takie granice, czy też ogólna teoria, które funkcje lambda są takie, że ich wielkość zapewnia dobrą wykładniczą koncentrację (tutaj funkcja była po prostu sumą kwadratów)? Może jakaś ogólna miara entropii?

Bardziej standardowe odniesienie do lematu Arora-Kannana byłoby również świetne, jeśli istnieje.

chernoff-bound Tomasz
źródło

Jak daleko posunąłeś się w odtwarzaniu ich granic? Ten szczególny przykład wykładniczej metody mgf wydaje się wymagać pewnych sprytnych granic i analizy przypadku.

Thomas Ahle,

Odpowiedzi:

Książka Dubhashiego i Panconesi zawiera wiele takich granic, liczniejszych, niż można tu wymienić. Jeśli masz trudności z natychmiastowym dostępem, dostępna jest internetowa ankieta na temat granic podobnych do Chernoffa autorstwa Chunga i Lu

Suresh Venkat
źródło

Dzięki, to wygląda bardzo dobrze. W szczególności Twierdzenie 3.5 z ankiety Chunga i Lu wydaje się być identyczne z lematem Arory-Kannana, o którym mówiłem. Pojawienie się sumy lambda_i ^ 2 jest naturalne, ponieważ jest to po prostu wariant X.

Thomas

Połączenie Chung i Lu nie działa. Jednak w Archiwum internetowym jest to: web.archive.org/web/20070714095538/http://… . Tytuł brzmi „Nierówności w koncentracji i nierówności w Martingale: ankieta”, a autorami są Fan Chung i Linyuan Lu.

jbapple,