Adjust items chance to be selected from a list

Here we will engineer a random number generator that has a distribution that favors low values. You can use it to prefer items at the beginning of a list. To decrease the odds of something being selected, move that item down the list. You have a few options for how you want to move the item down the list. Lets review the random variable transformation first.

By applying the following function to a uniform random variable between 0 and 1:

index = Int(l*(1-r^(0.5)) # l=length, r=uniform random var between 0 and 1

You get a cool distribution that drastically reduces the odds of a larger index

p(0)=0.09751
p(1)=0.09246
p(2)=0.08769
p(3)=0.08211
p(4)=0.07636
p(5)=0.07325
p(6)=0.06772
p(7)=0.06309
p(8)=0.05813
p(9)=0.05274
p(10)=0.04808
p(11)=0.04205
p(12)=0.03691
p(13)=0.03268
p(14)=0.02708
p(15)=0.02292
p(16)=0.01727
p(17)=0.01211
p(18)=0.00736
p(19)=0.00249

Here is the distribution for a list of size 2

0.75139
0.24862

Size 3

0.55699
0.33306
0.10996

Size 4

0.43916
0.31018
0.18836
0.06231

Now lets discuss the two options for moving the items down the list. I tested two:

• ToEnd - Move most recently selected item to end of list

• Sort - Keep an associated array of the number of times each item has been selected and sort the list from least to most selected.

I created a simulation to pick from a list and examine the standard deviation of the count that each item was selected. The lower the standard deviation the better. For example, 1 simulation for a list of 10 items where 50 selections where made created the spread:

{"a"=>5, "b"=>5, "c"=>6, "d"=>5, "e"=>4, "f"=>4, "g"=>5, "h"=>5, "i"=>6, "j"=>5}

The Standard Devation for this simulation wa

the general strategy for picking a weighted random element from a list is this: give each item a weight. normalise, so that the total weight is 1. (so to start with, every item has weight 1/n). sort your list by weight. now pick a random number between 0 and 1, and go down the list accumulating totals till you cross your number. e.g. if your weights are [0.4, 0.3, 0.2, 0.1] and your random number is 0.63215, your first two steps have total = 0.4, total = 0.7 and then notice that 0.7 is greater than 0.63215 so you return the second element.

once you pick an element, you adjust its weighting downwards (you'll need to experiment with downweighting formulas till you find one that works for you, the simplest is just to multiply it by some constant fraction each time), and then renormalise and repeat.

note that this is fairly inefficient if you have a lot of elements since it is O(n) in the length of the list, but it shouldn't matter in practice unless you're doing this in an inner loop that needs to be heavily optimised, or similar. if it turns out to be an issue you could look into geometric data structures like range trees to optimise the lookup.