1
$\begingroup$

Here's my problem: I have $N$ sets of integers $S_i$ where $|S_i| = n_i \forall i \in [1,N]$ each with non-uniform weights $W_i = \{w_{i,1}, ..., w_{i,n_i}\}$ such that $\sum_{j}{w_{i,j}} = 1$. I want to sample $m$ unique lists $P_{k \in [1,m]} = (p_{k,1}, ...,p_{k,i}, ...,p_{k,N})$ of $N$ integers (including duplicates, and ordering matters), with each element $p_{k,i} \in S_i$.

The naive implementation I use as a proof of concept to generate a new unique list $P_k$: I pick an element from $S_1$ at random according to the weights $W_1$, then I pick an element from $S_2$ with weights $W_2$, etc... until I have $N$ elements to create a candidate list. If this list is not unique among exiting lists, I discard it and start again at the top, otherwise it becomes the list $P_k$. This is repeated until I get $m$ unique lists.

Although it works and gives me the correct result, this is very inefficient as I get more and more duplicate sets as $m$ increases, and as the weights $w_i$ diverge from a uniform distribution.

Here's an example with disjoint sets: $N=3, n_1=4, n_2=3, n_3=5$ $$ S_1 = \{1, 2, 3, 4\}; S_2 = \{11, 12, 13\}; S_3 = \{21, 22, 23, 24, 25\}; $$ With $m=3$, a possible sampling would be: $$ P_1=(1, 11, 21), P_2=(1, 12, 24), P_3=(3, 12, 22) $$

All the sampling algorithms I have found either assume uniform distribution, or require "flattening" my problem from $N$ sets to one set of all possible combinations (and calculating the corresponding weights). Although the computation of the weight for a specific combination is trivial, it is not feasible for the size and number of sets I'm working with: $2 \leq N \leq 20$ and $2 \leq n_i \leq 50$. Typically $1 \leq m \leq 1000$ and $m \leq \prod_{i \in [1,N]}{n_i}$.

Does anyone has an idea to replace my current naive solution? I am looking for an algorithm that would allow me to make that sampling without replacement a. directly from $S_i$ and $W_i$, or b. a 1D weighted sampling algorithm that does not require pre-computing all possible combinations and corresponding weights.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

There is a mapping from each possible list $P$ to an interval $[\ell,r)$ contained in $[0,1)$, such that the resulting intervals (if you consider all possible lists) form a partition of $[0,1)$.

In particular, if $P=(p_1,\dots,p_N)$ and $N\ge 1$, define

$$f(P) = w_{p_N} f(p_1,\dots,p_{N-1}) + w_1 + w_2 + \dots + w_{p_N-1};$$

and if $N=0$, define $f(p_1) = [0,1)$. Also, given $x \in [0,1)$, you can find $P$ such that $x \in f(P)$ in a straightforward way.

Now one way to sample from your distribution is to sample a real number $x_1$ uniformly at random from $[0,1)$, then map it back to the corresponding list $P_1$, i.e., find $P_1$ such that $x_1 \in f(P_1)$, and output $P$.

If you want to sample a second list $P_2$ that is guaranteed to be different from $P_1$, sample $x_2$ uniformly at random from $[0,1) \setminus f(P_1)$, find $P_2$ such that $x_2 \in f(P_2)$, and output $P_2$.

To sample a third list $P_3$ that is different from $P_1,P_2$, sample $x_3$ uniformly at random from $[0,1) \setminus (f(P_1) \cup f(P_2))$, find $P_3$ such that $x_3 \in f(P_3)$, and output $P_3$.

Repeat. Note that $[0,1) \setminus (f(P_1) \cup \cdots \cup f(P_m))$ can be expressed as a disjoint union of $m+1$ intervals, and you can sample uniformly from it in $O(m)$ time, so the running time to generate $m$ different $P$'s is something like $O(m^2N)$. This should be good enough to accommodate your parameter settings. (In fact, by storing that union of intervals in a self-balancing binary tree structure, you can sample in $O(\log m)$ time, so you can reduce the total running time to $O(mN\log m)$, but that probably won't be necessary for your parameter settings.)

$\endgroup$
2
  • $\begingroup$ Thanks @D.W. after working on it on my side, your solution is very similar to what I came up with. But instead of picking from $[0,1) \setminus (f(P_1) \cup... \cup f(P_{m-1}))$, I update the partition of $[0,1)$ by setting the weights of the previously sampled lists $P_1, ..., P_m$ to 0. I keep track of the existing lists $P_1, ..., P_m$ in a tree. With a lot of memoization, I have very reasonable run times for $m <= 100000$ which is well beyond the requirements. $\endgroup$
    – Montspy
    Jun 29, 2022 at 22:24
  • $\begingroup$ @Montspy great, I'm glad that worked out! Thanks for reporting back about what ultimately worked well for you. $\endgroup$
    – D.W.
    Jul 3, 2022 at 3:24

Your Answer

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

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