Return to Answer

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a series of items efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_1 = \text{next}(10, 0)$
$a_2 = \text{next}(9, a_1)$
$a_3 = \text{next}(8, a_2)$
$\dots$
$a_{10} = \text{next}(1, a_9)$

While drawing that ascending series $(a_i)$ of uniformly distributed numbers, iterate over the set of probabilities $P$ which represents your arbitraty (yet finite) distribution. Let $0 \leq k < |P|$ be the iterator and $p_k \in P$. After drawing $a_i$, increment $k$ zero or more times until $\sum p_0 \dots p_k > a_i$. Then add $p_k$ to your sample and move on with drawing $a_{i+1}$.

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a sample efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

While drawing that ascending series $(a_i)$ of uniformly distributed numbers, iterate over the set of probabilities $P$ which represents your arbitraty (yet finite) distribution. Let $0 \leq k < |P|$ be the iterator and $p_k \in P$. After drawing $a_i$, increment $k$ zero or more times until $\sum p_0 \dots p_k > a_i$. Then add $p_k$ to your sample and move on with drawing $a_{i+1}$.

Example with the op's set $\{(1, 0.04), (2, 0.5), (3, 0.46)\}$ and sample size $N = 10$:

i  a_i    k  Sum   Draw
0  0.031  0  0.04  1
1  0.200  1  0.54  2
2  0.236  1  0.54  2
3  0.402  1  0.54  2
4  0.488  1  0.54  2
5  0.589  2  1.0   3
6  0.625  2  1.0   3
7  0.638  2  1.0   3
8  0.738  2  1.0   3
9  0.942  2  1.0   3

Sample: $(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a series of items efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_1 = \text{next}(10, 0)$
$a_2 = \text{next}(9, a_1)$
$a_3 = \text{next}(8, a_2)$
$\dots$
$a_{10} = \text{next}(1, a_9)$

Now while drawing that ascending series, parallel iterate over your set. For each drawn ascending random number, add the corresponding set item to your result.

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a series of items efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_1 = \text{next}(10, 0)$
$a_2 = \text{next}(9, a_1)$
$a_3 = \text{next}(8, a_2)$
$\dots$
$a_{10} = \text{next}(1, a_9)$

While drawing that ascending series $(a_i)$ of uniformly distributed numbers, iterate over the set of probabilities $P$ which represents your arbitraty (yet finite) distribution. Let $0 \leq k < |P|$ be the iterator and $p_k \in P$. After drawing $a_i$, increment $k$ zero or more times until $\sum p_0 \dots p_k > a_i$. Then add $p_k$ to your sample and move on with drawing $a_{i+1}$.

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.

I had the same problem: https://stats.stackexchange.com/questions/178991/sampling-from-a-probability-list-set-efficiently. In other words: Given a set where each item has a probability and whose items' probabilities sum up to one. I want to draw a series of items efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_1 = \text{next}(10, 0)$
$a_2 = \text{next}(9, a_1)$
$a_3 = \text{next}(8, a_2)$
$\dots$
$a_{10} = \text{next}(1, a_9)$

Now while drawing that ascending series, parallel iterate over your set. For each drawn ascending random number, add the corresponding set item to your result.

If you are interested in the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a series of items efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_1 = \text{next}(10, 0)$
$a_2 = \text{next}(9, a_1)$
$a_3 = \text{next}(8, a_2)$
$\dots$
$a_{10} = \text{next}(1, a_9)$

Now while drawing that ascending series, parallel iterate over your set. For each drawn ascending random number, add the corresponding set item to your result.

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.