Wahrscheinlichkeitsungleichungen

37

Ich suche nach einigen Wahrscheinlichkeitsungleichungen für Summen von unbegrenzten Zufallsvariablen. Ich würde mich sehr freuen, wenn mir jemand ein paar Gedanken machen könnte.

Mein Problem besteht darin, eine exponentielle Obergrenze für die Wahrscheinlichkeit zu finden, dass die Summe der unbegrenzten iid-Zufallsvariablen, die tatsächlich die Multiplikation von zwei iid-Gaußschen Variablen sind, einen bestimmten Wert überschreitet, dh , wobei , und iid aus generiert werden .X = Σ N i = 1 w i v i w i v i N ( 0 , σ )Pr[Xϵσ2N]exp(?)X=i=1NwiviwiviN(0,σ)

Ich habe versucht, die Chernoff-Grenze mit der Momenterzeugungsfunktion (MGF) zu verwenden. Die abgeleitete Grenze ist gegeben durch:

Pr[Xϵσ2N]minsexp(sϵσ2N)gX(s)=exp(N2(1+4ϵ21+log(1+4ϵ21)log(2ϵ2)))

wo ist die MGF von . Aber die Grenze ist nicht so eng. Das Hauptproblem bei meinem Problem ist, dass die Zufallsvariablen unbegrenzt sind und ich die Grenze der Höffding-Ungleichung leider nicht verwenden kann.gX(s)=(11σ4s2)N2X

Ich bin zu glücklich, wenn Sie mir helfen, eine enge exponentielle Grenze zu finden.

Farzad
quelle
3
Klingt nach einem Problem mit komprimierter Abtastung. Lesen Sie die Anmerkungen von R. Vershynin zur nichtasymptotischen Zufallsmatrixtheorie, insbesondere die Grenzen dessen, was er subexponentielle Zufallsvariablen nennt . Dann fängst du an. Wenn Sie weitere Hinweise benötigen, lassen Sie es uns wissen und ich werde versuchen, weitere Informationen zu veröffentlichen.
Kardinal
1
Es gibt mindestens ein paar Fragen und Antworten zu diesem Thema auf math.SE (Haftungsausschluss: einschließlich einer, an der ich teilgenommen habe).
Kardinal
1
Das Produkt hat als 'normales Produkt' eine Distribution. Ich glaube, der Mittelwert dieses Produkts ist Null und die Varianz ist wobei die Varianz von und . Für largeish können Sie den zentralen Grenzwertsatz verwenden, um die ungefähre Noralität von . Wenn Sie den Versatz der normalen Produktverteilung berechnen können, können Sie meines Erachtens das Berry-Esseen-Theorem anwenden, um die Konvergenzrate der CDF zu begrenzen. wiviσ4σ2wiviNX
Shabbychef
1
@shabbychef, Berry-Esseen hat eine ziemlich langsame Konvergenz, da es eine einheitliche Grenze über die Klasse aller Verteilungsfunktionen . F
Kardinal
4
@DilipSarwate: Entschuldigung, dass ich gerade Ihren Kommentar von vor einer Weile sehe. Ich denke, Sie interessieren sich vielleicht für das folgende kleine Papier, das ich auch ein paar Mal zu math.SE verlinkt habe: TK Phillips und R. Nelson (1995). Der Moment ist enger gebunden als Chernoffs Grenze für positiven Schwanz Wahrscheinlichkeiten , The American Statistician , Bd. 42, Nr. 2. 175-178.
Kardinal

Antworten:

1

Unter Verwendung der von Ihnen vorgeschlagenen Chernoff-Grenze für ein später angegebenes lautet wobei die zweite Ungleichung dank für jedes . Nehmen Sie nun und , die rechte Seite wird zu was für jedes ergibt .s1/(2σ2)

P[X>t]exp(st)exp((N/2)log(1σ4s2))exp(st+σ4s2N)
log(1x)2xx(0,1/2)t=ϵσ2Ns=t/(2σ4N)exp(t2/(4σ4N)=exp(ϵ2N/4)
P[X>ϵσ2N]exp(ϵ2N/4).
ϵ(0,1)

Eine andere Möglichkeit besteht darin, Konzentrationsunterschiede wie die Hanson-Wright-Ungleichung oder Konzentrationsunterschiede für das Gaußsche Chaos der Ordnung 2, die die Zufallsvariable umfassen, an der Sie interessiert sind, direkt anzuwenden.

Einfachere Annäherung ohne Verwendung der Momenterzeugungsfunktion

Nehmen Sie der Einfachheit halber (andernfalls können Sie die Skalierung durch Teilen durch ändern ).σ=1σ2

Schreib und . Sie fragen nach oberen Schranken für .v=(v1,...,vn)Tw=(w1,...,wn)TP(vTw>ϵN)

Sei. Dann ist durch die Unabhängigkeit von und unabhängig von mit der Verteilung mit Freiheitsgraden.Z=wTv/vZN(0,1)v,wv2Zχ2n

Nach Standardgrenzen für normale und zufällige Variablen ist Die Kombination mit der Vereinigungsgrenze ergibt eine obere Grenze für der Form .χ2

P(|Z|>ϵn/2)2exp(ϵ2n/4),P(v>2n)exp(n(21)2/2).
P(vTw>ϵN)2exp(ϵ2n/4)+exp(n(21)2/2)

jlewk
quelle
0

Die Bindung, die Sie erhalten, ist in der Reihenfolge als . Ich glaube nicht , Sie können für den allgemeinen viel besser . Von der Wikipedia - Seite über Produktvariablen die Verteilung von ist wo ist eine modifizierte Bessel - Funktion. Aus (10.25.3) in der DLMF-Funktionsliste , sime so dass für ausreichend groß was Ihnen keine subgaußsche Grenze geben wird.eϵϵϵwiviK0(z)/πK0K0(t)et/txP(wivi>x)xet/tdt

BookYourLuck
quelle