Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
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
add comment

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

share|improve this answer
Very nice solution thanks :) I will keep it in the back of my head –  Listing May 7 '11 at 22:43
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.