Weighted random numbers: boundary case

Question

In reference to the top answer given in this post, I've noticed that it fails for a boundary case when rnd=sum_of_weight. The fix is to generate random numbers in [0,sum_of_weight), however i was wondering why the code fails for this boundary case? Is it a flaw in the algorithm?

EDIT: Also, does the weight array need to be sorted high to low? It seems so, based on the subtraction loop.

Below is the Java code that implements the pseudo-code in the above post.

int sum_of_weight = 0;



int []choice_weight = {50, 15, 15, 10, 10};         // percentages
int num_choices = choice_weight.length;

public void init() {

    for (int i = 0; i < num_choices; i++) {
        sum_of_weight += choice_weight[i];
    }
}

int next() {
    int rnd = (int)Util.between(0, sum_of_weight);// random(sum_of_weight);
    rnd=sum_of_weight;                      // force the exception by hitting boundary case
    //System.out.print("rnd=" + rnd);
    for (int i = 0; i < num_choices; i++) {
        if (rnd < choice_weight[i])
            return i;
        rnd -= choice_weight[i];
    }

    throw new RuntimeException("should never get here for rnd=" + rnd);
}

public static void main(String[] args) {
    SimpleWeight sw = new SimpleWeight();
    sw.init();
    for (int i=0; i < 10;i++) {
        System.out.println(sw.next());
    }
}

score 3 · Accepted Answer · edited May 23 '17 at 11:47

Step 2 of the algorithm you link to states:

2) pick a random number between 0 and less than the sum weights.

To me, this reads clearly and unambiguously that the correct way is to pick a number from [0,sum_of_weight). Picking a number from a different range (e.g. any range that includes sum_of_weight) isn't a flaw in the algorithm, it's a flaw in the implementation of that algorithm.

edit No, the weights do not need to be sorted for the algorithm to work.

score 0 · Answer 2 · answered May 25 '12 at 14:57

For those that find it useful, here is another implementation of the above. Open to feedback too if you want to make it better. I'm still a beginner.

import java.util.Random;

public class WeightedRandom {

    private int choiceWeight[];
    private int numChoices = 0;
    private int i = 0;
    private Random r = new Random();

    public WeightedRandom() {
        this.choiceWeight = new int[] { 60, 35, 5 };
        this.numChoices = choiceWeight.length;
    }

    public WeightedRandom(int[] choiceWeight) {
        this.choiceWeight = choiceWeight;
        this.numChoices = this.choiceWeight.length;
    }

    public int weightedRandomGenerator() {

        int sumOfWeight = 0;
        for (int i = 0; i < numChoices; i++) {
            sumOfWeight += choiceWeight[i];
        }

        int randomNumber = r.nextInt(sumOfWeight);
        for (int i = 0; i < numChoices; i++) {
            if (randomNumber < choiceWeight[i])
                return i;
            randomNumber -= choiceWeight[i];
        }

        throw new RuntimeException("should never get here for RandomNumber = " + randomNumber);
    }

    public void printWeightedAverage(int numberOfIterations) {
        int numberCount[] = new int[numChoices];

        for (int n = 0; n < numberOfIterations; n++) {
            i = weightedRandomGenerator();
            numberCount[i]++;
        }

        for (int n = 0; n < numChoices; n++)
            System.out.println("Occurance of " + n + " = " + (((double) numberCount[n]) / numberOfIterations) * 100 + "%");
        System.out.println("--------");
    }

    public static void main(String[] args) {

        WeightedRandom wr = new WeightedRandom();
        WeightedRandom wr2 = new WeightedRandom(new int[] { 49, 25, 15, 5, 3, 2, 1 });
        wr.printWeightedAverage(100_000_000);
        wr2.printWeightedAverage(100_000_000);
    }

}

Weighted random numbers: boundary case

2 Answers2