Selecting biased random objects from a set

Normal random pick from set of objects will return every object equally likely.
For example, following function returns any character with equal probability from the argument string.

function randomselect(s) {
    return s[~~(Math.random() * s.length)];
}

This is usually the desired functionality, but games often require to pick one thing more likely than another. Typical use case are random drops from enemies, the common loot should drop most often and the good stuff should be much more rare.

Biased random pick is selecting object from a set randomly, so that some of them selected more often than others.

Calling randomselect("abc") will return each “a”, “b” and “c” with 33% probability.
Selection can be biased by just adding more of characters in the string. Calling randomselect("aaabbc") will return “a” with 50%,”b” with 33% and “c” with 16% propability.

Just adding entries in a list is bit clumsy, and more generic method is to use integral of probability density.

// define elements and probability for each
var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
]

// Biased random entry selection
function select(elems) {
    var r = Math.random();
    var ref = 0;

    for(var i=0; i < elems.length; i++) {
        var elem= elems[i];
        ref += elem[1];
        if (r < ref) return elem[0];
    }
    // This happens only if probabilities do not add up to 1
    return null;
}

Calling select(elems) returns a with 50%, b with 33.3% and c with 16.6% probability.
If defined probabilities do not sum to 1 you can get null, i.e not selection. In this case 0.5 + 0.333 + 0.166 is 0.999 so there is 0.1% probability (one out 1000) to get nothing.

For example to pick 100 times randomly from the set.

var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
];

var s = '';
for(var i=0; i < 100; i++) {
	s += select(elems);
}
console.log(s);

Run this with node to get string of randomly picked characters. Here you can see that selection bias works, half of the letters are ‘a’, one third ‘b’ and rest ‘c’.

$ node biased.js
babbaaaabaabbaabaccbaacabbbabbacbaabacabccacacacbacaaaaacbcaaaababaccbcbbbcaabcaabaccabbbcbcbacaabaa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: