What sampling function would I use to create a biased, random ordering? I can create a random ordering for a list $L$ by sampling values $y$ from a uniform distribution $U(0,1)$ for each item. If I sort $L$ on $y$, I can perform a simple shuffle.
I'd like to use a list of weights $W$ to bias this order. When sorted, this would be equivalent to roulette wheel selection, or a weighted selection of $len(L)$ items without replacement from $L$.
I know several ways I could do this procedurally, but what I'm curious about is:
Is there a sampling function $y_i \sim f(w_i)$ that would also produce these permutations with the same frequency as roulette wheel selection?
For example, if $L=[A,B,C]$, and $W=[3,2,1]$, then when sorted in reverse, I should see:




Permutation
frequency




ABC
$\frac{1}{2} \times \frac{2}{3}$ = $\frac{1}{3}$


ACB
$\frac{1}{2} \times \frac{1}{3}$ = $\frac{1}{6}$


BAC
$\frac{1}{3} \times \frac{3}{4}$ = $\frac{1}{4}$


BCA
$\frac{1}{3} \times \frac{1}{4}$ = $\frac{1}{12}$


CAB
$\frac{1}{6} \times \frac{3}{5}$ = $\frac{1}{10}$


CBA
$\frac{1}{6} \times \frac{2}{5}$ = $\frac{1}{15}$




I tried using an exponential distribution $y_i \sim Exp(1)*w_i$, but the results did not match the expected frequencies in my example.
 A: Peter's posted a related answer which works: https://stackoverflow.com/questions/63850562/infinite-scroll-algorithm-for-random-items-with-different-weight-probability-t
His solution was $ln(U(0,1))/w$
I spent some time trying to understand why it works, here's my logic:
Taking the log of samples from the standard uniform distribution  is equivalent to using an exponential distribution:
$$y=ln(x), x \sim U(0,1)$$
$$y=-x, x \sim Exp(1)$$
Incorporating the weight $w$, we can write:
$$y=-x/w, x \sim Exp(1)$$
This is equivalent to:
$$y=-x, x \sim Exp(w)$$
Since the samples are just used for ordering, we can re-scale the weights any way we like. It becomes clearer if we normalize them so they sum to 1. Let's define these as $probs$
$$weights = [3,2,1]$$
$$probs = weights/sum(weights) = \left[ \frac{1}{2}, \frac{1}{3}, \frac{1}{6} \right]$$
If we go back to the roulette wheel selection example, these are the probabilities found on the initial selection.
For selection without replacement, it's more efficient to use a new wheel after each round and re-scale the weights again minus the selected items. However, it's completely valid to re-use the wheel, and just ignore spins that select an item already selected.
Going back to the exponential distribution, we should also note that it is the continuous analogue of the geometric distribution, that is, how many trials do we need to get one success.
Then it follows that sampling $x \sim Exp(p)$ yields how many units of time will it take before this event occurs.
The expected value for each element of $probs$:
$$[2, 3, 6]$$
And since we desire larger values to occur with more likely events, we can just flip the sign of our sample. (We could also just sort in the opposite direction).
$$y=-x, x \sim Exp(w)$$
This is a memory-less way to assign ordering keys to items/events, given some weight/probability of occurrence.
