Rozszerzenie związane z Chernoffem

13

Szukam odwołania (a nie dowodu, że mogę to zrobić) do następującego rozszerzenia Chernoff.

Niech bądź logiczne zmienne losowe, niekoniecznie niezależne . Zamiast tego jest zagwarantowane, że dla każdego i każdego zdarzenia które zależy tylko od . $X_1,..,X_n$ $Pr(X_i=1|C)<p$ $i$ $C$ $\{X_j|j\neq i\}$

$\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

Z góry dziękuję!

reference-request pr.probability chernoff-bound ciekawy
źródło

26

To, czego chcesz, to uogólniona granica Chernoffa, która zakłada tylko dla dowolnego podzbioru S indeksów zmiennych. To ostatnie wynika z twojego założenia, ponieważ dla , Impagliazzo i Kabanets dali ostatnio alternatywny dowód na granicę Chernoffa, w tym uogólnioną. W ich pracy można znaleźć wszystkie odpowiednie odniesienia do poprzedniej pracy: http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ $S=\{i_1,\ldots,i_{|S|}\}$

P (\underset{i \in S}{⋀} X_{i}) = P (X_{i_{1}} = 1) P (X_{i_{2}} = 1 | X_{i_{1}} = 1) \dots P (X_{i_{| S |}} = 1 | X_{i_{1}}, . . ., X_{i_{| S | - 1}} = 1) \leq p^{| S |}

$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq p^{|S|}$

Dana Moshkovitz
źródło

Dziękuję za wyjaśnienie! W rzeczywistości ich stan implikuje zarówno to, co mam, jak i negatywne korelacje. Jest więc jakościowo silniejszy (jakoś przegapiłem ten moment, kiedy usłyszałem rozmowę Valentine'a). Teraz dowód tego, czego potrzebuję, staje się tak krótki, że chętnie zaznaczam moje pytanie jako odpowiedź, wielkie dzięki!

ciekawy

3

W twoim przypadku możesz po prostu stworzyć pod-martingale ze swoich zmiennych i użyć klasycznej nierówności Azuma do tego samego efektu. Aby to zadziałało, potrzebujesz tylko co wynika z twojego założenia.

P r [X_{i} = 1 | X_{1}, \dots, X_{i - 1}] < p

$Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$

Mahdi Cheraghchi,

7

Najbliższe rzeczy, o których wiem w literaturze, to rozszerzenia granic Chernoffa do ujemnie skorelowanych zmiennych losowych, np. Zobacz to lub tamto . Formalnie twój warunek może być spełniony bez ujemnej korelacji, ale pomysł jest podobny.

Ponieważ nie jest trudne do udowodnienia uogólnienie, być może nikt nie zadał sobie trudu, aby to napisać.

Lew Reyzin
źródło

Masz rację, to też było najbliższe, jakie znalazłem (w „Koncentracji ... do analizy ... algorytmów”). Chodzi o to, że mój rękopis jest za długi. Chciałbym uniknąć kolejnego podziału, jeśli to możliwe. Jeśli nie, nie będę miał wyboru ...

ciekawy

3

po to są Załączniki :)

Lew Reyzin

2

Hej, chłopaki, zostało to już udowodnione, a ja podałem w mojej odpowiedzi odniesienie (gdzie można znaleźć również wszystkie inne istotne odniesienia).

Dana Moshkovitz,

Ups - niesamowite. Jakoś nie zauważyłem twojej odpowiedzi!

Lew Reyzin

3

Alternatywnym odniesieniem może być Lemma 1.19 w B. Doerr, Analiza losowej heurystyki wyszukiwania: Narzędzia z teorii prawdopodobieństwa, Teoria losowej heurystyki wyszukiwania (red. A. Auger i B. Doerr, red.), World Scientific Publishing, 2011, s. 1–1 20

Krótko mówiąc, pokazuje, że gdy z prawdopodobieństwem bez względu na to, co włączone, a następnie spełniają wszystkie granice Chernoffa-Hoeffdinga, które są ważne dla niezależnych binarne zmienne losowe z prawdopodobieństwem sukcesu , odpowiednio . Dowód jest elementarny, a wynik jest naturalny, więc chyba nikt nie poczuł potrzeby, aby to napisać. $X_i=1$ $p_i$ $X_1, \dots, X_{i-1}$ $X_1, \ldots, X_n$ $Y_1, \ldots, Y_n$ $p_1, \ldots, p_n$

Benjamin Doerr
źródło

Rozszerzenie związane z Chernoffem

Odpowiedzi: