Heterogeneous Subset Sampling

摘要

In this paper, we consider the problem of heterogeneous subset sampling. Each element in a domain set has a different probability of being included in a sample, which is a subset of the domain set. Drawing a sample from a domain set of size n takes O(n) time if a Naive algorithm is employed. We propose a Hybrid algorithm that requires O(n) preprocessing time and O(n) extra space. On average, it draws a sample in O(1 + n{the square root of}(p~*)) time, where p~* is min (p_μ, 1 - p_μ) and p_μ denotes the mean of inclusion probabilities. In the worst case, it takes O(n) time to draw a sample. In addition to the theoretical analysis, we evaluate the performance of the Hybrid algorithm via experiments and present an application for particle-based simulations of the spread of a disease.