Prosty (?) Śmieszny problem kombinatoryczny!

Pozwólmy naprawić $0<E<1$ i liczbę całkowitą $t>0$ .

dla dowolnego $n$ i dla dowolnego wektora $\bar{c} \in [0,1]^n$ taki, że $\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 }$

Nie wiem, czy to prawda, czy fałsz. Myśle że to prawda.

Moja intuicja wynika z obserwacji, że dla wektorów (z pożądaną właściwością o sumie) mamy ; w tym przypadku możemy wybrać tylko podzbiór ze zbioru . $\bar{c} \in \{0,1\}^n$ $A_{\bar{c}}= \binom{ E \times n}{t}$ $\{ i ~|~ c_i = 1 \}$

W innym przypadku możemy stworzyć dobry podzbiór (st suma jest większa niż ) przy użyciu współrzędnych w ale także, być może, przy użyciu kilku współrzędnych ze zbioru możemy stworzyć inny dobry zestaw! $E \times t$ $\{ i ~|~ c_i > E \}$ $\{ i ~|~ c_i \leq E \}$

Udowodnij to lub znajdź błąd! mając nadzieję, że może to być dla ciebie zabawna gra!

Motywacja pytania :

Załóżmy, że masz losową zmienną , typową miarą „ile losowości” jest w jest min-entropia $X\in \{0,1\}^n$ $X$

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

W pewnym intuicyjnym sensie min-entropia jest najgorszym przypadkiem słynnej Shannon Entropy (to jest średni przypadek ).

Interesuje nas obniżenie dolnej entropii zmiennej losowej której jest równomiernie rozłożone w zbiorze . $(Z=X \wedge Y| Y)$ $Y$ $\{ y ~|~ \sum_i y_i = t\}$

Luźno mówiąc, jeśli mamy szczęście, możemy złapać bity które mają „dobrą entropię”, a więc jeśli to $X$ $H_{\infty}(X)\geq En$ $H_{\infty}(Z|Y)\geq Et$

Jakie jest prawdopodobieństwo, że mamy szczęście?

Problem jest dobrze zbadany i istnieje wiele literatury, na przykład patrz Lemat A.3. w odpornej na wycieki kryptografii klucza publicznego w modelu ograniczonego pobierania

co.combinatorics it.information-theory

— AntonioFa
źródło

Jestem zdezorientowany terminem . Ponieważ niekoniecznie jest liczbą całkowitą, jak jest zdefiniowana?

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

$E\times n \choose t$

E \times n

$E\times n$

— Dave Clarke

Jaka jest motywacja?

— Anthony Labarre

@Dave Clarke, standardowe podejście polega na zdefiniowaniu go pod względem funkcji gamma lub (biorąc pod uwagę, że jest liczbą całkowitą) jako.

t

$t$

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

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

— Peter Taylor

Współczynniki dwumianowe można uogólnić na argumenty niecałkowite (strona Wikipedii podaje sporo szczegółów). W tym przypadku może jednak nie być konieczne: Należy zauważyć, że wystarczy to udowodnić w ekstremalnym przypadku, gdy suma jest równa (tzn. jest ich średnią).

c_{i}

$c_i$

E \times n

$E\times n$

E

$E$

— Klaus Draeger

@Dave: Przepraszam za moją niedokładność, z mojego punktu widzenia możesz wybrać .

⌊ E n ⌋

$\lfloor En \rfloor$

— AntonioFa

Hipoteza w poście nie ma miejsca, ale słabsza hipoteza (w odniesieniu do podłogi), o której mowa w komentarzach, trwa. W rzeczywistości coś mocniejszego.

Lemat 1. Hipoteza w poście nie ma zastosowania. Oznacza to, że istnieje instancja spełniająca podane założenia, gdzie

| {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 }.$

Dowód. Rozważmy przypadek z , , i . Następnie . Po lewej stronie mamy ponieważ jakikolwiek podzbiór , który nie zawiera obu sum 1 do maksymalnie 1,7, a są tylko dwa podzbiory ( i ) zawierające oba . A prawa strona to $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$

Słabsza hipoteza sugerowana w komentarzach, a mianowicie związana z podłogą, , utrzymuje się. W rzeczywistości istnieje coś nieco silniejszego: $\lfloor E\, n \rfloor$

Lemat 2. Napraw , liczby całkowite i wektor pomocą . Następnie $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 }.$

Dowód. Niech . Załóżmy WLOG, że . (W przeciwnym razie przeskaluj i każde dół o jednolity współczynnik, aby tak było. Utrzymuje to i nie zmienia ani które podzbiory sumują się do co najmniej ani pożądanej dolnej granicy liczby takie podzbiory.) Załóżmy, że WLOG, że (w przeciwnym razie roszczenie jest trywialne). $a=\lfloor E\, n\rfloor$ $a=E\,n$ $E$ $c_i$ $\sum_i c_i \ge E\,n$ $E\,t$ $t\le a$

Rozważ dowolny podzbiór o wielkości co najmniej , gdzie . Ponieważ i zawiera wszystkie elementy z wyjątkiem co najwyżej (z których każdy ma najwyżej 1), mamy , zgodnie z życzeniem. $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$

Liczba takich podzbiorów wynosi $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}~~~$ (używając ) $n>a$

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

Ale (używając ), więc ostatnia suma jest co najmniej pożądaną dolną granicą liczby dobrych podzbiorów. $a-d = \lceil a\,t/n\rceil \le t$ $a/n = E < 1$ $~~\Box$

— Neal Young
źródło