# 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.

• Could you please explain how these weights would be used to change the probabilities? It's unclear how you have employed them in your example. Are you perhaps looking for three distributions $\alpha,\beta,\gamma$ so that when three independent random variables are drawn, $A\sim\alpha,$ $B\sim\beta,$ and $C\sim\gamma,$ the six possible orderings of those variables occur with specified probabilities?
– whuber
Commented Dec 21, 2022 at 18:35
• In the desired behavior, the weights correspond to the probability that this item will be chosen next, e.g: For the first item $P(A) = \frac{3}{6}, P(B) = \frac{2}{6}, P(C) = \frac{1}{6}$. If we drew $A$, then the next item $P(B) = \frac{2}{3}, P(C) = \frac{1}{3}$ Yes, a different distribution for each weight would be fine. I'm looking for a way to map each weight to a distribution, such as $y_i \sim \mathcal{N}(w_i,\,1)$ (This didn't work either) Commented Dec 21, 2022 at 19:38
• The distribution doesn't matter, since you're only concerned about order. You can stick to uniform distributions. I still don't understand the weights, because it now sounds like you are drawing values conditionally on previous values rather than independently. If that's the case, there are plenty of easily computed solutions. All you have to do is divide the cube $[0,1]^3$ into six regions whose volumes equal the six desired probabilities and sample the cube uniformly.
– whuber
Commented Dec 21, 2022 at 20:06
• I meant that the behavior I wanted to model was conditional. What I'm looking for is independent sampling. Commented Dec 21, 2022 at 20:19
• What I want to do is: For each weight, sample some distribution. Take these values, and use them as the sorting keys to sort the items. Commented Dec 21, 2022 at 20:30

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.

• This solution is incapable of reproducing arbitrary probability distributions on the set of all six permutations, because that space of distributions has five dimensions but you specify only three parameters. It's difficult to determine precisely what problem it is solving.
– whuber
Commented Dec 22, 2022 at 15:48
• Imagine you want to shuffle a playlist, but you don't want it to be truly random, you want it to be biased to play songs you like first. We have songs $[A, B, C]$, and ratings/scores $[3,2,1]$. We want the order of the playlist to reflect if you had performed a biased selection without replacement until all the songs were added. In this example, we expect the first song to be $A$ $\frac{1}{2}$ the time. Commented Dec 22, 2022 at 21:00
• For each song, we take the weight, and use it to sample a value. We then sort the songs on the values we just sampled. If we use the solution Peter posted, we get the same biased shuffle as using roulette wheel selection. Commented Dec 22, 2022 at 21:05