<p><em>The conjecture in the post does not hold, but the weaker conjecture (with respect to the floor) mentioned in the comments does hold.  In fact, something stronger holds.</em></p>

<hr>

<p><strong>Lemma 1.</strong> <em>The conjecture in the post does not hold.  That is, there is an instance satisfying the given assumptions where</em>
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| &lt; \binom{ E \, n}{ t }.$$</p>

<p><em>Proof.</em>
Consider the instance with $n=3$, $c=(1, 1, 0.7)$, $E=2.7/3=0.9$, and $t=2$.  Then $E\, t = 1.8$.
For the left-hand side, we have
$$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$$
because any subset $S$ that does not contain both 1's sums to at most 1.7, and there are only two subsets ($\{1,1\}$ and $\{1,1,0.7\}$) containing both 1's. And the right-hand side is $\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295&gt;2. ~~~\Box$</p>

<hr>

<p>The weaker conjecture suggested in the comments, namely the bound w.r.t. the floor, $\lfloor E\, n \rfloor$, does hold.  In fact something slightly stronger holds:</p>

<p><strong>Lemma 2.</strong> <em>Fix $0&lt;E&lt;1$, integers $n,t&gt;0$,
and vector $c \in [0,1]^n$ with $\sum_{i\in [n]} c_i \geq E\, n$.<br>
Then
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,&gt;\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$$</em></p>

<p><em>Proof.</em> Let $a=\lfloor E\, n\rfloor$. Assume WLOG that $a=E\,n$.  (Otherwise scale $E$ and each $c_i$ down by a uniform factor to make it so.  This maintains $\sum_i c_i \ge E\,n$ and changes neither which subsets sum to at least $E\,t$ nor the desired lower bound on the number of such subsets.)  Assume WLOG that $t\le a$ (otherwise the claim holds trivially).</p>

<p>Consider any subset $S\subseteq [n]$ of size at least $n-d$, where $d=a-\lceil a\,t/n\rceil \ge 0$. Since $\sum_{i\in[n]} c_i \ge a$ and $S$ contains all but at most $d$ elements (each of which is at most 1), we have $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$, as desired.</p>

<p>The number of such subsets $S$ is </p>

