Generate random integers with probabilities

Question

I'm a bit confused about how to generate integer values with probabilities.

As an example, I have four integers with their probability values: 1|0.4, 2|0.3, 3|0.2, 4|0.1

How can I generate these four numbers taking into account their probabilities?

Vaughnvaught

If you want to know lots of technical details about how to do this quickly, this is a great resource. For making a weighted choice among 4 choices, it's totally unneeded though. keithschwarz.com/darts-dice-coins – Joellenjoelly

See also stackoverflow.com/questions/3094873 – Screwworm

Answer 1

Here's a useful trick :-)

function randomWithProbability() {
  var notRandomNumbers = [1, 1, 1, 1, 2, 2, 2, 3, 3, 4];
  var idx = Math.floor(Math.random() * notRandomNumbers.length);
  return notRandomNumbers[idx];
}

Lucubrate

Correct direction, just create notRandomNumbers dynamically (given the numbers and their weight/probability) and it's ideal solution in my opinion. – Martine

Nice! Thanks. this looks just what I need. – Vaughnvaught

@ShadowWizard: yes, I made it simple for clarity :-) – Lucubrate

of course, I was just waiting for some more solutions to choose the best one ;) – Vaughnvaught

Nope, I didn't change anything. I only now accepted your answer for it's more elegant solution than the other one. – Vaughnvaught

Ah, I thought you accepted that one previously. Never mind. Yeah, my solution is more elegant :-) – Lucubrate

I don't think this is an efficient way to do so. Let's assume we have probabilities such as: [0.000000000001, 0.299999999999, 0.7], so what will be the notRandomNumbers table in this case? Quiz: How much memory it will use? I would rather say that it is THE WORST possible solution to this problem. – Barite

@nosbor: yeah, the answer from bhups would perform better. – Lucubrate

Answer 2

A simple naive approach can be:

function getRandom(){
  var num=Math.random();
  if(num < 0.3) return 1;  //probability 0.3
  else if(num < 0.6) return 2; // probability 0.3
  else if(num < 0.9) return 3; //probability 0.3
  else return 4;  //probability 0.1
}

Sihonn

What if two numbers have the same probability? :-) – Lucubrate

Sergio Tulentsev -> easy use the same differences between next steps – Kentiga

Answer 3

More flexible solution based on @bhups answer. This uses the array of probability values (weights). The sum of 'weights' elements should equal 1.

var weights = [0.3, 0.3, 0.3, 0.1]; // probabilities
var results = [1, 2, 3, 4]; // values to return

function getRandom () {
    var num = Math.random(),
        s = 0,
        lastIndex = weights.length - 1;

    for (var i = 0; i < lastIndex; ++i) {
        s += weights[i];
        if (num < s) {
            return results[i];
        }
    }

    return results[lastIndex];
};

Dronski

Answer 4

I suggest to use a continuous check of the probability and the rest of the random number.

This function sets first the return value to the last possible index and iterates until the rest of the random value is smaller than the actual probability.

The probabilities have to sum to one.

function getRandomIndexByProbability(probabilities) {
    var r = Math.random(),
        index = probabilities.length - 1;

    probabilities.some(function (probability, i) {
        if (r < probability) {
            index = i;
            return true;
        }
        r -= probability;
    });
    return index;
}

var i,
    probabilities = [0.4, 0.3, 0.2, 0.09, 0.01 ],
    count = {},
    index;

probabilities.forEach(function (a) { count[a] = 0; });

for (i = 0; i < 1e6; i++) {
    index = getRandomIndexByProbability(probabilities);
    count[probabilities[index]]++
}

console.log(count);

Idonna

Answer 5

This is the solution i find the most flexible, for picking within any set of object with probabilities:

// set of object with probabilities:
const set = {1:0.4,2:0.3,3:0.2,4:0.1};

// get probabilities sum:
var sum = 0;
for(let j in set){
    sum += set[j];
}

// choose random integers:
console.log(pick_random());

function pick_random(){
    var pick = Math.random()*sum;
    for(let j in set){
        pick -= set[j];
        if(pick <= 0){
            return j;
        }
    }
}

Alexaalexander

Answer 6

let cases = {
  10 : 60,// 0-10 : 60  => 10%
  90 : 10,// 10-90 : 10  => 80%
  100 : 70,// 90-100 : 70 => 10%
};
function randomInt(){
  let random = Math.floor(Math.random() * 100);
  for(let prob in cases){
    if(prob>=random){
      return cases[prob];
    }
  }
}
console.log(randomInt())

Hampstead

Answer 7

Some variation on Rom098 answer to make it a bit more flexible. Added weights as array of unit instead.

function randomWithProbability(outcomes, weights){
    if(!weights){
        weights=Array(outcomes.length).fill(1);
    }
    let totalWeight=weights.reduce((prev, curr)=>prev+=curr);
    const num=Math.random();
    let sum=0, lastIndex=weights.length-1;
    for(let i=0; i<=lastIndex; i++){
        sum+=weights[i]/totalWeight;
        if(num<sum) return outcomes[i];
    }
    return outcomes[lastIndex];
}

for(let i=0; i<20; i++){
  console.log(randomWithProbability([true, false], [10,1]));
}

Euglena