# Variance for summing over distinct random integers

Let $L=\{a_1,a_2,\ldots,a_k\}$ be a random (uniformly chosen) subset of length $k$ of the numbers $\{1,2,\ldots,n\}$. I want to find $\operatorname{Var}(X)$ where $X$ is the random variable that sums all numbers with $k < n$.

Earlier today I asked about the expected value, which I noticed was easier than I thought. But now I am sitting on the variance since several hours but cannot make any progress. I see that $E(X_i)=\frac{n+1}{2}$ and $E(X)=k \cdot \frac{n+1}{2}$, I tried to use $\operatorname{Var}\left(\sum_{i=1}^na_iX_i\right)=\sum_{i=1}^na_i^2\operatorname{Var}(X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^na_ia_j\operatorname{Cov}(X_i,X_j)$ but especially the second sum is hard to evaluate by hand ( every time I do this I get a different result :-) ) and I have no idea how to simplify the Covariance term. Furthermore I know that $\operatorname{Var}(X)=\operatorname{E}\left(\left(X-\operatorname{E}(X)\right)^2\right)=\operatorname{E}\left(X^2\right)-\left(\operatorname{E}(X)\right)^2$, so the main Problem is getting $=\operatorname{E}\left(X^2\right)$. Maybe there is also a easier way than to use those formulas.

I think I got the correct result via trial and error: $\operatorname{Var}(X)=(1/12) k (n - k) (n + 1)$ but not the way how to get there..

-

Let me (almost) quote myself:

Hint: (1) Compute $E(a_1^2)$. (2) Show that $E(a_k^2)=E(a_1^2)$ for every $k$. (3) Compute $E(a_1a_2)$. (4) Show that $E(a_ka_i)=E(a_1a_2)$ for every $k\ne i$. (5) Deduce $E(X^2)$.

You probably already know the distribution of $a_1$ hence (1) and (2) are easy. Now, you simply need to know the distribution of $(a_1,a_2)$.

This is (still) a good example where computing the distribution is messy but computing expectations (and variances) is easy.

Edit One finds $$\mbox{var}(a_1)=\frac{1}{12}(n+1)(n-1),\quad \mbox{cov}(a_1,a_2)=-\frac{1}{12}(n+1).$$ Hence $$\mbox{var}(X)=k\mbox{var}(a_1)+k(k-1)\mbox{cov}(a_1,a_2)=\frac{1}{12}k(n+1)(n-k),$$ as computed by the OP. Sanity check: if $k=n$, $\mbox{var}(X)=0$.

-
Thank you, I am sorry if the question seems redundant for you but actually I did not see the link :-( –  Listing May 7 '11 at 19:50
Did you manage to go through steps (1) to (5) or were you stopped at one of them? –  Did May 7 '11 at 19:54
Yes actually I had already calculated that $E(a_1^2)=\frac{(n+1)(2n+1)}{6}$ and $E(a_1 a_2)=\frac{(n + 1) (2 + 3 n)}{12}$ (I hope those are right). But does this give me $E(X^2)$ now? –  Listing May 7 '11 at 20:10
Yes... Inserting everything in my ugly variance and covariance formula finally gives me the right result, thanks! –  Listing May 7 '11 at 20:22

So I actually assigned this problem to a class a couple weeks ago.

You can do what you did, of course.

But if you happen to know the "finite population correction" from statistics, it's useful here. This says that if you sample $k$ times from a population of size $n$, without replacement, the variance of the sum of your sample will be $(n-k)/(n-1)$ times the variance that you'd get summing with replacement. The variance if you sum with replacement is, of course, $k$ times the variance of a single element.

So you get $Var(X) = k(n-k)/(n-1) \times Var(U)$, where $U$ is a uniform random variable on $\{1, 2, \ldots, n\}$. It's well-known that $Var(U) = (n^2-1)/12$ (and you can check this by doing the sums) which gives the answer.

Of course this formula is derived by summing covariances, so in a sense I've just swept that under the rug...

-
Very nice solution thanks :) I will keep it in the back of my head –  Listing May 7 '11 at 22:43