how to generate numbers to determine weighted race winners

Question

I need to find a way of picking winners, for like a race. Each racer has a weight of the chances of winning..

for instance

A - 25% chance to win
B - 10% chance to win
C - 25% chance to win
D - 10% chance
E - 10% chance
F - 20% chance

1) I need to pick the winner randomly but need to take the weighting in consideration.

2) I also need to pick the second most likely winner and the third...

I could pick the first by generating a random winner between 1-100 and basically splitting 100 among the racers depending on there chances like:

A = 1-25
B = 26 -35
C = 36-60.
etc
etc

Not sure how the stability of the above, but seemed okay.

Any more ideas?

Seems like you already have the answer to your question. Bear in mind that most random numbers will be zero-based. — David Grant, Oct 12 '12 at 15:24
Someone has already solved this problem http://stackoverflow.com/questions/1761626/weighted-random-numbers — andre, Oct 12 '12 at 16:04

Tom G · Accepted Answer · 2012-10-12T15:28:58.797

0

public class RaceWinners{
    public static void main(String[] args) {
        int[] percentages = {25,10,25,10,10,20};
        System.out.print(pickWinner(percentages));
    }

    //Returns the index of the winner(A = 0, B = 1, ...)
    private static int pickWinner(int[] percentages) {
        int randomNumber = (int)(Math.random() * 100);
        int countdown = randomNumber;
        for(int i = 0; i < percentages.length; i++) {
            countdown -= percentages[i];
            if(countdown < 0) {
                return i;
            }
        }
        return -1;
   }

}

edited Oct 12 '12 at 15:28

answered Oct 12 '12 at 15:23

Tom G

3,650
1
20
19

I think this algorithm is a bit partial in favor of the Racer who are in the beginning in array `percentages`. For eg, 3rd and 1st element should have equal probability of being picked randomly, but this algorithm will favor 3rd member. However, if we also randomize value of `i` this problem can be solved. – Aditya Jain Oct 12 '12 at 15:33

damoiser · Answer 2 · 2012-10-12T16:04:47.083

0

To determine the first rank you can do as you have described. But for the second, third,... places are little bit different (if A is first, then B has probability to be second p(B|A) := "the second is B given that the first is A", then B has not 10% to be second but a different value to be second and so on for the others members). Take a look at the condition probability (wiki: http://en.wikipedia.org/wiki/Conditional_probability )

this is a "pseudocode" that do the job

Ranking:
begin probability
a = 20%
b = 10%
...

calculate first
recalculate probability given that first is X (e.g. if first is A p(B|A), p(C|A),...)
calculate second (with the new probability, e.g. b = p(B|A), c = p(C|A),..)
recalculate probability given that first is X and second is Y
calculate third
etc..

NOTE: java random (Math.random) generates value between 0 and 0.999999... (e.g. [0, 1[ 0 is included but 1 not)

edited Oct 12 '12 at 16:04

answered Oct 12 '12 at 15:28

damoiser

6,058
3
40
66

Conditional probability will come in picture if it is confirmed that A won (may be during second run of the program), else probability calculated in first go should be ok. – Aditya Jain Oct 12 '12 at 15:42
@Aditya sure, the first go is ok. But for the others (to determine second, third,...etc if first is A or B or C...) you must use the conditional probability. – damoiser Oct 12 '12 at 15:52
@damoiser - I agree, what i ended up doing was once the winner was determined. I recalculated each racers probability and than proceeded to find next racer to complete. – user1555190 Oct 17 '12 at 09:11

how to generate numbers to determine weighted race winners

2 Answers2