8
$\begingroup$

I was wodering: if you have the set of integers $R = \{1, 2, \cdots , n\}$, I would like to know the distribution of the sum of the members of all the posible non-empty subsets. I have done a simple calculation for some values of $n$ and here you can see at the bottom the distribution, which resembles a lot to a gaussian or binomial distribution. My intuition says that binomial coefficient must be involved, but with some modification. Can you please help me with this problem? Seems to be more innocent that it is.

Many thanks in advance! enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Why exclude the empty subset? When including it, we would have "complete" symmetry (the number of subsets with a sum of $m$ would be equal to the number of subsets with a sum of $\binom{n+1}{2}-m$ for all $m$ ($\binom{n+1}{2}$ is the maximum sum). Also, the sum of the heights of the bars would be $2^n$ (instead of $2^n-1$). $\endgroup$ Mar 8 '19 at 15:08
3
$\begingroup$

Rather than getting a closed formula for the number of sums, I'll show that the distribution tends to a Gaussian.

Choosing a sum uniformly at random is the same as examining the random variable $$Y_n = 1 \cdot X_1 + 2 \cdot X_2 +\cdots + n \cdot X_n$$

where the variables $X_j$ are iid with $P[X_1 = 0] = P[X_1 = 1] = 1/2$. In your case you're looking at non-empty sums, so we should technically condition on not having $X_1 = X_2 = ... = X_n = 0$, but this set has exponentially small probability, and thus we can ignore it.

If we recenter and rescale, we will have $$\frac{Y_n - \mathbb{E}[Y_n]}{\sqrt{\operatorname{Var}[Y_n]}} \xrightarrow{d} \mathcal{N}(0,1)$$ as $n \to \infty$ by the Lindeberg Central Limit Theorem.

$\endgroup$
2
  • $\begingroup$ This is the first time I've heard about Lindeberg CLT (thanks! :D ) so I'm trying to understand what's going on here... Following the math at the wikipedia page, it seems you're relying on $\sum Var[k X_k] = \sum k^2 / 4 \propto n^3$ which, because it grows as a cube, is enough to meet the Lindeberg condition. Am I (roughly) correct? $\endgroup$
    – antkam
    Mar 9 '19 at 17:26
  • $\begingroup$ More or less, yeah; these random variables are bounded by $n$ and the standard deviation of $Y_n$ is on the order of $n^{3/2}$, thereby implying the Lindeberg condition. $\endgroup$
    – Marcus M
    Mar 10 '19 at 5:20
0
$\begingroup$

Let's put $$ N(s,n) $$ to be the number of occurrence of the sum $s$ among all the non-empty subsets taken from $\{ 1,2, \cdots, n\}$

Then, concerning the sum of the subsets of $\{1,2,\cdots,n,n+1\}$ we will have that $$ N(s,n + 1) = N(s,n) + N(s - n - 1,n) + \left[ {s = n + 1} \right] $$ because
- not involving $n+1$, we will have the same subsets and thus the same sums as from $\{1,\cdots,n\}$;
- the subsets obtained from a previous subset adding $n+1$, will sum to $s$ if previously was summimg to $s-(n+1)$;
- the unique subset containing $n+1$ will sum to $s$ if $s=n+1$: $\left[ {s = n + 1} \right]$ indicates the Iverson bracket.

As starting conditions we have $$ \left\{ \matrix{ N(s,n) = 0\quad \left| {\;n < 1\; \vee \;s < 1} \right. \hfill \cr N(s,1) = \left[ {s = 1} \right] \hfill \cr} \right. $$ and we can compactly write the recurrence as $$ \bbox[lightyellow] { N(s,n) = N(s,n - 1) + N(s - n,n - 1) + \left[ {s = n} \right]\quad \left| \matrix{ \;1 \le n \hfill \cr \;1 \le s\left( { \le \left( \matrix{ n + 1 \cr 2 \cr} \right)} \right) \hfill \cr} \right. }\tag{1}$$

This gives an o.g.f. in $s$ as $$ \bbox[lightyellow] { \eqalign{ & F(x,n) = \sum\limits_{1\, \le \,s} {N(s,n)\,x^{\,s} } = \cr & = \sum\limits_{1\, \le \,s} {N(s,n - 1)\,x^{\,s} } + \sum\limits_{1\, \le \,s} {N(s - n,n - 1)\,x^{\,s} } + \sum\limits_{1\, \le \,s} {\left[ {s = n} \right]\,x^{\,s} } = \cr & = F(x,n - 1) + x^{\,n} \sum\limits_{1\, \le \,s - n} {N(s - n,n - 1)\,x^{\,s - n} } + x^{\,n} = \cr & = \left( {1 + x^{\,n} } \right)F(x,n - 1) + x^{\,n} \cr} }\tag{2}$$

But that in $n$ or the double o.g.f. are of no practical use.

However from (2) we can obtain a closed form for $F(x,n)$ $$ \eqalign{ & F(x,n) - F(x,n - 1) = x^{\,n} \left( {F(x,n - 1) + 1} \right) \cr & \left( {F(x,n) + 1 - \left( {F(x,n - 1) + 1} \right)} \right) = x^{\,n} \left( {F(x,n - 1) + 1} \right) \cr & G(x,n) = \left( {1 + x^{\,n} } \right)G(x,n - 1) \cr & G(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} \cr} $$ i.e. $$ \bbox[lightyellow] { F(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} - 1 }\tag{3}$$ which matches the initial condition $F(x,1)=x$.

This gives in fact that

$N(s,n)$ is the number of partitions of $s$ into distinct parts, no greater than $n$.

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