Select $n$ numbers without replacement from the set $\{1,2,...,m\}$, and generate the set $S=\{a_1,a_2,...,a_n\}$. I want to calculate the expectation of the variance for the sampling set $\mathbb{E}[Var(S)]$ and the maximum variance among all samples : $\max{Var(S)}$.

Besides, what's the distribution of the sample variance?

  • $\begingroup$ It looks like a homework, so my given answer is not precise, since giving detailed answers to homework problems is not beneficial. $\endgroup$
    – mpiktas
    Jun 23 '11 at 7:50
  • $\begingroup$ @mp A glance at @Fan's previous question indicates this is not homework. $\endgroup$
    – whuber
    Jun 23 '11 at 16:12

We know that

$$\widehat{Var}(\mathbf{a}) = \frac{1}{n-1}\left(\sum_{i=1}^n a_i^2 - \frac{1}{n}\left(\sum_{i=1}^n a_i \right)^2 \right)$$

is an unbiased estimator of the population variance, which is easily computed as $(m+1)m/12$. This, therefore, answers the first question concerning the expected variance.

I will only sketch how to maximize the variance. I claim it is maximized when the $a_i$ are in two contiguous blocks: that is, $\mathbf{a}$ is in the form

$$\mathbf{a} = (1, 2, \ldots, k, m-l+1, m-l+2, \ldots, m).$$

(Evidently $k+l = n$.) To prove this claim, suppose $\mathbf{a}$ is not in this form: then you can find a gap in one of the end sequences and increase the variance by changing one of the components of $\mathbf{a}$ to that gap. It remains only to maximize the variance among these special forms of $\mathbf{a}$; this is done by making the end sequence lengths as balanced as possible; that is, by setting $k=l$ when $n$ is even and otherwise by setting either $k=l+1$ or $l=k+1$. When $n=2k$ is even, the maximum variance equals

$$ n \frac{\left(3 m^2-3 m n+n^2 -1\right)}{12 (n-1)}.$$

When $n=2k+1$ is odd, the maximum variance is

$$(n+1) \frac{\left(3 m^2-3 m n+n^2\right)}{12 n}.$$

  • $\begingroup$ i think if n=1, the expectation of variance is 0, otherwise the expectation is (m+1)m/12. $\endgroup$
    – Fan Zhang
    Jun 25 '11 at 11:13
  • $\begingroup$ @Fan With the definition I provided on the first line, the variance does not exist when $n=1$. $\endgroup$
    – whuber
    Jun 25 '11 at 22:17
  • $\begingroup$ Hi whuber, Can I send you a draft of my idea on the correlation problem to your email, I was trapped at current point. $\endgroup$
    – Fan Zhang
    Jun 26 '11 at 16:12

I will give the hints for the first question. I assume that you are sampling without a replacement from the set $A=\{a_1,...,a_m\}$. We have that

$$P(S=\{a_1,...,a_n\})=\frac{1}{m\choose n}$$


$EVar(S)=\sum_{\{i_1,...,i_n\}\subset \{1,...,m\}}\left(\frac{1}{n}\sum_{j=1}^n a_{i_j}^2-\left(\frac{1}{n}\sum_{j=1}^na_{i_j}\right)^2\right)\frac{1}{m\choose n}$


$$\sum_{\{i_1,...,i_n\}\subset \{1,...,m\}}a_{i_1}^2={{m-1}\choose{n-1}}\sum_{i=1}^ma_i^2 $$


$$\sum_{\{i_1,...,i_n\}\subset \{1,...,m\}}a_{i_1}a_{i_2}={{m-2}\choose {n-2}}\sum_{i\neq j}^ma_ia_j$$

So the first term in expectation will be

$$\sum_{\{i_1,...,i_n\}\subset \{1,...,m\}}\frac{1}{n}\sum_{j=1}^n a_{i_j}^2\frac{1}{m\choose n}=\sum_{i=1}^na_i^2\frac{1}{m\choose n}{{m-1}\choose {n-1}}=\frac{1}{m}\sum_{i=1}^ma_i^2$$

I'll leave the second term as an exercise. The end result should be that


maybe with some constants missing. As this is a standard result in survey sampling theory, you can look it up in appropriate book.

As for the second question, I do not think there is a closed formula. The case with $m=3$ and $n=2$ illustrates this. Then there are 3 possible samples and $Var S$ can get three values $(a_1-a_2)^2/4$, $(a_2-a_3)^2/4$ and $(a_1-a_3)^2/4$. The maximum depends on the set $A=\{a_1,a_2,a_3\}$.

  • $\begingroup$ @mpiktas I think there is something wrong with your result. The EVar(S) only depends on {a1,...,an} in your result. But I think it should depend on {a1,...,am}. $\endgroup$
    – Fan Zhang
    Jun 23 '11 at 8:28
  • $\begingroup$ @Fan, thanks, I fixed it. I usually use $n$ to indicate the size of the sample, hence the mistake. $\endgroup$
    – mpiktas
    Jun 23 '11 at 8:36
  • $\begingroup$ @mpiktas Thank you. Do you have any idea about Max Var(S), i think this one is more difficult than the expectation. $\endgroup$
    – Fan Zhang
    Jun 23 '11 at 9:53
  • $\begingroup$ @Fan, yes the second one is more difficult. I suggest checking the textbooks on survery sampling to get acquainted with better machinery. Where does this problem come from? $\endgroup$
    – mpiktas
    Jun 23 '11 at 10:16
  • $\begingroup$ @mpiktas Actually, this is a problem from myself. I want to know what pattern will generate the maximum variance. Note that the set is fixed {1,2,...,m}, for m=10, n=5, the set {1,2,3,9,10} has the biggest variance after I have enumerated all possible combinations. $\endgroup$
    – Fan Zhang
    Jun 23 '11 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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