Reverse Chernoff gebunden

31

Gibt es eine umgekehrte Chernoff-Grenze, die einschränkt, dass die Schwanzwahrscheinlichkeit mindestens so groß ist.

dh wenn X1,X2,,Xn unabhängige binomiale Zufallsvariablen sind und μ=E[i=1nXi] . Dann können wir für eine Funktion f beweisen, dass .Pr[i=1nXi(1+δ)μ]f(μ,δ,n)f

Ashwinkumar BV
quelle
1
Ihr Beispiel ist zu viel verlangt: mit p=n2/3 , ein Standard - Chernoff gebunden zeigt , dass Pr[|TS1|1.1n1/3] und Pr[|TS2|1.1n1/3] sind most exp(cn1/3) für einige c .
Colin McQuillan
Sie haben Recht, ich war verwirrt darüber, welcher Begriff in chernoff bound das Quadrat hat. Ich habe die Frage geändert, um eine schwächere Grenze widerzuspiegeln. Ich denke nicht, dass es mir bei meiner aktuellen Bewerbung helfen wird, aber es könnte aus anderen Gründen interessant sein.
Ashwinkumar BV

Antworten:

28

Hier ist ein expliziter Beweis dafür, dass eine Standard-Chernoff-Bindung für einen bestimmten Bereich der Parameter bis zu konstanten Faktoren im Exponenten eng ist. (Insbesondere, wenn die Variablen 0 oder 1 und 1 mit einer Wahrscheinlichkeit von 1/2 oder weniger und ϵ(0,1/2) sind und die Chernoff-Obergrenze kleiner als eine Konstante ist.)

Wenn Sie einen Fehler finden, lassen Sie es mich bitte wissen.

Lemma 1. (Enge der Chernoff-Grenze) Sei X der Durchschnitt von k unabhängigen 0/1-Zufallsvariablen (rv). Für jedes ϵ(0,1/2] und p(0,1/2] , vorausgesetzt, ϵ2pk3 ,

(i) Wenn jedes rv mit einer Wahrscheinlichkeit von höchstens , dann istp

Pr[X(1ϵ)p]  exp(9ϵ2pk).

(ii) Wenn jedes rv mit einer Wahrscheinlichkeit von mindestens , dann istp

Pr[X(1+ϵ)p]  exp(9ϵ2pk).

Beweis. Wir verwenden die folgende Beobachtung:

Behauptung 1. Wenn , dann 1k1(k)  1e2π(k)(kk)k

Beweis von Anspruch 1. Nach Stirlings Näherung ist wobeii!=2πi(i/e)ieλλ[1/(12i+1),1/12i].

Also ist , was ist mindestens QED(k)k!!(k)!

2πk(ke)k2π(e)  2π(k)(ke)kexp(112k+1112112(k))
  12π(k)(kk)ke1.

Beweis von Lemma 1 Teil (i). Ohne Allgemeingültigkeitsverlust sei angenommen, dass jede 0/1-Zufallsvariable in der Summe mit einer Wahrscheinlichkeit von genau . Hinweis entspricht der Summe , und .X pPr[X(1ϵ)p]i=0(1ϵ)pkPr[X=i/k]Pr[X=i/k]=(ki)pi(1p)ki

Fix . Die Terme in der Summe nehmen zu, also haben die Terme mit dem Index jeweils einen Wert von mindestens , also hat ihre Summe einen Gesamtwert von mindestens . Um den Beweis zu vervollständigen, zeigen wir, dass =(12ϵ)pk+1iPr[X=/k](ϵpk2)Pr[X=/k]

(ϵpk2)Pr[X=/k]  exp(9ϵ2pk).

Die Annahmen und ergeben , so dass die linke Seite oben mindestens . Verwendung von Anspruch 1, gebunden , ist dies wiederum mindestens , wo und ϵ2pk3ϵ1/2ϵpk623ϵpk(k)p(1p)k(k)ABA=23eϵpk/2πB=(k)(kk)kp(1p)k.

Zum Schluss zeigen wir und .Aexp(ϵ2pk)Bexp(8ϵ2pk)

Anspruch 2. Aexp(ϵ2pk)

Beweis von Anspruch 2. Die Annahmen und implizieren (i) .ϵ2pk3ϵ1/2pk12

Per Definition . Bis (i) . Somit ist (ii) .pk+1pk121.1pk

Einsetzen der rechten Seite von (ii) für in ergibt (iii) .AA23eϵpk/2.2π

Die Annahme impliziert , was mit (iii) (iv) ergibt .ϵ2pk3ϵpk3A23e3/2.2π0.1

Aus folgt, dass (v) .ϵ2pk3exp(ϵ2pk)exp(3)0.04

(iv) und (v) ergeben zusammen den Anspruch. QED

Anspruch 3. .Bexp(8ϵ2pk)

