Weighted Random Number

April 26th, 2010 by Mike Wilcox

If you are new to JavaScript, the method to get a random number may be difficult to grasp. The built-in function Math.random() does not accept any arguments, and it returns a decimal between 0 (inclusive) and 1 (exclusive). Most often, we want a whole number, maybe to be used for accessing a random element in an array. Consequently, random generators usually have to be custom coded. But what if we want to get a more weighted distribution of random numbers? Say of a random number between 1-5 we want 1 to show more often than 5? Even if you are not new to JavaScript, determining the math to add a weight to a random result can be quite tricky.

Random Whole Number

Generating a random whole number is not hard, but if you are unfamiliar with the technique it admittedly can take a bit of thought. Create a function named “randomNumber”, and allow one argument to be passed. The return will be between zero and that number. Multiply Math.random() times the argument, and then apply Math.floor to that.


var randomNumber = function(num){
    return Math.floor(Math.random() * num);
};

The function above returns you a value of between 0 and num-1. So, if you are looking for a value of between 0 and 9, you would need to pass 10 as an argument. If you were looking for 1 to 10, you could simply add 1 to the previous result. Further, you could have the function add 1 to the value before its return. Now of course it won’t work as well with arrays. Using a one-based or zero-based randomizer depends on your specific needs.

Unit Test


var myArray = [0,0,0,0,0];
for(var i=0;i<1000;i++){
    myArray[randomNumber(myArray.length)]++;
}
console.log(myArray);
// possible output:
[199, 214, 199, 203, 185]

To run this code, open Firebug. On the bottom right there is a small gray button with an up-arrow icon in it. Click this button to open the command line in multi-line mode. You can now paste in the above code. To execute, either click the Run button, or use the control + ENTER keys.

What the 1000 loop unit test does is create an array with 5 elements and set them all to zero. It then loops 1000 times, and accesses a random myArray element, determined by calling randomNumber and passing in the length of myArray which in this case is 5. So in effect, we called randomNumber(5); a thousand times, and used the return value of 0-4 to access that element of the array and increment it by one ( hence the ++). The output was successful. It generated no errors (like maybe an out-of-range error trying to increment element 6), all 5 elements were incremented which means all of our numbers were called, the numbers add up to 1000 meaning no unexpected numbers were called (like 5 which we shall get to in a moment), and the results were evenly distributed meaning we had a satisfactory random result which averaged out over time.

Simple Weighting

In our unit test loop, we had our random numbers evenly distributed. Let’s add a weight option to it so that our return is always skewed one way or another. We operate on the randomly generated number from Math.random, so start by adding a simple weight function and changing randomNumber to look like the following:


var weight = function(num){
    return num * num;
}

var randomNumber = function(num){
    return Math.floor( weight(Math.random()) * num );
};

Simply multiplying the random return by itself already gives us a weighted result. Doing the 1000 loops on myArray shows: [470, 181, 131, 115, 103], which skews quite a bit toward the beginning, just as we had hoped. Remember, Math.random generates a float between 0 and 1, so most times this number is a fraction and multiplying it by itself makes it smaller, which is why the lower elements in the array increments more often:


.1 * .1 == .01
.2 * .2 == .04
.9 * .9 == .81

Variable Weighting

Realizing that a multiple is what gives us our weight, and seeing that num * num can be rewritten as Math.pow(num, 2), we can now change the code and accept a second argument as an exponent, and increase the variance of our weight. Then we’ll edit the 1000 loop test to pass an exponent of 5.


var weight = function(num, exp){
    return Math.pow(num, exp);
};

var randomNumber = function(num, exp){
    return Math.floor( weight(Math.random(), exp) * num );
};

var myArray = [0,0,0,0,0];
for(var i=0;i>1000;i++){
    myArray[randomNumber(myArray.length, 5 )]++;
}
console.log(myArray);
// possible output:
[715, 114, 69, 63, 39]

Our exponent of 5 shows it is weighted more heavily than our original multiple of 2.

Our variable weight is so far a success, but there are problems with the current code. Using an exponent of 1 works, as that is the same as no weight. But 0 doesn’t doesn’t randomize at all, since any number to the power of zero is one. Negative numbers go off the charts, because a negative exponent is reversed, multiplying whole numbers and not fractions, outputting ten numbers might look like: [11672, 14, 1189, 21, 6, 347, 200286, 5, 180, 27321]. Finally, while an exponent of 1.5 returns a satisfactory result, 0.5 reverses the weight, but at a different slope than the whole numbers: [35, 135, 163, 292, 375].

There are different ways to handle these problems. We’ll approach them by looking at how we want the usability of the function to work. Ideally, 1, 2, and 3 would give us a weight toward the “beginning” (of resulting array from the 1000 loop unit test), while negative numbers should weight toward the “end”. And it stands to reason that zero therefore should have no effect. We also need to sneak in the handling of undefined, because we would like to not have to pass an argument to get an unweighted random number. So here’s what we’ll do:

  1. Check if the number is negative
  2. If the number is undefined, make it zero (which will then be one)
  3. Use the absolute value of the number, so that we never use a negative exponent
  4. Add one, so the number is never between 0 and 1
  5. Apply the exponent
  6. If the number was negative, flip our result by subtracting it from one

var weight = function(num, exp){
    var rev = exp < 0;
    exp = exp===undefined ? 1 : Math.abs(exp)+1;
    var res = Math.pow(num, exp);
    return rev ? 1 - res : res;
}

So to check our work, let's create a loop that runs through some relevant weights (exponents) and log the results:


var weight = function(num, exp){
    var rev = exp < 0;
    exp = exp===undefined ? 1 : Math.abs(exp)+1;
    var res = Math.pow(num, exp);
    return rev ? 1 - res : res;
}

var randomNumber = function(num, exp){
    return Math.floor( weight(Math.random(), exp) * num );
};

var exps = [-2, -1.5, -1, -.5, 0, .5, 1, 1.5, 2];
for(var x=0; x < exps.length; x++){
    var myArray = [0,0,0,0,0];
    for(var i=0;i<1000;i++){
        myArray[randomNumber(myArray.length, exps[x])]++;
    }
    console.log(exps[x], myArray);
}
// output:
-2   [63, 74, 113, 141, 609]
-1.5 [77, 92, 138, 149, 544]
-1   [100, 100, 150, 182, 468]
-0.5 [137, 148, 195, 196, 324]
0    [210, 184, 196, 207, 203]
0.5  [335, 171, 182, 163, 149]
1    [445, 171, 151, 126, 107]
1.5  [559, 150, 115, 91, 85]
2    [598, 153, 100, 79, 70]

The output looks good. The -2 weight is strong on the end, and 2 is strong at the beginning. Zero or undefined has no weight and returns a consistent random number.

Conclusion

We made random numbers easy with our simple helper function, and then we made them versatile with our weight function. It may be tempting to combine these into one function, but it's really better to leave the functionality separate. Even if there is no other code that could utilize weight by itself, it's nice to be able to write a test against it.

Feel free to copy or modify this code, but it shouldn't be considered the only way to weight a random number. As you can see by the output above, the curve is rather severe. For an exponent of 2, the first number gets called 400% more than the second, and the second called only 50% more than the third. A different method may be to use only a fractional number between 1 and 2 (and negative), or using different math, such as sine or cosine. The curve could even be in the middle or on the ends.

Random results are helpful but the data has to be close to our expectations for it to be useful. Weighting is the key to creating relevance in your randomization.

Tags: , , , , ,

5 Responses to “Weighted Random Number”

  1. [...] Adres URL: Weighted Random Number « Club AJAX – Dallas Ft. Worth Area AJAX … [...]

  2. [...] See the article here: Weighted Random Number « Club AJAX – Dallas Ft. Worth Area AJAX … [...]

  3. Very informative! I haven’t yet had a need for something like this, but I have definitely learned a lot and know which bookmark to come back to when I do.

  4. [...] weighting used in Randomizer is the same as described in the previous post, Weighted Random Number. That random function is the key method driving most of the functionality, which can be accessed [...]