I have a set of elements U (initially unknown size) and I would like to generate a random sample of n << |U| elements. Stream sampling works fine for this.
The issue comes when I have subdivided U into several subsets and taken a random sample of each subset (each sample contains k <= n elements, but usually k = n). I also know how many elements are in each subset. I would like to know how to combine these samples (preferably merging two samples at a time) into one size n sample.
Or put another way, given distinct sets A and B, and random samples a and b, I would like to make c ⊆ a ∪ b, such that c is a random sample of A ∪ B and I may specify the size of c (usually |c| will be about the same size as |a|).