9
$\begingroup$

For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a_1, a_2, \ldots, a_n$ with weights $w_1, w_2, \ldots, w_n$ respectively. The goal is to select a subset of size $k$ such that the probability of selecting the subset $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ is exactly $\dfrac{w_{i_1}\cdot w_{i_2}\cdots\cdot w_{i_k}}{\sum_{S_k\subseteq S, |S_k|=k}(\prod_{i\in S_k}w_i)}$. If $k=1$ then this is the usual selection from a weighted distribution and can easily be done in time $O(n)$ (or even $O(\log n)$ per sample with $O(n)$ preprocessing). If the $w_i$ are all equal then this is the usual uniform selection of a combination of $k$ things from a set of size $n$, and there are several well-established algorithms to do this in time $O(n)$. But I don't know of any algorithm for the generalized problem that runs faster than the naive version in $\Theta_n({n\choose k})=\Theta_n(n^k)$ time, and even a dip into TAOCP didn't turn up anything. Are there any known fast algorithms for this problem?

$\endgroup$
2
  • $\begingroup$ A strict subset, so sampling without replacement, right? $\endgroup$
    – orlp
    Commented Mar 24 at 17:36
  • $\begingroup$ @orlp That's correct. $\endgroup$ Commented Mar 24 at 18:51

1 Answer 1

13
$\begingroup$

There is a very simple $O(n \log k)$ algorithm described in Weighted random sampling with a reservoir by Pavlos S. Efraimidis and Paul G. Spirakis, which can be summarized as:

Associate a value $r_i^{1/w_i}$ with $a_i$, where $r_i$ is an independent random uniform value on $[0, 1]$. Sort the elements by their associated values; the $k$ largest values indicate the desired subset.

With a priority queue of size $k$ you don't need to do a full sort and can get away with $O(n \log k)$.


To get some mathematical intuition for why this works, you can look at the $k = 2$ case. Let the cumulative density function $F_w(x) = \Pr[r^{1/w} \leq x] = \Pr[r \leq x^w] = x^w$, which gives the probability density function $f_w(x) = wx^{w-1}$. Then we have

$$\Pr[r_1^{1/w_1} \leq r_2^{1/w_2}] = \int_{0}^1 F_{w_1}(x)f_{w_2}(x)dx = \int_{0}^1w_2x^{w_1+w_2-1}dx = \frac{w_2}{w_1 + w_2}.$$

For the full method I recommend reading the paper.

$\endgroup$
4
  • $\begingroup$ Are you sure that's $r_i^{1/w_i}$ and not $r_i/w_i$? In the case of sampling a singleton from two things with weights $1$ and $100$ that would be comparing $R$ with $R^{1/100}$ and the latter is exponentially smaller than the former, but dividing out would seem to be correct there... $\endgroup$ Commented Mar 24 at 18:54
  • 1
    $\begingroup$ @StevenStadnicki I think you're confused about the effect of exponentiation here. Consider $R = 0.5$, then $R^{1/100}$ is not 'exponentially smaller' than $R$, in fact $R^{1/100} \approx 0.9931$. $\endgroup$
    – orlp
    Commented Mar 24 at 19:22
  • $\begingroup$ @StevenStadnicki I expanded my answer a bit with the derivation of the probability for the 2-element case. $\endgroup$
    – orlp
    Commented Mar 24 at 19:46
  • $\begingroup$ @orip you're right; I had mentally flipped things in my head, mea culpa! $\endgroup$ Commented Mar 24 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.