Biased Random

What we call random numbers generated by computers are more correctly called pseudo random as they are not actually completely random. For the purposes of this article however we are going to ignore any bias in these random numbers and assume that they are completely unbiased. They are at least as unbiased as the authors of the random functions can make them.

What we are going to discuss here is when we want to deliberately introduce a bias to the random numbers we are generating. Now why might we want to do that? Well what we are looking at here is probability. If the random numbers don't have a bias then each will be equally likely to occur but that isn't the situation we usually have in the real world.

A simple example would be to roll two dice. The result will be a number between 2 and 12 but each number is not equally likely to occur. The likelihood of a 7 is six times more likely to occur than either a 2 or a 12. If we want a random number representing the result of rolling two dice (or anything else where all the possible results don't have equal probability then we need to introduce an appropriate bias into the random numbers we get returned to take into account the probability of the different results.

With rolling two dice the solution is straightforward. Simply generate two random integers between 1 and 6 and add them together.

var rand = function(min,max) {
return Math.floor(Math.random() * (max-min+1)) + min;
}
 
console.log(rand(1,6)+rand(1,6));

This resolves creating this particular bias but it doesn't help toward solving any other probability bias that we may want to use. Let's generate a more useful function that will solve not only this specific random bias but which can be used to resolve any random bias problem.

var biasRand = function(l, w) {
var r, i=0;
if (l.length !== w.length) throw new RangeError('Array length mismatch');
r = Math.random() * w.reduce(function(p,c){return p+c;});
while(true) {if (r <= w[i]) return l[i]; r-= w[i++];}
};
 
console.log(biasRand([2,3,4,5,6,7,8,9,10,11,12],[1,2,3,4,5,6,5,4,3,2,1]));

With this function we pass in two arrays. The first array is the set of the possible values we want the function to return and the second array is the relative weights that we want to apply to each of those values in order to apply the appropriate bias. We need these two arrays to be the same length in order for the biased random result to be able to be returned so let's throw an error if they are not. We'll also use the rand function from our earlier code but modified so that it will return any number greater than or equal to min and less than max instead of just integers. We then take a copy of the weight array and modify the values so that instead of representing the relative weights of the individual values they represent the probability of the value being less than or equal to the current one. We can then generate a random number greater than or equal to zero and less than the last value in this new array and then find the first entry in this array that this random value is not greater than. The value from our list array in this position is then returned.

Both of these pieces of code so far return the same biased set of results representing the probabilities of getting the different results when two dice are thrown. If that were all we were trying to do then the first code would be the solution to use as it is much simpler and more obvious. Where this second version comes in is that it is not limited to solving just that one problem. Let's say that instead of simply throwing two dice to get one of eleven possible values that we instead want to obtain a number between -5 and 5 where the probability of a given number occurring varies with the square of the number. We now have a different set of eleven numbers with completely different probabilities. We can however use our second function to produce random numbers with this different bias simply by substituting the arrays whereas the first function is no help at all with this new problem.

console.log(biasRand([-5,-4,-3,-2,-1,0,1,2,3,4,5],[25,16,9,4,1,0,1,4,9,16,25]));

We can of course substitute any code that returns an array for either or both of the arrays we need to pass to the function. In each of our two examples so far we have a range of consecutive numbers as the first array. If we have a function that will generate this array for us then we can substitute the function for the first array. Note that the array of possible results need not be a series of consecutive integers in which case you'd need a function that generates whatever list of values you want the biasedRand function to return.

Array.prototype.range = function(a,b) {
var x = Math.min(a,b), y = Math.max(a,b);
return Array.apply(null, Array(y-x+1)).map(function (z,i) {return x+i});
}
 
console.log(biasRand([].range(2,12),[1,2,3,4,5,6,5,4,3,2,1]));
console.log(biasRand([].range(-5,5),[25,16,9,4,1,0,1,4,9,16,25]));

The last two lines of that code use a range method added to the Array object to generate the required list array for each of our two previous problems.

We can also use a function to create the values for the weight array where we know a formula for generating the values. With the second of our two problems the weights are simply the squares of the values in the list array and so we can resolve this second problem using:

var lst = [].range(-5,5);
console.log(biasRand(lst,lst.map(function(x){return x*x;})));

The ability to substitute a function for each of these arrays makes our function extremely flexible. Being able to substitute for the second array means that we can enter a formula for the weights instead of needing to calculate out each value separately. Being able to substitute a function for the first array makes changing the range of possible results much easier. Simply substitute [].range(-10,10) and now we have extended the range of our possible results and we have applied the corresponding weights via the second function.

Simply by selecting the appropriate range of values for the list array and giving them appropriate weights will allow our biasRand function to return any selected range of values where the appropriate bias toward specific values has been applied.

 

This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow
Donate