An Efficient Method for Weighted Sampling without Replacement

Abstract

In this note, an efficient method for weighted sampling of K objects without replacement from a population of n objects is proposed. The method requires $O(K\log n)$ additions and comparisons, and $O(K)$ multiplications and random number generations while the method proposed by Fagin and Price requires $O(Kn)$ additions and comparisons, and $O(K)$ divisions and random number generations.