Consider a two-stage sampling scheme: First, use weighted random selection from a list to obtain a set of N unique elements. Next, use uniform random selection to pick one of those elements.
How can I counter the skew caused by the uniqueness condition when obtaining the first weighted set, so that the output selection frequency corresponds well with the weights defined for each element?
I obtain the first set by repeating a simple weighted sampling: Construct a cumulative list of weights, select a random integer in [0, sum(cumweights)), find corresponding index in cumulative list of weights, then return the corresponding element. I repeat this N times, where N is the number of elements in the list. Then I throw away duplicates.
Here's the comparison between keeping and throwing away duplicates, when I run a simulation 1'000'000 times:
Element Weight W/duplicates WO/duplicates A 5 0.050 0.066 B 10 0.100 0.125 C 20 0.200 0.219 D 30 0.300 0.283 E 35 0.350 0.307
The application here is a DNS load balancer with a configured set of (IP,weight) tuples. A query should return a set of unique IPs to the client in such a way that over time, each IP is selected with a probability corresponding to its weight -- as if a single sample was taken. The various DNS resolvers involved in the process (OS stub resolver, local recursor, etc) can be assumed to shuffle the IP set uniformly (although this is resolver-specific).