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
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.
Odpowiedzi:
Możemy nawiązać do nierówności Hoeffdinga w dość bezpośredni sposób .
Zauważ, że mamy
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+ϵ/2 Zi EZi=0 Z i ∈ [ - θ - ϵ / 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:
Myślę, że ekspozycja jest przejrzysta i stanowi bardzo dobry sposób na szybkie zapoznanie się z literaturą.
źródło
Szczegóły do załatwienia sprawy .N=0
Dla Alecos.
źródło
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
podczas gdy ustawiamy jeśli .Wi=0 ∑ni=1Yi=0
Mamy więc zmienną
Interesuje nas prawdopodobieństwo
Podobnie jak w przypadku wielu innych nierówności, Hoeffding rozpoczyna swoje rozumowanie od stwierdzenia, że i to
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
i łączenie wyników, aby dojść do
Koncentrując się na naszym przypadku, ponieważ i są niezależne, wartości oczekiwane można rozdzielić,Wi Xi
W naszym przypadku to iid Bernoullis z parametrem , a jest ich wspólną funkcją generowania momentu w , . WięcXi θ E[ehXi] h E[ehXi]=1−θ+θeh
Otrzymujemy minimalizując RHS w odniesieniu doh
Włączając go w nierówność i manipulując, uzyskujemy
podczas
Hoeffding to pokazuje
Dzięki uprzejmości OP (dzięki, byłem już trochę wyczerpany ...)
Wreszcie „podejście zmiennych zależnych” daje nam
Porównajmy to z ograniczeniami kardynała, opartymi na transformacji „niezależności”, . Aby nasza więź była ściślejsza, potrzebujemyBI
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≤4 BD≤BI n≥5 BI BD ϵ n=12 ϵ≥0.008 BI
KOMENTARZWi Xi Xi
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 i
źródło