11
$\begingroup$

Let we fix $0<E<1$ and an integer $t>0$.

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

$\endgroup$
  • 3
    $\begingroup$ I'm confused by the term $E\times n \choose t$. As $E\times n$ is not necessarily an integer, how is it defined? $\endgroup$ – Dave Clarke Jun 22 '11 at 6:23
  • 2
    $\begingroup$ What is the motivation? $\endgroup$ – Anthony Labarre Jun 22 '11 at 8:44
  • 6
    $\begingroup$ @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!$. $\endgroup$ – Peter Taylor Jun 22 '11 at 10:33
  • 2
    $\begingroup$ 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). $\endgroup$ – Klaus Draeger Jun 22 '11 at 10:36
  • 1
    $\begingroup$ @Dave: I'm sorry for my inaccuracy, from my point of view you can choose $\lfloor En \rfloor$. $\endgroup$ – AntonioFa Jun 22 '11 at 12:10
2
$\begingroup$

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 $0<E<1$, integers $n,t>0$, 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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.