Wykładnicza górna granica

12

Załóżmy, że mamy losowe zmienne IID z rozkładem . Będziemy obserwować próbkę „s w następujący sposób: niech być niezależny zmiennymi losowymi, załóżmy, że wszystkie ” S i „s są niezależne i określają wielkość próby . W „s wskazują, które z ” s są w próbce, i chcemy studiować część sukcesów w próbce określonej przez X1,,XnBer(θ)XiY1,,YnBer(1/2)XiYiN=i=1nYiYiXi

Z={1Ni=1nXiYiifN>0,0ifN=0.
Dla chcemy znaleźć górną granicę dla która rozpada się wykładniczo z . Nierówność Hoeffdinga nie ma zastosowania natychmiast ze względu na zależności między zmiennymi.ϵ>0Pr(Zθ+ϵ)n
Zen
źródło
1
Niech . (i) Czy nie niezależny od ? (ii) czy ? ... W rezultacie nie jest dla mnie jasne, czy nie jest „sumą niezależnych zmiennych losowych”Zi=1NXiYiZiZjiZ=ZiZ
Glen_b
Ach, dobra racja. I myślał o zamiast . Ale czy nie możesz zamiast tego napisać i pozwól ? Oznacza to, że suma we wszystkich przypadkach, niezależnie od tego, czy wynosi 1 lub 0. ... nie, to nie działa. Licznik jest taki sam, ale mianownik jest inny. N Z i = 1nNZ= n i = 1 ZiYZi=1nXiYiZ=i=1nZiY
Glen_b
To daje mniej niż ułamek sukcesów w próbie, czyli wielkość zainteresowania problemem, ponieważ , ponieważ . N n(1/n)i=1nXiYi(1/N)i=1nXiYiNn
Zen
1
Tak, dlatego skończyłem z „nie, to nie działa”. Istnieją nierówności, które odnoszą się do nie-niezależnego przypadku, takie jak niektóre nierówności Bernsteina (patrz czwarty punkt), i istnieje szereg nierówności, które mają zastosowanie do martingales (choć nie wiem, że będą one miały zastosowanie tutaj).
Glen_b
1
Przyjrzę się, a także spróbuję znaleźć związek z wynikami Martingales. Ograniczenie dla jest takie łatwe ( ), że kuszące jest połączenie tego z za pomocą pewnego rodzaju warunkowania. P r ( U θ / 2 + ϵ ) exp ( - 2 n ϵ 2 ) ZU=(1/n)i=1nXiYiPr(Uθ/2+ϵ)exp(2nϵ2)Z
Zen

Odpowiedzi:

16

Możemy nawiązać do nierówności Hoeffdinga w dość bezpośredni sposób .

Zauważ, że mamy

{Z>θ+ϵ}={iXiYi>(θ+ϵ)iYi}={i(Xiθϵ)Yi>0}.

Ustaw tak, aby to iid, i 2/2 poprzez proste zastosowanie nierówności Hoeffdinga (od więc weź wartości w przedziale wielkości jeden).Z i E Z i = 0 P ( Z > θ + ϵ ) = P ( i Z i > n ϵ / 2 )e - n ϵ 2 / 2Zi=(Xiθϵ)Yi+ϵ/2ZiEZi=0Z i[ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ]

P(Z>θ+ϵ)=P(iZi>nϵ/2)enϵ2/2,
Zi[θϵ/2,1θϵ/2]

Istnieje bogata i fascynująca literatura pokrewna, która powstała w ciągu ostatnich kilku lat, w szczególności na tematy związane z teorią macierzy losowych o różnych praktycznych zastosowaniach. Jeśli jesteś zainteresowany tego typu rzeczami, bardzo polecam:

R. Vershynin, Wprowadzenie do niesymptotycznej analizy macierzy losowych , Rozdział 5 Compress Sensing, Theory and Applications. Pod redakcją Y. Eldar i G. Kutyniok. Cambridge University Press, 2012.

Myślę, że ekspozycja jest przejrzysta i stanowi bardzo dobry sposób na szybkie zapoznanie się z literaturą.

kardynał
źródło
1
Ponieważ zawierają w swojej definicji, mam wrażenie, że (granica się nie zmienia). ϵ / 2 Z i[ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ]Ziϵ/2Zi[θϵ/2,1θϵ/2]
Alecos Papadopoulos
1
Drogi @Zen: Zauważ, że uważna księgowy wypadku pozwoli na zastąpienie ścisłej nierówności przez wszędzie bez zmiany ostateczna granica. > N=0>
kardynał
Drogi @ kardynał: Przeredagowałem pytanie, ponieważ faktycznie jest (nieco) tendencyjnym estymatorem , ponieważ . θ E [ Z ] = E [ I { N = 0 } Z ] + e [ I { N > 0 } Z ] = ( 1 - 1 / 2 n )ZθE[Z]=E[I{N=0}Z]+E[I{N>0}Z]=(11/2n)θ
Zen
6

Szczegóły do ​​załatwienia sprawy . N=0

{Zθ+ϵ}=({Zθ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({0θ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({N=0})({Zθ+ϵ}{N>0})={i=1nXiYi(θ+ϵ)i=1nYi}{N>0}{i=1nXiYi(θ+ϵ)i=1nYi}={i=1n(Xiθϵ)Yi0}={i=1n((Xiθϵ)Yi+ϵ/2)nϵ/2}.

Dla Alecos.

E[i=1nWi]=E[I{i=1nYi=0}i=1nWi]+E[I{i=1nYi>0}i=1nWi]=E[I{i=1nYi>0}i=1nYii=1nYi]=E[I{i=1nYi>0}]=11/2n.
Zen
źródło
5

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

WiYii=1nYi,i=1nYi0,i=1nWi=1,n2

podczas gdy ustawiamy jeśli .Wi=0i=1nYi=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ći=1nWi=1

ehZn=exp{h(i=1nWiXi)}i=1nWiehXi

i łączenie wyników, aby dojść do

Pr(Znμn+ϵ)eh(μ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+ϵ)eh(μ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+ϵ)eh(μ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θϵe2ϵ2

Dzięki uprzejmości OP (dzięki, byłem już trochę wyczerpany ...)

i=1nE(Wi)=11/2n

Wreszcie „podejście zmiennych zależnych” daje nam

Pr(Znθ+ϵ)(112n)e2ϵ2BD

Porównajmy to z ograniczeniami kardynała, opartymi na transformacji „niezależności”, . Aby nasza więź była ściślejsza, potrzebujemyBI

BD=(112n)e2ϵ2enϵ2/2=BI

2n12nexp{(4n2)ϵ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 DB I n 5 B I B D ϵ n = 12 ϵ 0,008 B In4BDBIn5BIBDϵ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

Alecos Papadopoulos
źródło
Alecos: (spójrz na pochodne na końcu mojej odpowiedzi). Twoja granica nie rozkłada się wykładniczo z jak kardynał. NE[W1]=(11/2n)/nn
Zen
@Zen Rzeczywiście (w rzeczywistości zwiększa się wraz z rozmiarem próbki, choć jest ograniczony), dlatego wiązanie Kardynała jest bardziej przydatne dla większości rozmiarów próbek.
Alecos Papadopoulos