-boleh ruang probabilitas independen

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 $n$ $Y_1, \dots, Y_n$ $b$ $\{0, \dots, 2^b-1 \}$ $Y_i$ $2^{-b}$ $k$ $i_1 < \dots < i_k$ $y_1, \dots, y_k$

P (Y_{i_{1}} = y_{1} \land \dots \land Y_{i_{k}} = y_{k}) = 2^{- k b}

$P(Y_{i_1} = y_1 \wedge \dots \wedge Y_{i_k} = y_k) = 2^{-k b}$

Ketika Anda selalu bisa mendapatkan ruang probabilitas ukuran dan kadang-kadang Anda bisa mendapatkan - apakah ada pernyataan yang jelas tentang kapan ini mungkin? $b = 1$ $n^{k}$ $n^{k/2}$

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

Terima kasih

pr.probability limited-independence 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?

G F (2^{max {b, ⌈ \log_{2} n ⌉}})

$GF(2^{\max\{b,\lceil \log_2 n \rceil\}})$

k - 1

$k-1$

n

$n$

max {2^{k b}, n^{k}}

$\max\{2^{kb}, n^k\}$

Thomas

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

$k$

Yury

Jawaban:

Untuk acak , Alon, Babai dan Itai menunjukkan batas bawah pada ukuran ruang probabilitas mana $b$ $m(n,\lfloor k/2 \rfloor)$

m (n, k) = \sum_{i = 0}^{k} (\binom{n}{i})

$m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$

yaitu untuk konstanta . $\Omega(n^{k/2})$ $k$

Mereka juga memberikan konstruksi ukuran dalam kasus . $O(n^{k/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=1$ $p_1,\ldots,p_n$ $p_i = P(Y_i = 1)$ $p_1,\ldots,p_n$ $m(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(n^k)$

Marc Bury
sumber