Peristiwa probabilitas tinggi tanpa koordinat probabilitas rendah

9

Biarkan menjadi variabel acak yang mengambil nilai dalam (untuk beberapa alfabet besar ), yang memiliki entropi sangat tinggi - katakanlah,untuk konstanta kecil yang sewenang-wenang . Biarkan menjadi peristiwa yang mendukung sedemikian rupa sehingga , di mana adalah konstanta kecil yang berubah-ubah. $X$ $\Sigma^n$ $\Sigma$ $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ $\delta$ $E \subseteq \rm{Supp}(X)$ $X$ $\Pr[X \in E] \ge 1 - \varepsilon$ $\varepsilon$

Kami mengatakan bahwa sepasang $(i,\sigma)$ adalah probabilitas rendah koordinat dari $E$ jika $\Pr[X \in E | X_i = \sigma] \le \varepsilon$ . Kami mengatakan bahwa string $x \in \Sigma^n$ berisi koordinat probabilitas $E$ jika $(i, x_i)$ adalah koordinat probabilitas $E$ untuk beberapa $i$ .

Secara umum, beberapa string di $E$ mungkin berisi koordinat probabilitas rendah $E$ . Pertanyaannya adalah dapatkah kita selalu menemukan peristiwa probabilitas tinggi $E' \subseteq E$ sehingga tidak ada string dalam $E'$ mengandung koordinat probabilitas rendah $E'$ (dan bukan $E$ ).

Terima kasih!

it.information-theory pr.probability Atau Meir
sumber

4

Berikut adalah contoh yang melengkapi jawaban Harry Yuen. Sebagai contoh tandingan, cukup untuk mendefinisikan dan menunjukkan bahwa setiap himpunan bagian besar harus memiliki probabilitas rendah koordinasi - probabilitas rendah koordinasi tentu merupakan probabilitas rendah co -ordinat . $X,E$ $E'\subseteq E$ $E$ $E$ $E'$

Juga, saya akan mengabaikan kondisi tentang entropi - menambahkan variabel bebas terdistribusi seragam seragam ke (dan mengambil ke ) akan meningkatkanke hampir tanpa mempengaruhi apakah ada (saya belum memikirkan hal ini dengan seksama). $N$ $X$ $E$ $E\times \Sigma^N$ $H(X)/(n+N)\log|\Sigma|$ $1$ $E'$

Inilah contohnya. Misalkan adalah elemen acak dari sehingga setiap vektor dengan berat Hamming (yaitu vektor-vektor dari bentuk ) memiliki probabilitas dan semua-satu vektor memiliki probabilitas . Biarkan menjadi himpunan vektor dengan berat Hamming . $X$ $\{0,1\}^n$ $1$ $0\dots 010\dots 0$ $(1-\epsilon)/n$ $1\dots 1$ $\epsilon$ $E$ $1$

Pertimbangkan subset . Jika tidak kosong, ini berisi vektor Hamming weight , katakan tanpa kehilangan keumuman. Tetapi , yang kurang dari jika adalah sekitar . $E'\subseteq E$ $E'$ $1$ $100\dots 0$ $\Pr[X \in E'|X_i=1]=\frac{(1-\epsilon)/n}{(1-\epsilon)/n + \epsilon}$ $\epsilon$ $n$ $2/\epsilon^2$

Colin McQuillan
sumber

6

Bagaimana dibandingkan dengan ? Jika bisa menjadi , maka saya pikir kami dapat mencapai apa yang Anda inginkan. Mari . Perhatikan bahwa diberikan massa probabilitas di bawah . Misalkan menunjukkan massa probabilitas yang ditetapkan untuk string dalam sedemikian rupa sehingga koordinat ke- memiliki simbol . $\epsilon$ $n$ $\epsilon$ $O(1/\sqrt{n})$ $B = \mbox{Supp}(X) - E$ $B$ $\epsilon$ $X$ $\lambda(i,\sigma)\epsilon$ $B$ $i$ $\sigma$

Misalkan adalah probabilitas rendah koordinat untuk beberapa string di . Biarkan menunjukkan massa probabilitas yang ditetapkan untuk string tersebut. Kemudian, menurut definisi, , menyiratkan bahwa . Kita dapat membuang string probabilitas rendah ini sementara hanya menderita kerugian dalam prob. massa untuk . $(i,\sigma)$ $E$ $\delta(i,\sigma)$ $\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$ $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$ $\delta(i,\sigma)$ $E$

Lanjutkan melakukan ini untuk semua kemungkinan yang buruk , dan pada akhirnya kami hanya membuang paling banyak . Ini menggunakan fakta bahwa untuk semua , . $(i,\sigma)$ $\sum_{i,\sigma} \delta(i,\sigma) \leq \sum_{i} \sum_{\sigma} 2\lambda(i,\sigma)\epsilon^2 \leq 2\sum_{i} \epsilon^2 = 2n\epsilon^2$ $i$ $\sum_{\sigma} \lambda(i,\sigma) = 1$

Jika Anda ingin memiliki massa probabilitas , maka harus sedemikian rupa sehingga , atau yang sudah cukup. $E'$ $1 -\gamma$ $\epsilon$ $\epsilon + 2n\epsilon^2 \leq \gamma$ $\epsilon = O(\gamma/\sqrt{2n})$

Tidak jelas bagi saya saat ini apakah ketergantungan ini pada dapat dihilangkan; Saya akan terus memikirkannya. $n$

Henry Yuen
sumber

Oh, saya baru menyadari bahwa Anda sedang mencari persyaratan kuat - yaitu, bahwa tidak memiliki koordinat probabilitas rendah sehubungan dengan , bukan . Saya akan kembali lagi nanti hari ini.

E^{'}

$E'$

E^{'}

$E'$

E

$E$

Henry Yuen

Terima kasih! Saya mencari epsilon yang konstan, tetapi bisa saja kecil.

Atau Meir

Peristiwa probabilitas tinggi tanpa koordinat probabilitas rendah

Jawaban: