Generate A Weighted Random Number

I'm trying to devise a (good) way to choose a random number from a range of possible numbers where each number in the range is given a weight. To put it simply: given the range of numbers (0,1,2) choose a number where 0 has an 80% probability of being selected, 1 has a 10% chance and 2 has a 10% chance.

It's been about 8 years since my college stats class, so you can imagine the proper formula for this escapes me at the moment.

Here's the 'cheap and dirty' method that I came up with. This solution uses ColdFusion. Yours may use whatever language you'd like. I'm a programmer, I think I can handle porting it. Ultimately my solution needs to be in Groovy - I wrote this one in ColdFusion because it's easy to quickly write/test in CF.

public function weightedRandom( Struct options ) {

    var tempArr = [];

    for( var o in arguments.options )
    {
        var weight = arguments.options[ o ] * 10;
        for ( var i = 1; i<= weight; i++ )
        {
            arrayAppend( tempArr, o );
        }
    }
    return tempArr[ randRange( 1, arrayLen( tempArr ) ) ];
}

// test it
opts = { 0=.8, 1=.1, 2=.1  };

for( x = 1; x<=10; x++ )
{
    writeDump( weightedRandom( opts ) );    
}

I'm looking for better solutions, please suggest improvements or alternatives.

Rejection sampling (such as in your solution) is the first thing that comes to mind, whereby you build a lookup table with elements populated by their weight distribution, then pick a random location in the table and return it. As an implementation choice, I would make a higher order function which takes a spec and returns a function which returns values based on the distribution in the spec, this way you avoid having to build the table for each call. The downsides are that the algorithmic performance of building the table is linear by the number of items and there could potentially be a lot of memory usage for large specs (or those with members with very small or precise weights, e.g. {0:0.99999, 1:0.00001}). The upside is that picking a value has constant time, which might be desirable if performance is critical. In JavaScript:

function weightedRand(spec) {
  var i, j, table=[];
  for (i in spec) {
    // The constant 10 below should be computed based on the
    // weights in the spec for a correct and optimal table size.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
    for (j=0; j<spec[i]*10; j++) {
      table.push(i);
    }
  }
  return function() {
    return table[Math.floor(Math.random() * table.length)];
  }
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...

Another strategy is to pick a random number in [0,1) and iterate over the weight specification summing the weights, if the random number is less than the sum then return the associated value. Of course, this assumes that the weights sum to one. This solution has no up-front costs but has average algorithmic performance linear by the number of entries in the spec. For example, in JavaScript:

function weightedRand2(spec) {
  var i, sum=0, r=Math.random();
  for (i in spec) {
    sum += spec[i];
    if (r <= sum) return i;
  }
}
weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution...

Generate a random number R between 0 and 1.

If R in [0, 0.1) -> 1

If R in [0.1, 0.2) -> 2

If R in [0.2, 1] -> 3

If you can't directly get a number between 0 and 1, generate a number in a range that will produce as much precision as you want. For example, if you have the weights for

(1, 83.7%) and (2, 16.3%), roll a number from 1 to 1000. 1-837 is a 1. 838-1000 is 2.

I use the following

function weightedRandom(min, max) {
  return Math.round(max / (Math.random() * max + min));
}

This is my go-to "weighted" random, where I use an inverse function of "x" (where x is a random between min and max) to generate a weighted result, where the minimum is the most heavy element, and the maximum the lightest (least chances of getting the result)

So basically, using weightedRandom(1, 5) means the chances of getting a 1 are higher than a 2 which are higher than a 3, which are higher than a 4, which are higher than a 5.

Might not be useful for your use case but probably useful for people googling this same question.

After a 100 iterations try, it gave me:

==================
| Result | Times |
==================
|      1 |    55 |
|      2 |    28 |
|      3 |     8 |
|      4 |     7 |
|      5 |     2 |
==================

Here are 3 solutions in javascript since I'm not sure which language you want it in. Depending on your needs one of the first two might work, but the the third one is probably the easiest to implement with large sets of numbers.

function randomSimple(){
  return [0,0,0,0,0,0,0,0,1,2][Math.floor(Math.random()*10)];
}

function randomCase(){
  var n=Math.floor(Math.random()*100)
  switch(n){
    case n<80:
      return 0;
    case n<90:
      return 1;
    case n<100:
      return 2;
  }
}

function randomLoop(weight,num){
  var n=Math.floor(Math.random()*100),amt=0;
  for(var i=0;i<weight.length;i++){
    //amt+=weight[i]; *alternative method
    //if(n<amt){
    if(n<weight[i]){
      return num[i];
    }
  }
}

weight=[80,90,100];
//weight=[80,10,10]; *alternative method
num=[0,1,2]

This is more or less a generic-ized version of what @trinithis wrote, in Java: I did it with ints rather than floats to avoid messy rounding errors.

static class Weighting {

    int value;
    int weighting;

    public Weighting(int v, int w) {
        this.value = v;
        this.weighting = w;
    }

}

public static int weightedRandom(List<Weighting> weightingOptions) {

    //determine sum of all weightings
    int total = 0;
    for (Weighting w : weightingOptions) {
        total += w.weighting;
    }

    //select a random value between 0 and our total
    int random = new Random().nextInt(total);

    //loop thru our weightings until we arrive at the correct one
    int current = 0;
    for (Weighting w : weightingOptions) {
        current += w.weighting;
        if (random < current)
            return w.value;
    }

    //shouldn't happen.
    return -1;
}

public static void main(String[] args) {

    List<Weighting> weightings = new ArrayList<Weighting>();
    weightings.add(new Weighting(0, 8));
    weightings.add(new Weighting(1, 1));
    weightings.add(new Weighting(2, 1));

    for (int i = 0; i < 100; i++) {
        System.out.println(weightedRandom(weightings));
    }
}