How to choose a random number in a weighted way

Question

For example if I have an array of ints like this:

int[] list = {1, 4, 2};

And I want to choose one of these 3 numbers, but have the greater values get chosen more frequently:

1 get chosen 1/7 of the time
4 gets chosen 4/7 of the time
2 gets chosen 2/7 of the time

How can I write a function for this, if there isn't already one in Java.

Edit: I'm looking for an efficient solution, O(n) or better.

I'm going to be running this code a lot times in many threads. Building a new list is not sufficient.

Yes, I copied each element into an arraylist n times and then picked a random element from that list. It's not efficient though. — Josh, Nov 05 '14 at 07:08
Something like this? http://stackoverflow.com/questions/20327958/random-number-with-probabilities — Alexander_Winter, Nov 05 '14 at 07:10
@Alexander_Winter Yes, this is what I tried, but I need a better idea. I feel like there is a simple way of doing this without allocating more memory each time. — Josh, Nov 05 '14 at 07:14
Do you need to use always these probabilities, or they can change every time a random element is to be chosen? — icza, Nov 05 '14 at 07:19
@icza They can change, I need a general solution not just for this example. — Josh, Nov 05 '14 at 07:21

score 3 · Accepted Answer · answered Nov 05 '14 at 07:08

3

Accumulate the values in list and call the resulting sum S. Now generate a random number from 0 to S - 1. Iterate once more over list and for each element do the following: if the element is greater then S than choose that element. Otherwise decrease S by the element's value and continue on to the next element.

answered Nov 05 '14 at 07:08

Ivaylo Strandjev

69,226
18
123
176

It's worth noting that your number of entries in the list is very large this can be inefficient - in that case you build cumulative counts and use bisection on those counts. (but for small lists the bisection is more expensive) – Michael Anderson Nov 05 '14 at 07:15
@MichaelAnderson you can not solve a single iteration of such query in better complexity than O(N) because the input is of this magnitude. However if you have multiple queries you can optimize by using binary search. – Ivaylo Strandjev Nov 05 '14 at 07:16
@IvayloStrandjev I think that this is the best I'm going to be able to do. The only way I could do better is if I put them into the list n times each initially and then chose a rnd number 1 to n. This would be constant time, but it's a hack. Thanks. – Josh Nov 05 '14 at 07:23
@Josh please note the solution you propose will not be constant as you have to put the elements in the list aforehand. Thus for a single query you will perform just as well in terms of computation complexity, but will require more memory. If you are to perform multiple queries however the solution you propose may be better. Also if you are to make multiple queries you can use a combination of my solution with binary search(possibly with less memory overhead, but worse performance than your solution). – Ivaylo Strandjev Nov 05 '14 at 07:26
@IvayloStrandjev Ah, I see. I guess that the function that runs the query will be constant time but the work done beforehand will take cycles as well. I think I'll go with your answer above though, since there will only be one query per array. – Josh Nov 05 '14 at 07:33

icza · Answer 2 · 2020-10-11T19:11:26.593

You can simply use Math.random() to get a random number in the range of 0..1, and choose the number at the index whose cumulative weights "cover" the random number:

public static int random(int[] numbers, double[] weights) {
    double r = Math.random();
    
    double sum = 0;
    for (int i = 0; i < weights.length; i++) {
        sum += weights[i];
        if (r < sum)
            return numbers[i];
    }
    
    return 0; // You can only get here if sum weights is less than 1
}

This solution chooses you a random number according to the weights you provide in O(N). In most cases the algorithm doesn't even read the whole weights array. This is as good as it can get. Maximum steps is N, average number of steps is N/2.

Notes:

On average the method will be faster if bigger weights are at the beginning of the weights array.
The sum of the weights is expected to be 1. If the sum of the weights is less than 1, this method might return 0 (with a probability of 1-sum(weights)).

score 0 · Answer 3 · answered Nov 05 '14 at 07:14

1) Take the sum(S) of elements(A[i]) 2) Get Cumulative sum list(C[i]) 3) Get Random Value(R) from 0 to S-1 4) If R < C[i], your random value is A[i]

Cumulative Sum Range    Index in the Cumulative Array      Value in Original Array  
-----------------      -----------------------------      ----------------------
 0 <= x < 1                      0                            1
 1 <= x < 6                      1                            4
 6 <= x < 7                      2                            2

How to choose a random number in a weighted way

3 Answers3