Ta odpowiedź ciągle mutuje. Obecna wersja nie odnosi się do dyskusji, którą prowadziłem z @cardinal w komentarzach (chociaż dzięki tej dyskusji na szczęście zdałem sobie sprawę, że podejście warunkowe nigdzie nie prowadziło).
Do tej próby wykorzystam inną część oryginalnego artykułu Hoeffdinga z 1963 roku , mianowicie rozdział 5 „Sumy zależnych zmiennych losowych”.
Ustaw
Wi≡Yi∑ni=1Yi,∑i=1nYi≠0,∑i=1nWi=1,n≥2
podczas gdy ustawiamy jeśli .Wi=0∑ni=1Yi=0
Mamy więc zmienną
Zn=∑i=1nWiXi,E(Zn)≡μn
Interesuje nas prawdopodobieństwo
Pr(Zn≥μn+ϵ),ϵ<1−μn
Podobnie jak w przypadku wielu innych nierówności, Hoeffding rozpoczyna swoje rozumowanie od stwierdzenia, że
i to
Pr(Zn≥μn+ϵ)=E[1{Zn−μn−ϵ≥0}]
1{Zn−μn−ϵ≥0}≤exp{h(Zn−μn−ϵ)},h>0
W przypadku zmiennych zależnych jako Hoeffding wykorzystujemy fakt, że i wywołujemy nierówność Jensena dla funkcji wykładniczej (wypukłej), aby napisać∑ni=1Wi=1
ehZn=exp{h(∑i=1nWiXi)}≤∑i=1nWiehXi
i łączenie wyników, aby dojść do
Pr(Zn≥μn+ϵ)≤e−h(μn+ϵ)E[∑i=1nWiehXi]
Koncentrując się na naszym przypadku, ponieważ i są niezależne, wartości oczekiwane można rozdzielić,WiXi
Pr(Zn≥μn+ϵ)≤e−h(μn+ϵ)∑i=1nE(Wi)E(ehXi)
W naszym przypadku to iid Bernoullis z parametrem , a jest ich wspólną funkcją generowania momentu w , . WięcXiθE[ehXi]hE[ehXi]=1−θ+θeh
Pr(Zn≥μn+ϵ)≤e−h(μn+ϵ)(1−θ+θeh)∑i=1nE(Wi)
Otrzymujemy minimalizując RHS w odniesieniu doh
eh∗=(1−θ)(μn+ϵ)θ(1−μn−ϵ)
Włączając go w nierówność i manipulując, uzyskujemy
Pr(Zn≥μn+ϵ)≤(θμn+ϵ)μn+ϵ⋅(1−θ1−μn−ϵ)1−μn−ϵ∑i=1nE(Wi)
podczas
Pr(Zn≥θ+ϵ)≤(θθ+ϵ)θ+ϵ⋅(1−θ1−θ−ϵ)1−θ−ϵ∑i=1nE(Wi)
Hoeffding to pokazuje
(θθ+ϵ)θ+ϵ⋅(1−θ1−θ−ϵ)1−θ−ϵ≤e−2ϵ2
Dzięki uprzejmości OP (dzięki, byłem już trochę wyczerpany ...)
∑i=1nE(Wi)=1−1/2n
Wreszcie „podejście zmiennych zależnych” daje nam
Pr(Zn≥θ+ϵ)≤(1−12n)e−2ϵ2≡BD
Porównajmy to z ograniczeniami kardynała, opartymi na transformacji „niezależności”, . Aby nasza więź była ściślejsza, potrzebujemyBI
BD=(1−12n)e−2ϵ2≤e−nϵ2/2=BI
⇒2n−12n≤exp{(4−n2)ϵ2}
Więc dla mamy . W przypadku dość szybko staje się ciaśniejszy niż ale w przypadku bardzo małego , podczas gdy nawet to małe „okno” szybko zbiega się do zera. Na przykład dla , jeśli , to jest ciaśniejsze. Podsumowując, granica kardynała jest bardziej przydatna. B D ≤ B I n ≥ 5 B I B D ϵ n = 12 ϵ ≥ 0,008 B In≤4BD≤BIn≥5BIBDϵn=12ϵ≥0.008BI
KOMENTARZ
Aby uniknąć mylących wrażeń dotyczących oryginalnej pracy Hoeffdinga, muszę wspomnieć, że Hoeffding bada przypadek deterministycznej wypukłej kombinacji zależnych zmiennych losowych. W szczególności jego są liczbami, a nie zmiennymi losowymi, podczas gdy każdy jest sumą niezależnych zmiennych losowych, podczas gdy może istnieć zależność między . Następnie rozważa różne „statystyki U”, które można przedstawić w ten sposób.X i X iWiXiXi