How to constantly adjust the weight for random number generator so the results can be distributed more evenly?

Question

I'm trying to come up with a solution that can generate random integers with more evenly distributed results.

The basic idea is this:

For example, I want to generate a random integer between 0 - 9. As each new random number is generated, I also keep a list that counts how many times each number has been generated. And for example, if the first result is 5, then 5 will have a count of 1, which will make the number 5 less likely to be generated for the next time, because other numbers only have a count of 0.

At first, I was thinking about doing this just like a regular weighted random number generator, which will sum up all the weights and create a random number in the range of the sum, and see which result the random number falls into.

However, the weight list still has the same order as the selections. For example, if we have 4 choices: 0, 1, 2, 3, and they have weights of 1, 2, 3, 4. The normalized non-weighted probabilities would be 25% for each selection, and the normalized weighted probabilities would be 10%, 20%, 30%, and 40%. This means that the normalized random number has to be 0 - 0.1 to roll 0, and 0.1 - 0.3 to roll 1, and so on.

The problem with this is that because a random number generator should more or less have evenly distributed results in the long run, it may produce less ideal results if the weights are still aligned in the same order of the available results. Using the example from above. Let's say the random number generator rolls a 0.59, which will result in the number 2 gets selected. And now since number 2 is selected, the weight on other selections should increase (so 2 is less likely to be selected next time). Which means that now the weight range for selecting number 3 will increase from 0.6 - 1.0, and will probably cover 0.59, which was within the range for number 2 in the last operation. By design, a larger range of weight should result in a greater chance for the represented result to be selected. However, since 0.59 was rolled last time, by the nature of a reliable random number generator, the chance of getting 0.59 this time should be less than getting another float between 0 - 1, which will in turn lower the chance of the number 3 (which will now be selected if 0.59 is rolled) get selected.

I think I currently have a solution that will involve creating a really big list, and it feels very inelegant, and is probably very easy to hit the size limit for a list. So I would like to know a more elegant solution to this problem.

By the way, here (in Unity C#) is how I currently calculate the weight (which is probably not important):

// Get the largest weight number
int largestWeight = Mathf.Max(weightList.ToArray()); 

// Get list for weights adjusted based on the weight factor
List<int> adjustedWeights = new List<int>(weightList);
adjustedWeights.ForEach(w => w = Mathf.RoundToInt(Mathf.Pow((largestWeight - w + 1), weightFactor)));

This weightList is a list of counts of how many times each result has been selected, and is maintained so that if every count is greater than 0, all count will - 1, which keeps the lowest count always be 0.

Answer 1

It appears that you want to simulate a weighted choice described in my section "Weighted Choice Without Replacement (Multiple Copies)". In your case, it could work as follows:

1. Give each item the same weight, specified as a positive integer. For example, give a weight of 20 to each item.

2. Use a weighted-choice-with-replacement algorithm. Perhaps the simplest is rejection sampling, described as follows. Assume that the highest weight is max and each weight is 0 or greater. To choose an integer in [1, weights.Count] using rejection sampling:

   1. Choose a uniform random integer i in [1, weights.Count].
   2. With probability weights[i]/max, return i. Otherwise, go to step 1.

   There are many other ways to make a weighted choice besides rejection sampling; see my note on weighted choice algorithms.

3. As each item is chosen, reduce its weight by 1 to make it less likely to be chosen.

4. If all the weights are 0, assign each item the same weight chosen in step 1 (in this example, 20).

Since you mention Unity, your goal is probably to make a game that controls which random numbers appear, to make the random outcomes appear "fairer" to players. However, you should also consider whether it may be better to make an independent uniform random choice instead, especially if you care whether players could gain an unfair advantage by predicting the random outcomes.

Answer 2

Alternative to Peter O idea to use positive growing weight, start with count of 1 and increase it for each sample, but use INVERSE of count as weight. Thus value with more count would less likely to be selected, similar in idea to inverse weighting.

Some code (untested! based on Math.Net numerics)

import MathNet.Numerics.Distributions;

static void Main() {

    const int N = 4;

    var counts  = new int [N] {1, 1, 1, 1};
    var weights = new double [N] {1.0, 1.0, 1.0, 1.0};

    while (true) {
        int v = Categorical.Sample(weights[k]); // sample one value in [0...N)
        // update counts and weights
        counts[v] += 1;
        weights[v] = 1.0/(double)counts[v];
        
        // use v here for something
        ...
    }
}

You could invent a bit more generic weighting, one important thing to remember, counts go to denominator.

F.e. that might work better

weights[v] = 1.0/(1.0 + .5*(double)counts[v]);

or that

var squared => (x) => x*x;

weights[v] = 1.0/(7.0 + .25*squared((double)counts[v]));

or that

weights[v] = 1.0/(3.0 + Math.Sqrt((double)counts[v]));

As soon as it is monotonically growing function of counts in denominator of weights formula, it will alter the probabilities in a desired way