1
$\begingroup$

Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this is divide each score by the total, then randomly sample based on each probability. This is at least O(N), and running it the next time will be O(N) as well since we have to renormalize. Inserting is also O(N) because we have to renormalize. I'm wondering if there is way we can utilize a priority queue or binary tree to make sampling and insertion less costly.

I am thinking for example, store every item in a priority queue, then to sample: Look at the current item's score, the left item's sum of scores, and the right item's sum of scores. Normalize by dividing each by the sum of all three, and sample the result. If the result is the left, rerun the algorithm on the left node. If the result is the right, rerun the algorithm on the right node. Otherwise if it's the current node, remove the node and return it as the sample. It is guaranteed to terminate when it gets to a leaf. We would have to do some extra work to keep track of the sum, but I think this would make all operations O(log(N)). Not sure this would sample with the actual required probability or if the time complexity is correct. Is there any existing work on this?

Edit: I think I found the answer: https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps you can write a full answer to your own question now, to help others in the future who might have a similar question? $\endgroup$
    – D.W.
    Dec 16 '20 at 19:56
1
$\begingroup$

This is exactly what the A-Res algorithm is for

If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time. The way you achieve this is:

  • For each sample: randomly generate a number between from 0 to 1
  • Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)

$\endgroup$

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.