Sampling without replacement

updated:

Efraimidis-Spirakis algorithm

Reference:

Weighted random sampling with a reservoir - ScienceDirect

Algorithm

• Input: weight and the number of samples to draw
• Output: samples without duplicates
• Operation:
  1. Draw a uniform random variable for each item
  2. Compute a random variable
  3. Find the indices of the largest values.
  4. Return the indices

Implementation tips

Since can be arbitrarily large and cause overfloating, it would be preferred to transform by

The logarithmic transformation preserves the order . Thus, instead of using , we can use to find what indices to return.

Code