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