# Guessing sum of random sub set of length x from one set

Given a known Set x . Given a know size y. User choose a random subset from x of size y. We need to guess the sum of the new subset. both x and y are less then 5000. After searching on net this problem seem to be related like Variance (one example is :Fair dice ).

But I am not able to find the solution for this problem. As number can't be repeated in the set. So what will the formula for this problem ?

-
The set x is an arbitrary set of numbers? "Length" means "size"? I dont understand what has this to do with "Variance", and why you are looking for a "formula"... – leonbloy Sep 1 '11 at 14:46
@Vivek: there are some details need to be known about your problem. If $x$ finite, countable or uncountable (maybe a subset of set of reals) - since the random choice depends on it very much? Btw, for the guess about the sum of elements in the random set, you better use expectation or the confidence interval. – Ilya Sep 1 '11 at 14:46
updated the question – Vivek Goel Sep 1 '11 at 14:54
"So what will the formula for this problem ?" Can you clearly describe what the problem is? Currently the question is not at all readable. – Srivatsan Sep 1 '11 at 15:07
The way I understand it: you have a set consisting of the first X natural numbers. You pick a random subset of Y elements from the set. The question is asking how to guess the sum of the numbers in the subset. Is that right? – Chris Taylor Sep 1 '11 at 15:10

Let $B$ be a set of $n$ real numbers. We choose at random an $m$-element subset $A$ of $B$. We want to know the expected value (mean) of the sum of the chosen numbers.

Let $B=\{b_1,b_2,\dots, b_n\}$. Imagine that the choosing is done sequentially. Let the random variable $X_i$ be the $i$-th number chosen, and let $$X=\sum_{i=1}^m X_i.$$ Then $X$ is the sum of the chosen numbers, and we want to find $E(X)$, the expected value of this sum. For any random variables $X_1, X_2, \dots, X_m$ we have $$E\left(\sum_{i=1}^m X_i\right)=\sum_{i=1}^m E(X_i).$$ Now we need to compute $E(X_i)$. But $X_i$ takes on the values $b_1, b_2,\dots, b_n$, each with probability $1/n$. It follows that $$E(X_i)=\frac{\sum_{i=1}^n b_i}{n},$$ and therefore $$E(X)=\frac{m}{n}\sum_{i=1}^nb_i.$$

$1$. The OP specified that the numbers chosen are distinct. In standard terminology, this means that the choosing is done without replacement. The above argument does not depend on whether the choosing is done with replacement or without replacement: the answer under each assumption is the same.

$2$. In an answer to one of the comments, the OP seemed to say that the set $B$ consists of the first $n$ positive integers, though that wasn't entirely clear. If $B=\{1,2,\dots,n\}$, then $$\sum_{i=1}^n i=\frac{n(n+1)}{2}\quad\text{and therefore}\quad E(X)=\frac{m(n+1)}{2}.$$

$3$. The same argument goes through if $B$ is a multiset (some of the $b_i$ are allowed to be equal), and $A$ is a (multi)subset of $B$.

$4$. As Yuval Filmus has pointed out in a comment, we can also find the variance of $X$ by an argument that exploits the linearity of expectation.

-

The expected value will be indeed better estimation for the sum, while the variance corresponds to the error of this estimation. Let me denote $x = \{x_1,...,x_n\}$. To model the random choice you should construct a probability space and there are several possibilities to do it.

The one is to pick up a random combination $s = \{s_1,...,s_y\}\subset x$ of $y$ elements from $x$. E.g. $s_1 = x_2,s_2 = x_3,s_3=x_4$ and so on. Let $S$ denote the set of all possible such combinations. Since numbers cannot repeat, $S$ has $C^y_n$ elements. To model a random choice you can assume that each combination has the same probability which is $$p(n,y) = \displaystyle{\frac{1}{C^y_n}}.$$

The formula for the expectation of the sum will be $$E = p(n,y)\sum\limits_{s\in S}\sum\limits_{i=1}^ys_i$$ and for the variance $$V = p(n,y)\sum\limits_{s\in S}\left(E-\sum\limits_{i=1}^ys_i\right)^2.$$

Although these formulas look weird, unfortunately if you don't have any special information about $x$ (e.g. $x =1,2,...,n$) then I believe you should deal with all possbile combinations. If you $x$ has a nice structure, then there can be nice formulas for $E$ and $V$.

-
As mentioned in the comments above, using linearity of expectation it's easy to compute E. You can compute V the same way, with perhaps a few more lines of computation. – Yuval Filmus Sep 1 '11 at 19:35
@Proteus: To add detail to the comment by Yuval Filmus, do the picking sequentially, let random variable $X_i$ be the number picked on the $i$-th trial, and let $X=\sum_1^m X_i$. Then $E(X)=E(\sum_1^m X_i)=\sum_1^m E(X_i)$. Independence is not required. And if the possible values are $a_1,\dots,a_n$, then $E(X_i)=(1/n)\sum_1^n a_i$. Expectation is great, we often need very little information to compute it. In particular, we do not need the probability distribution of the sum. – André Nicolas Sep 1 '11 at 20:49
@Andre: oh yeah, I missed it. Maybe you post these comments as an answer - seems that OP was wondering about it. Then I'll delete mine. – Proteus Sep 2 '11 at 6:06
There is no need to delete. Just modify your absolute assertion that nothing further can be done. You have given a valid expression for the answer. – André Nicolas Sep 2 '11 at 10:50