Skip to main content
Post Undeleted by Aaron Meyerowitz
added 8 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Does theThe probability you seekwill depend on $b$? Or are you looking for the probability that the multiset of all $2^n-1$ subset sums does not include all(for $2n-1$ values between$n \gt 1$). It is the same for $-2^n+1$$b$ and $2^n-1$?$-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 chosen subset is equally likely to be $\{{-1,0\}},\{{-1,1\}},\{{0,1\}}$ So you are sure to have a subset which sums to $0$, have a chance subset sum of $1$ with probability will be $\frac{2}{3}$ and get$\frac13$ in all three of $-1,0,1$ with probability $\frac{1}{3}$cases.

In case $n=2$ you end up with one of the $35$$21$ ways to pick $4$$2$ distinct elements from $-3,-2,-1,0,1,2,3.$ All $35$ waysThe number of these which allow a subset sum of $0$. A$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 $1$,$2$,$0,1,2,3,4,5,6$ or $3$ occurs with probability $\frac{31}{35}$,$7$ are $\frac{28}{35}$,$193,175,164,163,151,149,137$ or $\frac{26}{35}$$134$. The probability of getting

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

Does the probability you seek depend on $b$? Or are you looking for the probability that the multiset of all $2^n-1$ subset sums does not include all $2n-1$ values between $-2^n+1$ and $2^n-1$?

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 chosen subset is equally likely to be $\{{-1,0\}},\{{-1,1\}},\{{0,1\}}$ So you are sure to have a subset which sums to $0$, have a chance subset sum of $1$ with probability $\frac{2}{3}$ and get all three of $-1,0,1$ with probability $\frac{1}{3}$

In case $n=2$ you end up with one of the $35$ ways to pick $4$ distinct elements from $-3,-2,-1,0,1,2,3.$ All $35$ ways allow a subset sum of $0$. A sum of $1$,$2$, or $3$ occurs with probability $\frac{31}{35}$, $\frac{28}{35}$, or $\frac{26}{35}$. The probability of getting all $7$ of $-3,-2,-1,0,1,2,3$ is $\frac{12}{35}.$

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.

Post Deleted by Aaron Meyerowitz
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Does the probability you seek depend on $b$? Or are you looking for the probability that the multiset of all $2^n-1$ subset sums does not include all $2n-1$ values between $-2^n+1$ and $2^n-1$?

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 chosen subset is equally likely to be $\{{-1,0\}},\{{-1,1\}},\{{0,1\}}$ So you are sure to have a subset which sums to $0$, have a chance subset sum of $1$ with probability $\frac{2}{3}$ and get all three of $-1,0,1$ with probability $\frac{1}{3}$

In case $n=2$ you end up with one of the $35$ ways to pick $4$ distinct elements from $-3,-2,-1,0,1,2,3.$ All $35$ ways allow a subset sum of $0$. A sum of $1$,$2$, or $3$ occurs with probability $\frac{31}{35}$, $\frac{28}{35}$, or $\frac{26}{35}$. The probability of getting all $7$ of $-3,-2,-1,0,1,2,3$ is $\frac{12}{35}.$