Eine Erweiterung von Chernoff gebunden

12

Ich suche einen Verweis (kein Beweis, den ich machen kann) auf die folgende Erweiterung von Chernoff.

Lassen sind boolesche Zufallsvariablen, die nicht unbedingt unabhängig sind . Stattdessen ist garantiert, dass P r ( X i = 1 | C ) < p für jedes i und jedes Ereignis C ist , das nur von { X j | abhängt j i } .X1,..,XnPr(Xi=1|C)<piC{Xj|ji}

Natürlich möchte ich eine obere Grenze für .Pr(i[n]Xi>(1+λ)np)

Danke im Voraus!

neugierig
quelle

Antworten:

25

P(iSXi)p|S|S={i1,,i|S|}

P(iSXi)=P(Xi1=1)P(Xi2=1|Xi1=1)P(Xi|S|=1|Xi1,...,Xi|S|1=1)p|S|
http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf
Dana Moshkovitz
quelle
Danke für die Klarstellung! In der Tat ist ihr Zustand sowohl durch das, was ich habe, als auch durch negative Korrelationen impliziert. Es ist also in der Tat qualitativ stärker (ich habe diesen Punkt irgendwie verpasst, als ich Valentines Rede hörte). Nun wird der Beweis für das, was ich brauche, so kurz, dass ich meine Frage gerne als beantwortet markiere, vielen Dank !!
neugierig
3
Pr[Xi=1|X1,,Xi1]<p
7

Die nächsten Dinge, die mir in der Literatur bekannt sind, sind Erweiterungen von Chernoff-Grenzen zu negativ korrelierten Zufallsvariablen, z. B. siehe dies oder das . Formal könnte Ihre Bedingung ohne die negative Korrelation erfüllt werden, aber die Idee ist ähnlich.

Da Ihre Verallgemeinerung nicht schwer zu beweisen ist, könnte es sein, dass sich niemand darum gekümmert hat, sie aufzuschreiben.

Lev Reyzin
quelle
Sie haben Recht, das war auch das Nächste, was ich gefunden habe (in "Konzentration ... für die Analyse von ... Algorithmen"). Die Sache ist, dass mein Manuskript zu lang wird, ich würde gerne noch ein Spin-off vermeiden, wenn möglich. Wenn nicht, habe ich keine andere Wahl ...
neugierig
3
Dies ist, was
Anhänge
2
Hey Leute, das wurde schon mal bewiesen und ich habe in meiner Antwort einen Verweis gegeben (auf den Sie auch alle anderen relevanten Verweise finden können).
Dana Moshkovitz
Ups - großartig. Ihre Antwort ist mir irgendwie nicht aufgefallen!
Lev Reyzin
3

Eine alternative Referenz könnte Lemma 1.19 in B. Doerr, Analyse randomisierter Suchheuristiken: Werkzeuge aus der Wahrscheinlichkeitstheorie, Theorie randomisierter Suchheuristiken (A. Auger und B. Doerr, Hrsg.), World Scientific Publishing, 2011, S. 1- sein. 20.

In einfachen Worten zeigt es, wann Xich=1 mit wahrscheinlichkeit pich egal was du bedingst X1,,Xich-1 dann auf X1,,Xn erfüllen alle Chernoff-Hoeffding-Grenzen, die für unabhängige binäre Zufallsvariablen gelten Y.1,,Y.n mit erfolgswahrscheinlichkeit p1,,pn, beziehungsweise. Der Beweis ist elementar und das Ergebnis ist natürlich, also hatte wohl niemand das Bedürfnis, ihn aufzuschreiben.

Benjamin Doerr
quelle