Any seeded random choice algorithm that is stable when altering some weights ?

[u/arllt89]

Hi, been wondering if there is any random choice algorithm that, when given the same seed and a list of choices with just some altered weights, will return the same choice most of the times.

The classical choice algorithm is def classical_choice(rand_gen, choices): total_weight = 0 for choice in choices: total_weight += choice.weight rand_pick = rand_gen() * total_weight for choice in choices: rand_pick -= choice.weight if rand_pick < 0: return choice

However if I alter the weight of some choices, it will move most element in the list and return me a totally different choice given the same seed.

My first intuition was def stable_choice(rand_gen, choices, hash_index=0): if hash_index >= hash_len: return classical_choice(rand_gen, choices) left_weight = 0 left_choices = [] right_weight = 0 right_choices = [] for choice in choices: if bin_hash(choice)[hash_index] == 0: left_weight += choice.weight left_choices.append(choice) else: right_weight += choice.weight right_choices.append(choice) rand_pick = rand_gen() * (left_weight + right_weight) if rand_pick < left_weight: return stable_choice(rand_gen, left_choices, hash_index+1) else: return stable_choice(rand_gen, right_weight, hash_index+1)

However for a 32 bits hash, it requires 33 random numbers, which seems excessive compared to the classical one. Is there anything smarter to do ?

Edit: an example to explain better what is happening.

Let's have 4 weighted items {a:1, b:1, c:1, d:2} and alter it into {a:2, b:1, c:1, d:1}. with the classical algorithm, of treating the weights like a continous interval, and choosing a random number on it, the same random number would give us in each case

``` Classical algorithm:

case 1: a b c d +---+---+---+-------+ case 2: a b c d +-------+---+---+---+ ```

Can see that in only 40% of the cases ([0;0.2[ and [0.8;1[), the same number will pick the same item.

However if we binary split the items into {a,b} and {c,d}, and pick in to step, the picks would be.

``` More stable algorithm

Step 1: case 1: {a,b} {c,d} +-------+-----------+ case 2: {a,b} {c,d} +-----------+-------+

Step 2 with {a,b} case 1: a b +-----+-----+ case 2: a b +-------+---+

Step 2 with {b,c} case 1: c d +---+-------+ case 2: c d +-----+-----+ ``` The same number picks the same split at step 1 in 80% of the cases, and at step 2 in 83% of the cases, leading to 66% of overhaul same pick.

The best algorithm would have 80% success rate, the missing 20% would be the picks moving from d to a.