How can a random value be spreaded with a given probability?

Question

For an AI I'm using random values to decide which action to perform next (only when there is nothing rule based to do). Some of the actions should be picked more often than others.

The idea is to define a group of probabilities and pick an action from the probs 2 twice as often then an action with 1, the action 4 with a five times higher probability.

action prob
0         1
1         2 (twice as often than 1)
2         2
3         2
4         5 (5 times morer often than 1)

Is there a wellknown algorithm for this behaviour or a more mathematical approach?

My test implementation is somewhat awkward. I would prefer to avoid the inner loop.

public static void main(String[] args) {
    int[] counts = new int[5];
    int[] props = { 1 ,2 ,2 ,2 ,5 };
    int sum = 0;
    for (int i = 0; i < props.length ; i++) {
        sum += props[i];
    }
    for ( int i = 0 ; i < 100 ; i++ ) {
        int rand = (int) (Math.random() * sum);
        for ( int j = 0 ; j < props.length ; j++ ) {
            if ( rand - props[j] <= 0 ) {
                counts[j] = counts[j] + 1;
            }
        }
    }
    for ( int j = 0 ; j < props.length ; j++ ) {
        System.out.println( "count " + j + "=" + counts[j] );
    }
}

Depending on the test run it produces results like:

count 0=14
count 1=25
count 2=25
count 3=25
count 4=50

saagarjha · Answer 1 · 2015-08-16T19:32:06.990

3

How about an array with the values, with more common values appearing more often:

int[] actions = {0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4} // 12 values.

You can then just do

int action = actions[Math.random() * actions.length]

to get a weighted random action.

edited Aug 16 '15 at 19:32

answered Aug 16 '15 at 17:18

saagarjha

2,221
1
20
37

I think shuffling `actions` elements would give better weighted distribution. – John Aug 16 '15 at 19:49
It doesn't really matter, since Math.random() is uniformly distributed, right? Of course you can if you want. – saagarjha Aug 16 '15 at 19:54
Depends on how precise random do you need. It is not really unfiorm, nor the Linear congruential generator is the most precise option. You might find this interesting: http://stackoverflow.com/questions/453479/how-good-is-java-util-random – John Aug 16 '15 at 20:01
Might be a bit nit-picking that is :) I upvoted the answer. – John Aug 16 '15 at 20:04
How would you plan to shuffle `actions`, anyways? Wouldn't you have to use Math.random()? – saagarjha Aug 16 '15 at 20:26
Have to, no. Would I ? Probably. I see where you are going with this, but my suggestion was to not have same weights adjacented to each other, that is all. – John Aug 16 '15 at 20:37

score 2 · Accepted Answer · answered Aug 16 '15 at 17:09

you are looking to solve the equation:

p0 + p1 + p2 + p3 + p4 = 1
p0 = p
p1 = 2p
p2 = 2p
p3 = 2p
p4 = 5p

This is a set of linear equations and can be solved pretty easily using linear algebra.

In this example:

p + 2p + 2p + 2p + 5p = 1
12p = 1
p = 1/12
p0 = 1/12
p1 = p2 = p3 = 2/12
p5 = 5/12

You can use a single uniformly distributed number in [0,1) x to chose which event happens by setting an array:

aux[0] = 0
aux[i] = aux[0] + p_{i-1}

so in your example:

aux = [0,1/12,3/12,5/12,7/12,1]

Then, draw a value for x, and do a binary search on i to find the closest value which is higher than x, and that's your event.

How can a random value be spreaded with a given probability?

2 Answers2