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

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

<p>Is there a way to do this?</p>

CC BY-SA 3.0
2011-08-17T20:05:00.647Z
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]$.
whuber
CC BY-SA 2.5
2010-09-08T17:35:23.217Z
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. http://mathoverflow.net/questions/36735/enumeration-and-random-selection
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-08T18:40:33.063Z
I meant k, not m.  I corrected it.
Paul Reiners
<ds.algorithms><permutations><st.statistics>
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
Paul Reiners
# Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range

(Asked by: username_0 on 2010-09-08)

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?

**Tags:** ds.algorithms, permutations, st.statistics
> **Comments:**
> **username_2**: 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. http://mathoverflow.net/questions/36735/enumeration-and-random-selection  
> **username_0**: I meant k, not m.  I corrected it.  
> **username_1**: 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]$.  

---

## 0 answers

