Sampling subsegments from discrete input ranges

Question

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?

Answer 1

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.