Masalah kombinatorial sederhana (?) Yang lucu!

Mari kita perbaiki $0<E<1$ dan bilangan bulat $t>0$ .

untuk setiap $n$ dan untuk setiap vektor $\bar{c} \in [0,1]^n$ sehingga $\sum_{i\in [n]} c_i \geq E \times n$

$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t }$

Saya tidak tahu apakah statament itu benar atau salah. Saya pikir itu benar.

Intuisi saya berasal dari pengamatan bahwa untuk vektor (dengan properti desidered tentang jumlah) kita memiliki ; dalam hal ini kita hanya dapat memilih subset dari set . $\bar{c} \in \{0,1\}^n$ $A_{\bar{c}}= \binom{ E \times n}{t}$ $\{ i ~|~ c_i = 1 \}$

Dalam kasus lain kita dapat membuat subset yang baik (st jumlahnya lebih besar daripada ) menggunakan koordinat di tetapi juga, mungkin, menggunakan beberapa koordinat dari set kita bisa membuat set bagus lainnya! $E \times t$ $\{ i ~|~ c_i > E \}$ $\{ i ~|~ c_i \leq E \}$

Jadi, Buktikan atau temukan bug! berharap itu bisa menjadi permainan lucu untuk Anda!

Motivasi dari pertanyaan :

Misalkan Anda memiliki variabel acak , ukuran khas "berapa banyak keacakan" yang ada di adalah min-entropi $X\in \{0,1\}^n$ $X$

$H_{\infty}(X) = min_{x} \{ -log(Pr[X = x]) \}$

Dalam beberapa hal intuitif, entropi min adalah kasus terburuk dari Entropi Shannon yang terkenal (yaitu kasus rata - rata ).

Kami tertarik untuk menurunkan min-entropi dari variabel acak mana terdistribusi secara seragam pada set . $(Z=X \wedge Y| Y)$ $Y$ $\{ y ~|~ \sum_i y_i = t\}$

Secara longgar jika kita beruntung kita dapat menangkap bit yang memiliki "entropi yang baik" dan demikian juga kita jika lalu $X$ $H_{\infty}(X)\geq En$ $H_{\infty}(Z|Y)\geq Et$

Berapa probabilitas kita beruntung?

Masalahnya dipelajari dengan baik dan ada banyak literatur, misalnya lihat Lemma A.3. dalam Kriptografi Kunci-Publik yang Tahan Kebocoran dalam Model Pengambil-Terikat

co.combinatorics it.information-theory AntonioFa
sumber

Saya bingung dengan istilah . Karena belum tentu berupa bilangan bulat, bagaimana ini didefinisikan?

(\binom{E \times n}{t})

$E\times n \choose t$

E \times n

$E\times n$

Dave Clarke

Apa motivasinya?

Anthony Labarre

@Dave Clarke, pendekatan standar adalah untuk mendefinisikannya dalam hal fungsi gamma atau (mengingat bahwa adalah bilangan bulat) sebagai.

t

$t$

\prod_{k = 0}^{t - 1} (E n - k) / t!

$\prod_{k=0}^{t-1}(En-k) / t!$

Peter Taylor

Koefisien binomial dapat digeneralisasikan ke argumen non-integral (halaman Wikipedia memberikan beberapa detail). Meskipun demikian, mungkin tidak diperlukan dalam kasus ini: Perhatikan bahwa cukup untuk membuktikan ini dalam kasus ekstrem di mana jumlah sama dengan (yaitu adalah rata-rata mereka).

c_{i}

$c_i$

E \times n

$E\times n$

E

$E$

Klaus Draeger

@Dave: Saya minta maaf atas ketidaktepatan saya, dari sudut pandang saya, Anda dapat memilih .

⌊ E n ⌋

$\lfloor En \rfloor$

AntonioFa

Jawaban:

Dugaan dalam posting tidak berlaku, tetapi dugaan yang lebih lemah (sehubungan dengan lantai) yang disebutkan dalam komentar tidak berlaku. Bahkan, sesuatu yang lebih kuat berlaku.

Lemma 1. Dugaan dalam postingan tidak berlaku. Yaitu, ada contoh yang memenuhi asumsi yang diberikan di mana

| {S \subseteq [n] : \sum_{i \in S} c_{i} \geq E t} | < (\binom{E n}{t}) .

$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$

Bukti. Pertimbangkan contoh dengan , , , dan . Kemudian . Untuk sisi kiri, kita memiliki karena setiap himpunan bagian yang tidak mengandung jumlah kedua 1 paling banyak 1,7, dan hanya ada dua himpunan bagian ( dan ) yang mengandung keduanya 1. Dan sisi kanan adalah $n=3$ $c=(1, 1, 0.7)$ $E=2.7/3=0.9$ $t=2$ $E\, t = 1.8$

| {S \subseteq [3] : \sum_{i \in S} c_{i} \geq 1.8} | = 2

$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$

S

$S$

{1, 1}

$\{1,1\}$

{1, 1, 0.7}

$\{1,1,0.7\}$

(\binom{2.7}{2}) = 2.7 \cdot 1.7 / 2 = 2.295 > 2. ◻

$\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

Dugaan yang lebih lemah yang disarankan dalam komentar, yaitu lantai yang diikat lantai, , memang berlaku. Bahkan sesuatu yang sedikit lebih kuat berlaku: $\lfloor E\, n \rfloor$

Lemma 2. Perbaiki , bilangan bulat , dan vektor dengan . Kemudian $0<E<1$ $n,t>0$ $c \in [0,1]^n$ $\sum_{i\in [n]} c_i \geq E\, n$

| {S \subseteq [n] : \sum_{i \in S} c_{i} \geq E t} | > (\binom{⌊ E n ⌋}{t}) + (\binom{⌊ E n ⌋}{t + 1}) + \dots + (\binom{⌊ E n ⌋}{⌊ E n ⌋}) .

$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,>\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$

Bukti. Biarkan . Asumsikan WLOG bahwa . (Jika tidak, skala dan masing-masing turun dengan faktor seragam untuk membuatnya jadi. Ini mempertahankan dan tidak mengubah yang merupakan himpunan bagian setidaknya ke atau batas bawah yang diinginkan pada jumlah himpunan bagian tersebut.) Asumsikan WLOG bahwa (jika tidak, klaim berlaku sepele). $a=\lfloor E\, n\rfloor$ $a=E\,n$ $E$ $c_i$ $\sum_i c_i \ge E\,n$ $E\,t$ $t\le a$

Pertimbangkan setiap subset dengan ukuran setidaknya , di mana . Karena dan berisi semua elemen kecuali paling banyak (masing-masing paling banyak 1), kami memiliki , seperti yang diinginkan. $S\subseteq [n]$ $n-d$ $d=a-\lceil a\,t/n\rceil \ge 0$ $\sum_{i\in[n]} c_i \ge a$ $S$ $d$ $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$

Jumlah himpunan bagian adalah $S$

${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$

$= {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$

$> {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (menggunakan ) $n>a$

$= {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$

Tetapi (menggunakan ), jadi jumlah terakhir setidaknya adalah batas bawah yang diinginkan pada jumlah himpunan bagian yang baik. $a-d = \lceil a\,t/n\rceil \le t$ $a/n = E < 1$ $~~\Box$

Neal Young
sumber