Un problème combinatoire simple (?) Drôle!

Fixons et un entier . $0<E<1$ $t>0$

pour tout et pour tout vecteur tel que $n$ $\bar{c} \in [0,1]^n$ $\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 }$

Je ne sais pas si le statament est vrai ou faux. Je pense que c'est vrai.

Mon intuition vient de l'observation que pour les vecteurs $\bar{c} \in \{0,1\}^n$ (avec la propriété souhaitée sur la somme) nous avons $A_{\bar{c}}= \binom{ E \times n}{t}$ ; dans ce cas, nous ne pouvons sélectionner qu'un sous-ensemble de l'ensemble $\{ i ~|~ c_i = 1 \}$ .

Dans les autres cas, nous pouvons créer un bon sous-ensemble (st la somme est supérieure à $E \times t$ ) en utilisant les coordonnées dans $\{ i ~|~ c_i > E \}$ mais aussi, peut-être, en utilisant quelques coordonnées de l'ensemble $\{ i ~|~ c_i \leq E \}$ nous pourrions créer un autre bon ensemble!

Alors, prouvez-le ou trouvez le bug! en espérant que cela pourrait être un jeu amusant pour vous!

Motivation de la question :

Supposons que vous ayez une variable aléatoire , une mesure typique de "combien de caractère aléatoire" il y a dans est l'entropie min $X\in \{0,1\}^n$ $X$

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

Dans un sens intuitif, la min-entropie est le pire des cas de la célèbre entropie de Shannon (c'est le cas moyen ).

Nous nous intéressons à la limite inférieure de l'entropie min de la variable aléatoire où est uniformément répartie sur l'ensemble . $(Z=X \wedge Y| Y)$ $Y$ $\{ y ~|~ \sum_i y_i = t\}$

En gros, si nous avons de la chance, nous pouvons attraper les bits de qui ont une "bonne entropie" et donc nous si puis $X$ $H_{\infty}(X)\geq En$ $H_{\infty}(Z|Y)\geq Et$

Quelle est la probabilité d'avoir de la chance?

Le problème est bien étudié et il existe de nombreuses publications, voir par exemple le lemme A.3. dans la cryptographie à clé publique résiliente aux fuites dans le modèle de récupération bornée

co.combinatorics it.information-theory AntonioFa
la source

Je suis confus par le terme . Comme n'est pas nécessairement un entier, comment est-il défini?

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

$E\times n \choose t$

E \times n

$E\times n$

Dave Clarke

Quelle est la motivation?

Anthony Labarre

@ Dave Clarke, les approches standard consistent à le définir en termes de fonction gamma ou (étant donné que est entier) comme.

t

$t$

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

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

Peter Taylor

Les coefficients binomiaux peuvent être généralisés à des arguments non intégraux (la page Wikipedia fournit pas mal de détails). Cela peut ne pas être nécessaire dans ce cas, cependant: Notez qu'il suffit de le prouver dans le cas extrême où la somme des est égale à (c'est-à-dire que est leur moyenne).

c_{i}

$c_i$

E \times n

$E\times n$

E

$E$

Klaus Draeger

@Dave: Je suis désolé pour mon inexactitude, de mon point de vue, vous pouvez choisir .

⌊ E n ⌋

$\lfloor En \rfloor$

AntonioFa

Réponses:

La conjecture dans le message ne tient pas, mais la conjecture plus faible (par rapport au sol) mentionnée dans les commentaires tient. En fait, quelque chose de plus fort tient.

Lemme 1. La conjecture dans le poste ne tient pas. Autrement dit, il existe une instance satisfaisant aux hypothèses données où

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

Preuve. Considérons l'instance avec , , et . Alors . Pour le côté gauche, nous avons car tout sous-ensemble qui ne contient pas les deux 1 au plus 1,7, et il n'y a que deux sous-ensembles ( et ) contenant les deux 1. Et le côté droit est $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$

La conjecture la plus faible suggérée dans les commentaires, à savoir la limite par rapport au sol, , tient. En fait, quelque chose de légèrement plus fort tient: $\lfloor E\, n \rfloor$

Lemme 2. Fixe , entiers et vecteur avec . Alors $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 }.$

Preuve. Soit . Supposons que WLOG . (Sinon, échelle et chaque vers le bas par un facteur uniforme pour le rendre ainsi. Cela maintient et ne change ni les sous-ensembles de somme d'au moins ni la borne inférieure souhaitée sur le nombre ces sous-ensembles.) Supposons que le WLOG (sinon la revendication est triviale). $a=\lfloor E\, n\rfloor$ $a=E\,n$ $E$ $c_i$ $\sum_i c_i \ge E\,n$ $E\,t$ $t\le a$

Considérons tout sous-ensemble de taille au moins , où . Étant donné que et contient tous les éléments sauf au plus (dont chacun est au plus 1), nous avons , comme vous le souhaitez. $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$

Le nombre de ces sous-ensembles est $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}~~~$ (en utilisant ) $n>a$

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

Mais (en utilisant ), donc la dernière somme est au moins la borne inférieure souhaitée du nombre de bons sous-ensembles. $a-d = \lceil a\,t/n\rceil \le t$ $a/n = E < 1$ $~~\Box$

Neal Young
la source