Summe unabhängiger exponentieller Zufallsvariablen

12

Können wir ein scharfes Konzentrationsergebnis auf der Summe unabhängiger exponentieller Zufallsvariablen nachweisen, dh X1,Xr seien unabhängige Zufallsvariablen, so dass Pr(Xi<x)=1ex/λi . Sei Z=Xi . Können wir Grenzen der Form P r ( | Z - μ Z | > t ) < e - t beweisen ?Pr(|ZμZ|>t)<et2/(λi)2 . Dies folgt direkt, wenn wir die Varianzform der Chernoff-Grenzen verwenden und daher glaube ich, dass dies wahr ist, aber die Grenzen, die ich lese, erfordern eine Begrenztheit oder eine gewisse Abhängigkeit von der Begrenztheit der Variablen. Könnte jemand auf einen Hinweis auf das oben Gesagte hinweisen?

Gaul
quelle
Folgen Sie einfach dem Beweis von chernoff: Es ist einfach, das exponentielle Moment exponentieller Zufallsvariablen zu begrenzen.
Sasho Nikolov
Ich habe versucht, den Beweis von Chernoff zu wiederholen. Ich habe es für den einfacheren Fall getan, wenn alle λi=λ . Ich kann die Art von Beziehung, die ich suche, unter einer milden Bedingung von t<nλ . Tritt ein solcher Zustand natürlich auf oder liegt es an meiner nicht so guten Lösung?
NAg
3
Überprüfen Sie Lemma 2.8 hier eprint.iacr.org/2010/076.pdf
Sasho Nikolov
Ja das macht Sinn. Auch in ihrem Lemma haben sie eine Bedingung auf klein genug ist. Okay, dann scheint meine Lösung richtig zu sein. Vielen Dank für die Links und den Vorschlag. t
NAg
1
x Pr [ X i < x ] = 1 - e - λ i x λ - 2 iPr[Xi<x]=eλixxPr[Xi<x]=1eλixλi2

Antworten:

7

Nehmen wir zur Verdeutlichung an, dass das PDF des rv istXi

p(Xi=x)=12λieλi|x|.

Dies ist die Laplace-Verteilung oder die doppelte Exponentialverteilung. Seine Varianz ist . Das cdf ist2λi2

Pr[Xix]=112eλix
für .x0

Die Momenterzeugungsfunktion von istXi

E euXi=11u2/λi2,
für . Unter Verwendung dieser Tatsache und der Exponentialmomentmethode, die beim Beweis von Chernoff-Grenzen Standard ist, erhalten Sie, dass für und die folgende Ungleichung gilt|u|<λiX=iXiσ2=2iλi2

Pr[X>tσ]<et2/4,
solange . Eine detaillierte Ableitung finden Sie im Beweis von Lemma 2.8 dieses Papiers .t2σminiλi

Sasho Nikolov
quelle
Vielen Dank für die Antwort. In meiner Anwendung ist es jedoch nicht unbedingt wahr, dass . Man würde jedoch eine noch stärkere Konzentration erwarten, wenn . Wir können ein solches Ergebnis erhalten, wenn wir nicht die Näherung von die den Bereich von im Beweis einschränkt, aber die Analyse davon wird im Fall von unterschiedlichem unüberschaubar . Irgendwelche Vorschläge dazu? t>t2σminiλi1/(1-x)e c x tλt>2σminiλi1/(1x)ecxtλis
NAg
Dies wird ein kräftiges Handwinken sein, aber ich gehe davon aus, dass so große Werte von am wahrscheinlichsten auftreten, wenn nur eine kleine Anzahl von den Median von überschreitet um viel. Aber doppelte Exponentialvariablen haben einen schwereren Schwanz als Gaußsche, und eine kleine Anzahl von ihnen kann sich nicht so stark konzentrierenX iXXi|Xi|
Sasho Nikolov
2
Mir ist klar, dass das, was ich oben geschrieben habe, nicht klar ist: Ich erwarte, dass dieser Ausweg im Schwanz wie der Schwanz eines anderen rv aussieht der die Summe einer kleinen Anzahl von doppelt exponentiellen rv ist. Der Schwanz eines solchen sollte nicht sein subgaußsch. X ' X 'XXX
Sasho Nikolov
3

Wenn Sie für die Laplace-Distribution die Bernoulli-Bindung verwenden, können Sie schreiben

σ

EeuiXi=i11u2/λi211u2σ2/2,
wobei . Dann gibt die klassische Chernoff-Methode nachσ2=2iλi2

Pr[iXitσ]1+1+2t22e11+2t2{(et/2+1)e2tet2/2+t4/8.

Beachten Sie, dass diese Grenzen für uneingeschränkte Werte von und . Die Grenzen rechts zeigen die beiden möglichen Regime. Für kleine Werte von wir die "normale" Konzentration , während wir für große Werte von , was auch die CDF für ist eine einzelne verteilte Laplace-Variable.tλitet2/2te2t

Die -Bindung ermöglicht es Ihnen, zwischen den beiden Situationen zu interpolieren, aber ich vermute, dass man in fast allen Fällen entweder im großen oder im kleinen Lager fest sein wird.11+2t2tt

Für die Exponentialverteilung geben uns dieselben Techniken wobei . Daher ist Sie sehen also immer noch etwas normal aus, aber mit statt wie wir es uns erhofft haben. Ich weiß nicht, ob es möglich ist, eine Grenze in Bezug auf die Varianz zu erhalten. Sie könnten versuchen, zu studieren , aber es scheint nicht einfach zu sein, damit zu arbeiten.EeuiXi11uμμ=i1/λi

Pr[(iXi)μtμ](t+1)etet2/2+t3/3.
tμtσEeu(Xiμ)2
Thomas Ahle
quelle
Ich habe nicht die Zeit, die Details zu erarbeiten, aber ich bin zu 99,9% sicher, dass man eine Grenze für exponentiell verteilte Zufallsvariablen erhalten kann, die von der Varianz abhängt. Ihre momentan gebundene Erzeugungsfunktion sieht übermäßig locker aus.
Warren Schudy
@ Warren Schudy, was wäre dein Ansatz?
Thomas Ahle
Ich sehe zwei offensichtliche Ansätze: 1. Die zweite Grenze, die unter en.wikipedia.org/wiki/… aufgeführt ist, scheint zu funktionieren. 2. Finden Sie eine engere Grenze für die Momenterzeugungsfunktion.
Warren Schudy
@WarrenSchudy Die Bernstein-Grenze ergibt , aber nur für . Ich nehme an, das ähnelt Sashos Antwort. t σ min i λ i / 2Pr[iXitσ]et2/2tσminiλi/2
Thomas Ahle
Es ist unvermeidlich, dass Grenzen im Gaußschen Stil irgendwann aufhören. Sogar eine einzelne exponentiell verteilte Zufallsvariable hat schließlich dickere Schwänze als jede Gaußsche.
Warren Schudy