# Sampling subsegments from discrete input ranges

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?

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$.
• 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? – Alex Reynolds Aug 17 '12 at 18:08