Beweis nach Anspruch 3. Fixiere so, dass . Die Wahl von impliziert , daher gilt die Behauptung so lange wie . Nimmt man jede Seite dieser letzteren Ungleichung und vereinfacht sie, so entspricht dies Wenn Sie und vereinfachen, entspricht dies δ=(1δ)pk
δ2ϵBexp(2δ2pk)1/

pk(k(1p)k)k/1  exp(2δ2pk).
=(1δ)pk
(1δ)(1+δp1p)1(1δ)p1  exp(2δ21δ).
Nimmt man den Logarithmus beider Seiten und verwendet zweimal , so gilt Die linke Seite oben vereinfacht sich zu , was weniger als weil . QEDln(1+z)z
δ+δp1p(1(1δ)p1)  2δ21δ.
δ2/(1p)(1δ)2δ2/(1δ)p1/2

Ansprüche 2 und 3 implizieren . Dies impliziert Teil (i) des Lemmas.ABexp(ϵ2pk)exp(8ϵ2pk)

Beweis von Lemma 1 Teil (ii). Ohne Beschränkung der Allgemeinheit annehmen , jede Zufallsvariable mit einer Wahrscheinlichkeit von genau .1p

Beachten Sie . Fix .Pr[X(1+ϵ)p]=i=(1ϵ)pknPr[X=i/k]^=(1+2ϵ)pk1

Die letzten Terme in der Summe ergeben mindestens , was mindestens . (Der Beweis dafür ist der gleiche wie für (i), außer dass durch und durch so dass .) QEDϵpk(ϵpk2)Pr[X=^/k]exp(9ϵ2pk)^δδ^^=(1+δ^)pk

Neal Young
quelle
Mehrere [Rechenfehler] - Gibt es eine Chance, sie zu beheben?
Aryeh
Diese mathematischen Ausdrücke werden normalerweise gut angezeigt. Aus irgendeinem Grund funktioniert der Befehl \ choose in mathjax nicht. Weder ist \ binom. ZB $ a \ wähle b $ gibt . Vermutlich ist dies ein Fehler in der Mathjax-Konfiguration. Hoffentlich wird es bald behoben. In der Zwischenzeit finden Sie Lemma 5.2 im Anhang von arxiv.org/pdf/cs/0205046v2.pdf oder cs.ucr.edu/~neal/Klein15Number . (ab)
Neal Young
22

Das Berry-Esseen-Theorem kann Schwanzwahrscheinlichkeits-Untergrenzen angeben, solange sie höher als .n1/2

Ein weiteres Werkzeug, das Sie verwenden können, ist die Paley-Zygmund-Ungleichung . Es impliziert , dass für eine beliebige gerade Zahl und jede reellwertigen Zufallsvariablen ,kX

Pr[|X|>=12(E[Xk])1/k]E[Xk]24E[X2k]

Zusammen mit dem Multinomialsatz kann für eine Summe von Rademacher-Zufallsvariablen Paley-Zygmund ziemlich starke Untergrenzen ergeben. Es funktioniert auch mit Randed-Independence-Zufallsvariablen. Zum Beispiel erhalten Sie leicht, dass die Summe von 4-fach unabhängigen Zufallsvariablen mit konstanter Wahrscheinlichkeit ist.Xnn±1Ω(n)

Sasho Nikolov
quelle
14

Wenn Sie in der Tat in der Lage sind, die Anzahl der Bernoulli-Versuche zu begrenzen (und nicht etwa die Anzahl der zufälligen Variablen), ist das Folgende ziemlich eng.

Schlammungleichheit *. Sei iid Draws aus einem Bernoulli-Rv mit , und sei die Ganzzahl gegeben. Wenn entweder (a) und oder (b) , dann wobei die cdf einer Standardnormalen ist.{Xi}i=1nE(X1)=pknp1/4npknpkn(1p)

Pr[iXik]1Φ(knpnp(1p)),
Φ

(Wenn man das Argument von als Transformation der Standardnormalen betrachtet, stimmt dies genau mit dem überein, was die CLT Ihnen sagt. Tatsächlich sagt es uns, dass Binomialzahlen, die die Bedingungen des Theorems erfüllen, ihre entsprechenden Gaußschen auf den oberen Schwänzen dominieren.)Φ

Ab hier können Sie Grenzen für , um etwas Schöneres zu erhalten. Zum Beispiel wird in Fellers erstem Buch im Abschnitt über Gauß'sche Verhältnisse für jedes dass wobei die Dichte einer Standardnormalen ist. Ähnliche Grenzen gibt es auch im Wikipedia-Artikel für "Q-Funktion".Φz>0

z1+z2φ(z)<1Φ(z)<1zφ(z),
φ

Anders als das und was andere Leute gesagt haben, können Sie auch versuchen, das Binomial direkt zu verwenden, vielleicht mit etwas Stirling.

