Chernoff für gewichtete Summen gebunden

14

Man betrachte , wobei lambda_i> 0 und Y_i als Standardnormal verteilt sind. Welche Art von Konzentrationsgrenzen kann man auf X als Funktion der (festen) Koeffizienten lambda_i nachweisen?X=ichλichY.ich2

Wenn alle lambda_i gleich sind, ist dies eine Chernoff-Grenze. Das einzige andere Ergebnis, das mir bekannt ist, ist ein Lemma aus einer Arbeit von Arora und Kannan ("Learning blend of arbitrary Gaussians", STOC'01, Lemma 13), das die Konzentration der Form , dh die Schranke hängt von der Summe der Quadrate der Koeffizienten ab.PrÖb(X<E[X]-t)<exp(-t2/(4ichλich2)

Der Beweis ihrer Deckspelze ist analog zum üblichen Beweis der Chernoff-Bindung. Gibt es andere "kanonische" solche Grenzen, oder eine allgemeine Theorie, welche Funktionen der Lambda_i so sind, dass ihre Größe eine gute exponentielle Konzentration gewährleistet (hier war die Funktion einfach die Summe der Quadrate)? Vielleicht ein allgemeines Maß für die Entropie?

Eine Standardreferenz für das Arora-Kannan-Lemma wäre auch großartig, wenn es existiert.

Thomas
quelle
Wie weit sind Sie bei der Reproduktion ihrer Bindung gekommen? Diese besondere Instanz der exponentiellen mgf-Methode scheint einige geschickte Grenzen und Fallanalysen zu erfordern.
Thomas Ahle

Antworten:

14

Das Buch von Dubhashi und Panconesi fasst viele solcher Schranken zusammen, die zahlreicher sind, als hier aufgeführt werden können. Wenn Sie nicht sofort darauf zugreifen können, gibt es eine Online-Umfrage zu Chernoff-ähnlichen Grenzen von Chung und Lu

Suresh Venkat
quelle
Danke, das sieht sehr gut aus. Insbesondere scheint Satz 3.5 der Chung- und Lu-Umfrage mit dem von mir angegebenen Arora-Kannan-Lemma identisch zu sein. Es ist natürlich, dass die Summe von lambda_i ^ 2 erscheint, da es einfach die Varianz von X ist.
Thomas
Die Verbindung zwischen Chung und Lu ist tot. Internet Archive hat es jedoch: web.archive.org/web/20070714095538/http://… . Der Titel lautet "Concentration Inequalities and Martingale Inequalities: A Survey" und die Autoren sind Fan Chung und Linyuan Lu.
Jbapple