0
$\begingroup$

I have an set of input ranges {[a1, b1], [a2, b2], ...}. Each a and b represent integer values.

I have a constant "segment length" i that is always less than b-a for all a and b.

I would like to uniformly sample (either with or without replacement) from the input ranges to get a set of subranges that fall within those inputs.

My naive approach is to expand the inputs to a larger set:

{
  [a1, a1 + i],
  [a1 + 1, a1 + i + 1],
  ...
  [b1 - i, b1],
  [a2, a2 + i],
  ...
  [b2 - i, b2],
  ...
}

and then sample from this. This would be a pretty memory-exhaustive approach. I also need to deal with duplicate elements. Is there a smarter way to subsample?

$\endgroup$
0
$\begingroup$

First, compute the number of all possible $i$ length segments, $\ell_j$ for range $j$. Let's say you have a total of $N$ ranges, i.e. {[a1, b1], [a2, b2], ..., [aN,bN]}.

Then, sample a range according to the distribution $P(j) = \ell_j / \sum_{j=1}^N \ell_j$.

Finally, uniformly randomly choose a segment within the chosen range in the previous step.

$\endgroup$
  • $\begingroup$ I think this is the naive approach I'm outlined in my question. Is there an smarter (i.e., more efficient) way to do this? For example, can I uniformly sample any [an, bn], and calculate subsegments, and uniformly sample again within that smaller space? Will two uniform samples like this give me the same distribution as one uniform sample on the entire space of subsegments? $\endgroup$ – Alex Reynolds Aug 17 '12 at 18:08
  • $\begingroup$ My suggested procedure is not memory exhaustive. Sampling the ranges uniformly will work only if all ranges contain the same number of segments. What is wrong with my suggestion? $\endgroup$ – emrea Aug 17 '12 at 18:25

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.