(*) Einige neuere Aussagen über die Ungleichheit von Slud lassen einige dieser Bedingungen außer Acht. Ich habe die in Sluds Papier reproduziert.

matus
quelle
7

Der Satz von de Moivre-Laplace zeigt, dass Variablen wieNach einer geeigneten Normalisierung und unter bestimmten Bedingungen wird die Verteilung zu einer Normalverteilung konvergieren. Das reicht, wenn Sie konstante Untergrenzen wünschen.|TS1|

Für untere Schranken wie benötigen Sie ein etwas feineres Werkzeug. Hier ist ein Hinweis, den ich kenne (aber nur aus Versehen - ich hatte noch nie die Gelegenheit, eine solche Ungleichung selbst zu verwenden). Einige explizite untere Schranken für die Endwahrscheinlichkeiten von Binomialverteilungen sind in Theorem 1.5 des Buches Random Graphs von Béla Bollobás, Cambridge, 2. Auflage, angegeben, in dem auf eine Einführung in die Wahrscheinlichkeit und ihre Anwendungen von Feller und Foundations of Probability von Rényi verwiesen wird.nc

Colin McQuillan
quelle
4

Das verallgemeinerte Littlewood-Offord-Theorem ist nicht genau das, was Sie wollen, aber es gibt das, was ich als "umgekehrtes Chernoff" bezeichne, indem es zeigt, dass es unwahrscheinlich ist, dass die Summe der Zufallsvariablen in einen kleinen Bereich um einen bestimmten Wert fällt (einschließlich die Erwartung). Vielleicht wird es nützlich sein.

Formal lautet der Satz wie folgt.

Verallgemeinerter Littlewood-Offord-Satz : Sei und reelle Zahlen, so dass for und lassen unabhängige Zufallsvariablen sein, die die Werte Null und Eins haben. Nehmen wir für , dass für alle . Dann, für jedes , Wobei eine Konstante ist, die nur von abhängt .a1,,ans>0|ai|s1inX1,,Xn0<p12pPr[Xi=0]1p1inrR

Pr[ri=1naiXi<r+s]cpn
cpp
Lev Reyzin
quelle
3
Es kann für andere hilfreich sein zu wissen, dass diese Art von Ergebnis auch als "kleine Kugelungleichheit" bezeichnet wird und Nguyen und Vu eine hervorragende Umfrage haben. People.math.osu.edu/nguyen.1261/cikk/LO-survey.pdf . Meine Sichtweise hier unterscheidet sich geringfügig von Ihrer. Ich stelle mir einen "umgekehrten Chernoff" vor, der eine niedrigere Schätzung der Wahrscheinlichkeitsmasse des kleinen Balls um 0 ergibt. Ich stelle mir eine kleine Ballungleichung vor, die qualitativ besagt, dass die Wahrscheinlichkeit des kleinen Balls durch den Ball bei 0 maximiert wird Sense Reverse-Chernoff-Schranken sind in der Regel leichter zu beweisen als kleine Ballungleichungen.
Sasho Nikolov
3

Der Exponent in der Standard-Chernoff-Grenze, wie er in Wikipedia angegeben ist, ist eng für Zufallsvariablen mit einem Wert von 0/1. Lassen und lassen eine Folge von unabhängigen Zufallsvariablen , so dass für jedes , und . Dann für jede , 0<p<1X1,X2,iPr[Xi=1]=pPr[Xi=0]=1pε>0

2D(p+εp)nn+1Pr[i=1nXi(p+ε)n]2D(p+εp)n.

Hier ist , was die Kullback-Leibler-Divergenz zwischen Bernoulli-Zufall ist Variablen mit den Parametern und .D(xy)=xlog2(x/y)+(1x)log2((1x)/(1y))xy

Wie erwähnt, wird die obere Schranke in der obigen Ungleichung auf Wikipedia ( https://en.wikipedia.org/wiki/Chernoff_bound ) unter dem Namen "Chernoff-Hoeffding Theorem, additive Form" bewiesen . Die Untergrenze kann zB mit der "Methode der Typen" nachgewiesen werden. Siehe Lemma II.2 in [1]. Dies wird auch im klassischen Lehrbuch zur Informationstheorie von Cover und Thomas behandelt.

[1] Imre Csiszár: Die Methode der Typen. IEEE-Transaktionen zur Informationstheorie (1998). http://dx.doi.org/10.1109/18.720546

JWM
quelle
Es ist auch erwähnenswert, dass und für den allgemeinen Fall von es ist . Dies zeigt, dass bei die typische -Bindung scharf ist. (Und wenn für ). D(p+δpp)=p22pδ2+O(δ3)p=1/212δ2+O(δ4)δ=O(n1/3)eCδ2δ=O(n1/4)p=1/2
Thomas Ahle