I am struggling on a probability problem. Here is the theoretical layout: Consider a set $\Omega$ with #$\Omega = N$ and a function $f:\Omega \rightarrow (0,1)$ such that $\sum\limits_{i \epsilon \Omega} f(i) = p$
We pick a random subset S of $\Omega$ with #$S = n$ with $p\leq n$ Let's define the random variable $X = \sum\limits_{j \epsilon S} f(j) $
Let's suppose that all subset of $\Omega$ have the same probability of being drawn. The question is to find the expectancy and variance of the random variable X
My first thought is to compute the following for k <= p $$ \mathbb{P}(X=k) = \frac{\binom{p}{k}\binom{N-p}{n-k}}{\binom{N}{n}} $$ Now it is possible to get the expectation $$ \mathbb{E}(X) = \sum\limits_{k=0}^p \frac{\binom{p}{k}\binom{N-p}{n-k}}{\binom{N}{n}} k $$ Which leads us to compute the following sum: $$ \mathbb{E}(X) = \sum\limits_{k=0}^p \binom{p}{k}\binom{N-p}{n-k} k $$ However, I am kind of stuck at this point. Same thing, I will need to compute the following to get to the variance $$ \mathbb{E}(X^2) = \frac{1}{\binom{N}{n}} \sum\limits_{k=0}^p \binom{p}{k}\binom{N-p}{n-k} k^2 $$
Anyone may hint me something ? I really feel I might use the derivation of $(1+x)^p(1+x)^{N-p}$ but cannot manage to find anything
Thanks a lot
A key to these computations is to rewrite $X$ as a sum over a fixed set, that is, $$ X=\sum_{i\in\Omega}f(i)\mathbf 1_{i\in S}. $$ If $S$ is chosen uniformly, then by symmetry, $P[i\in S]=n/N$ for each $i$. Thus, $$ E[X]=\sum_{i\in\Omega}f(i)P[i\in S]=\sum_{i\in\Omega}f(i)n/N=pn/N. $$ Likewise, $$ X^2=\sum_{i\in\Omega}f(i)^2\mathbf 1_{i\in S}+\sum_{i\ne j}f(i)f(j)\mathbf 1_{i,j\in S}. $$ If $S$ is chosen uniformly, then by symmetry, $P[i,j\in S]=n(n-1)/(N(N-1))$ for each $i\ne j$. Thus, $$ E[X^2]=\sum_{i\in\Omega}f(i)^2P[i\in S]+\sum_{i\ne j}f(i)f(j)P[i,j\in S], $$ that is, $$ E[X^2]=rn/N+(p^2-r)n(n-1)/(N(N-1)), $$ where $$ r=\sum_{i\in\Omega}f(i)^2. $$ The variance follows, as $$ \mathrm{var}(X)=\frac{n(N-n)}{N(N-1)}\left(r-\frac{p^2}N\right). $$