# Is there a linear-time algorithm for randomly sampling weighted combinations?

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?

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

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.

• 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... Commented Mar 24 at 18:54
• @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$.
– orlp
Commented Mar 24 at 19:22
• @StevenStadnicki I expanded my answer a bit with the derivation of the probability for the 2-element case.
– orlp
Commented Mar 24 at 19:46
• @orip you're right; I had mentally flipped things in my head, mea culpa! Commented Mar 24 at 19:47