Perpanjangan Chernoff terikat

12

Saya mencari referensi (bukan bukti, yang bisa saya lakukan) untuk perpanjangan Chernoff berikut.

Misalkan menjadi variabel acak Boolean, tidak harus independen . Sebagai gantinya, dijamin bahwa untuk setiap dan setiap peristiwa yang hanya bergantung pada . $X_1,..,X_n$ $Pr(X_i=1|C)<p$ $i$ $C$ $\{X_j|j\neq i\}$

Secara alami, saya ingin batas atas di . $\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

Terima kasih sebelumnya!

reference-request pr.probability chernoff-bound ingin tahu
sumber

25

Yang Anda inginkan adalah Chernoff bound generalised, yang hanya mengasumsikan untuk setiap subset S dari indeks variabel. Yang terakhir mengikuti dari asumsi Anda, karena untuk , Impagliazzo dan Kabanets baru-baru ini memberikan bukti alternatif dari ikatan Chernoff, termasuk yang digeneralisasi. Dalam makalah mereka, Anda dapat menemukan semua referensi yang sesuai untuk karya sebelumnya: 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
sumber

Terimakasih atas klarifikasinya! Bahkan, kondisi mereka tersirat oleh apa yang saya miliki dan korelasi negatif. Jadi, ini memang lebih kuat secara kualitatif (saya entah bagaimana kehilangan titik itu ketika saya mendengar pembicaraan Valentine). Sekarang bukti dari apa yang saya butuhkan menjadi sangat singkat, sehingga saya dengan senang hati menandai pertanyaan saya sebagai dijawab, terima kasih banyak !!

penasaran

3

Dalam kasus Anda, Anda bisa membuat sub-martingale dari variabel Anda dan menggunakan ketimpangan Azuma klasik untuk efek yang sama. Agar ini berfungsi, Anda hanya perlu yang tersirat oleh asumsi Anda.

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

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

KIA

7

Hal terdekat yang saya ketahui dalam literatur adalah ekstensi batas Chernoff ke variabel acak berkorelasi negatif, misalnya melihat ini atau ini . Secara formal, kondisi Anda dapat dipenuhi tanpa korelasi negatif, tetapi idenya serupa.

Karena generalisasi Anda tidak sulit untuk dibuktikan, mungkin tidak ada yang mau repot-repot menuliskannya.

Lev Reyzin
sumber

Anda benar, itu juga yang paling dekat yang saya temukan (dalam "Konsentrasi ... untuk Analisis ... Algoritma"). Masalahnya adalah bahwa naskah saya terlalu panjang, saya ingin menghindari spin-off lagi, jika mungkin. Jika tidak, saya tidak punya pilihan ...

penasaran

3

ini adalah untuk apa Apendiks :)

Lev Reyzin

2

Hai, teman-teman, sudah terbukti sebelumnya, dan saya memberikan referensi dalam jawaban saya (di mana Anda juga dapat menemukan semua referensi lain yang relevan).

Dana Moshkovitz

Ups - luar biasa. Saya entah bagaimana tidak memperhatikan jawaban Anda!

Lev Reyzin

3

Referensi alternatif bisa Lemma 1.19 dalam B. Doerr, Menganalisis heuristik pencarian acak: Alat dari teori probabilitas, Teori Heuristik Pencarian Acak (A. Auger dan B. Doerr, eds.), World Scientific Publishing, 2011, hlm. 1- 20.

Dengan kata-kata sederhana, ini menunjukkan bahwa ketika dengan probabilitas tidak peduli apa pun kondisi Anda aktif, maka memenuhi semua batasan Chernoff-Hoeffding yang valid untuk independen variabel acak biner dengan probabilitas keberhasilan , masing-masing. Buktinya dasar dan hasilnya alami, jadi saya kira tidak ada yang merasa perlu untuk menuliskannya. $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
sumber

Perpanjangan Chernoff terikat

Jawaban: