Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a list of distinct integers $a_1,\dots,a_n$ chosen uniformly from the interval $(-2^n,2^n)$, what is the probability that the list contains $\underline{NO\mbox{ }SUBSETS}$ that sum to another integer $b:|b|<2^n$? (what is the probability that the np complete problem SUBSET SUM does not have a subset sum)

Is the odds that there is no subset that sums to b (when b is fixed) is $\frac{1}{2}\pm\epsilon$ or $\epsilon$ or $1-\epsilon$?

share|improve this question

2 Answers 2

The probability that a particular subset of size $k$ has sum $b$ is bounded by $\frac{C}{2^n \sqrt{k}}$, (maximized by $b=0$). Thus the probability that some subset has sum $b$ is at most the sum over $k\leq n$, which is roughly $C/\sqrt{n}$.

[EDIT:] The above is for numbers chosen uniformly with repetition. However, this makes little difference, as the probability of a repetition is much smaller, of order $n^2 2^{-n}$.

share|improve this answer

The probability will depend on $b$ (for $n \gt 1$). It is the same for $b$ and $-b$. Here is some small data:

The empty subset has sum $0$ but it goes without saying that you mean a non-empty subset, so I won't even mention that.

In the case $n=1$ the probability will be $\frac13$ in all three cases.

In case $n=2$ you end up with one of the $21$ ways to pick $2$ distinct elements from $-3,-2,-1,0,1,2,3.$ The number of these which allow a subset sum of $0,1,2$ or $3$ are $9,8,7$ or $7$

In the case $n=3$ there are $\binom{15}{3}=455$ equally likely outcomes and of these the number allowing a subset sum of $0,1,2,3,4,5,6$ or $7$ are $193,175,164,163,151,149,137$ or $134$.

It seems premature to make any conjectures based on that. It would be a little more time consuming to consider all $\binom{31}7=31465$ possibilities for $n=4$. One could either do random samples or come up with a more intelligent analysis.

share|improve this answer
    
are your counts correct? For n=3. In [a1 a2 a3], pick a1=0, then a2 and a3 can be any of the other numbers for a count of 14*13. Pick a1=1. Then you have a2=-a3 or a2=-1 or a3=-1. For a2=-1 itself you have 13 different choices for a3. This partical count itself takes number of ways 0 can occur as subset to 14*13+13=195>193. –  Turbo Dec 2 '13 at 9:05
    
I was counting out of (unordered) sets of 3 values. so $0,x,y$ occurs $\frac{14\cdot 13}{2}=91$ ways. $x,-x,y$ with $y \ne 0$ happens $14\cdot 6=84$ ways. Another $9$ are $x,y,-x-y$ for 1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 3,4 and a final $9$ of $-x,-y,x+y$ for the same choices . In all, $91+84+9+9=193.$ –  Aaron Meyerowitz Dec 2 '13 at 21:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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