<p>${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$</p>

<p>$ = {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$</p>

<p>$ &gt; {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (using $n&gt;a$)</p>

<p>$ = {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$</p>

<p>But $a-d = \lceil a\,t/n\rceil \le t$ (using $a/n = E &lt; 1$), so the last sum is at least the desired lower bound on the number of good subsets. $~~\Box$</p>

CC BY-SA 4.0
2018-07-30T13:28:00.827Z
2018-07-30T14:53:22.433Z
2018-07-30T14:53:22.433Z
Neal Young
<p>Let we fix $0&lt;E&lt;1$ and an integer $t&gt;0$.</p>

<p>for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$</p>

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

<p>I don't know if the statament is true o false. 
I think it's true.</p>

<p>My intuition come from the observation that for the vectors $\bar{c} \in \{0,1\}^n$ (with the desidered property about the sum) we have $A_{\bar{c}}= \binom{ E \times n}{t}$; in this case we can only select subset from the set $\{ i ~|~ c_i = 1 \}$.</p>

<p>In the others case we can create good subset (s.t. the sum is greater then $E \times t$) using the coordinate in $\{ i ~|~ c_i &gt; E \}$ but also, maybe, using few coordinate from the set $\{ i ~|~ c_i \leq E \}$ we could create other good set!</p>

<p>So,Prove it or find the bug! hoping that it could be a funny game for you!</p>

<p><strong>Motivation of the question</strong>:</p>

<p>Suppose you have a random variable $X\in \{0,1\}^n$, a typical measure of "how much randomness" there is in $X$ is the min-entropy</p>

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

<p>In some intuitive sense the min-entropy is the <em>worst case</em> of the famous Shannon Entropy (that is the <em>average case</em>).</p>

<p>We are interested to lowerbound the min-entropy of the random variable $(Z=X \wedge Y| Y)$ where $Y$ is uniformely distributed over the set $\{ y ~|~ \sum_i y_i = t\}$.</p>

<p>Loosely speaking if we are lucky we can catch the bits of $X$ that have "good entropy" and so we if $H_{\infty}(X)\geq En$ then  $H_{\infty}(Z|Y)\geq Et$</p>

<blockquote>
  <p>What is the probability that we are lucky?</p>
</blockquote>

<p>The problem is well-studied one and there exists a lot of literature,
for example see Lemma A.3. in Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model</p>

CC BY-SA 3.0
2011-06-22T06:23:05.173Z
I'm confused by the term $E\times n \choose t$. As $E\times n$ is not necessarily an integer, how is it defined?
Dave Clarke
CC BY-SA 3.0
2011-06-22T08:44:55.603Z
What is the motivation?
Anthony Labarre
CC BY-SA 3.0
2011-06-22T10:33:58.080Z
@Dave Clarke, the standard approaches are to define it in terms of the gamma function or (given that $t$ is integer) as $\prod_{k=0}^{t-1}(En-k) / t!$.
Peter Taylor
CC BY-SA 3.0
2011-06-22T10:36:23.257Z
Binomial coefficients can be generalized to non-integral arguments (the Wikipedia page provides quite a few details). It may not be necessary in this case, though: Note that it is enough to prove this in the extremal case where the sum of the $c_i$ equals $E\times n$ (i.e. $E$ is their mean).
Klaus Draeger
CC BY-SA 3.0
2011-06-22T12:10:04.073Z
@Dave: I'm sorry for my inaccuracy, from my point of view you can choose $\lfloor En \rfloor$.
AntonioFa
CC BY-SA 3.0
2011-06-22T12:27:38.367Z
@Anthony: suppose you want to select $t$ random position in a "not purely" random string of $n$ bit, the problem is well studied for example you can see Lemma A.3. [link] (http://cs.nyu.edu/~dodis/ps/pkcbrm.pdf) `Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model`
AntonioFa
CC BY-SA 3.0
2011-06-22T13:29:26.763Z
@AntonioFa: Could you incorporate the motivation into the question?
Dave Clarke
<co.combinatorics><it.information-theory>
A simple(?) funny combinatorial problem!
AntonioFa
# A simple(?) funny combinatorial problem!

(Asked by: username_0 on 2011-06-21)

Let we fix $00$.

for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\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 }$

I don't know if the statament is true o false.
I think it's true.

My intuition come from the observation that for the vectors $\bar{c} \in \{0,1\}^n$ (with the desidered property about the sum) we have $A\_{\bar{c}}= \binom{ E \times n}{t}$; in this case we can only select subset from the set $\{ i ~|~ c\_i = 1 \}$.

In the others case we can create good subset (s.t. the sum is greater then $E \times t$) using the coordinate in $\{ i ~|~ c\_i > E \}$ but also, maybe, using few coordinate from the set $\{ i ~|~ c\_i \leq E \}$ we could create other good set!

So,Prove it or find the bug! hoping that it could be a funny game for you!

**Motivation of the question**:

Suppose you have a random variable $X\in \{0,1\}^n$, a typical measure of "how much randomness" there is in $X$ is the min-entropy

$H\_{\infty}(X) = min\_{x} \{ -log(Pr[X = x]) \}$

In some intuitive sense the min-entropy is the *worst case* of the famous Shannon Entropy (that is the *average case*).

We are interested to lowerbound the min-entropy of the random variable $(Z=X \wedge Y| Y)$ where $Y$ is uniformely distributed over the set $\{ y ~|~ \sum\_i y\_i = t\}$.

Loosely speaking if we are lucky we can catch the bits of $X$ that have "good entropy" and so we if $H\_{\infty}(X)\geq En$ then $H\_{\infty}(Z|Y)\geq Et$

> What is the probability that we are lucky?

The problem is well-studied one and there exists a lot of literature,
for example see Lemma A.3. in Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model

**Tags:** co.combinatorics, it.information-theory

> **Comments:**
> **username_1**: I'm confused by the term $E\times n \choose t$. As $E\times n$ is not necessarily an integer, how is it defined?  
> **username_2**: What is the motivation?  
> **username_3**: @username_1, the standard approaches are to define it in terms of the gamma function or (given that $t$ is integer) as $\prod_{k=0}^{t-1}(En-k) / t!$.  
> **username_4**: Binomial coefficients can be generalized to non-integral arguments (the Wikipedia page provides quite a few details). It may not be necessary in this case, though: Note that it is enough to prove this in the extremal case where the sum of the $c_i$ equals $E\times n$ (i.e. $E$ is their mean).  
> **username_0**: @Dave: I'm sorry for my inaccuracy, from my point of view you can choose $\lfloor En \rfloor$.  
> **username_0**: @Anthony: suppose you want to select $t$ random position in a "not purely" random string of $n$ bit, the problem is well studied for example you can see Lemma A.3. [link] (http://cs.nyu.edu/~dodis/ps/pkcbrm.pdf) `Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model`  
> **username_1**: @username_0: Could you incorporate the motivation into the question?  

---

## 1 answers

### Answer by username_5 on 2018-07-30. Score: 2 | Accepted answer

*The conjecture in the post does not hold, but the weaker conjecture (with respect to the floor) mentioned in the comments does hold. In fact, something stronger holds.*

---

**Lemma 1.** *The conjecture in the post does not hold. That is, there is an instance satisfying the given assumptions where*
$$\big|\textstyle\big\{ S \subseteq [n] : \sum\_{i \in S}~ c\_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$$

*Proof.*
Consider the instance with $n=3$, $c=(1, 1, 0.7)$, $E=2.7/3=0.9$, and $t=2$. Then $E\, t = 1.8$.
For the left-hand side, we have
$$\big|\textstyle\{ S \subseteq [3] : \sum\_{i \in S}~ c\_i \geq 1.8 \}\big| = 2$$
because any subset $S$ that does not contain both 1's sums to at most 1.7, and there are only two subsets ($\{1,1\}$ and $\{1,1,0.7\}$) containing both 1's. And the right-hand side is $\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

---

The weaker conjecture suggested in the comments, namely the bound w.r.t. the floor, $\lfloor E\, n \rfloor$, does hold. In fact something slightly stronger holds:

**Lemma 2.** *Fix $00$,
and vector $c \in [0,1]^n$ with $\sum\_{i\in [n]} c\_i \geq E\, n$.  
Then
$$\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 }.$$*

*Proof.* Let $a=\lfloor E\, n\rfloor$. Assume WLOG that $a=E\,n$. (Otherwise scale $E$ and each $c\_i$ down by a uniform factor to make it so. This maintains $\sum\_i c\_i \ge E\,n$ and changes neither which subsets sum to at least $E\,t$ nor the desired lower bound on the number of such subsets.) Assume WLOG that $t\le a$ (otherwise the claim holds trivially).

Consider any subset $S\subseteq [n]$ of size at least $n-d$, where $d=a-\lceil a\,t/n\rceil \ge 0$. Since $\sum\_{i\in[n]} c\_i \ge a$ and $S$ contains all but at most $d$ elements (each of which is at most 1), we have $\sum\_{i\in S} c\_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$, as desired.

The number of such subsets $S$ is

${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}~~~$ (using $n>a$)

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

But $a-d = \lceil a\,t/n\rceil \le t$ (using $a/n = E < 1$), so the last sum is at least the desired lower bound on the number of good subsets. $~~\Box$


---

