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..
 A: 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...
A: 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$.
