5
$\begingroup$

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$?

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Dec 2, 2013 at 9:05
  • $\begingroup$ 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.$ $\endgroup$ Dec 2, 2013 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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