I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets whose variance falls within r. Not only that, but I want to do this in an efficient manner. That is, the time for choosing a particular subset should be polynomial in n and k.

Note that n is large enough that I cannot brute-force the problem. That is, I cannot just iterate through all k-element subsets and find which ones have a variance that falls within r.

Is there a way to do this?

  • $\begingroup$ If you are satisfied with approximately uniform sampling, the problem is equivalent to approximately counting the number of k-element subsets whose variance is within the desired range, which might be easier to consider. See e.g. mathoverflow.net/questions/36735/… $\endgroup$ Sep 8, 2010 at 17:35
  • $\begingroup$ I meant k, not m. I corrected it. $\endgroup$ Sep 8, 2010 at 18:40
  • $\begingroup$ The following partial answer suggests additional information about the problem setting can be helpful: If the variance of the entire set of numbers lies within or even "reasonably close" to $[l,u]$, then random selection of subsets will be efficient. If you fix the variance while increasing $n$, this method will have constant asymptotic computational cost. As a function of $k$, it will become more efficient with large $n$ and $k$ provided the variance always lies within $[l,u]$. $\endgroup$
    – whuber
    Aug 17, 2011 at 20:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.