-boleh ruang probabilitas independen

8

Saya telah mengalami banyak kesulitan menemukan referensi yang memberikan penjelasan sederhana dan langsung tentang hal berikut:

Misalkan kita memiliki variabel acak , masing-masing dari bit. (Yaitu dengan nilai dalam ). Kami menginginkan ruang probabilitas di mana setiap tidak bias (mengambil setiap nilai dengan probabilitas tepat ), dan memiliki -independensi. Yaitu, untuk setiap dan setiap kami memiliki nY1,,Ynb{0,,2b1}Yi2bki1<<iky1,,yk

P(Yi1=y1Yik=yk)=2kb

Ketika Anda selalu bisa mendapatkan ruang probabilitas ukuran dan kadang-kadang Anda bisa mendapatkan - apakah ada pernyataan yang jelas tentang kapan ini mungkin?b=1nknk/2

Dapatkah seseorang mengarahkan saya ke referensi tentang apa yang terjadi ketika ?b>1

Terima kasih

David Harris
sumber
Saya tidak yakin apa rujukannya, tetapi konstruksi yang saya tahu adalah: pilih polinomial acak daripada derajat paling banyak dan evaluasi pada poin. Ini memberikan ruang sampel dengan ukuran . Apakah ini jenis hasil yang Anda cari? GF(2max{b,log2n})k1nmax{2kb,nk}
Thomas
1
Ada survei yang bagus tentang topik tersebut oleh Salil Vadhan; ini tersedia online: people.seas.harvard.edu/~salil/pseudorandomness . Bab 3 mencakup variabel acak independen -wise. k
Yury

Jawaban:

5

Untuk acak , Alon, Babai dan Itai menunjukkan batas bawah pada ukuran ruang probabilitas mana bm(n,k/2)

m(n,k)=i=0k(ni)

yaitu untuk konstanta .Ω(nk/2)k

Mereka juga memberikan konstruksi ukuran dalam kasus .O(nk/2)b=1

Untuk ada makalah oleh Karloff dan Mansour yang menunjukkan batas bawah dan batas atas untuk probabilitas arbitrer, yaitu untuk dengan . Misalnya, ada probabilitas sedemikian rupa sehingga ukuran ruang probabilitas setidaknya . Mereka juga mengatakan bahwa juga merupakan batas atas untuk probabilitas arbitrer.b=1p1,,pnpi=P(Yi=1)p1,,pnm(n,k)m(n,k)

Saya tidak tahu ada konstruksi dengan batas atas yang lebih baik daripada yang diberikan oleh konstruksi (lihat di sini ) disebutkan oleh Thomas sebagai komentar.O(nk)

Marc Bury
sumber