a better way to do random sampling with a probability distribution?

Question

I want to choose random items from an array but with certain probability distributions. currently I do: myarray =[5,5,5,95] which gets me a 75% chance of getting a 5 and 25% chance of getting a 95.

I have a lot more numbers though and it takes too much time to write out all those numbers, is there a faster/better way to do this?

Answer 1

You can have an array with objects that contain any value, and a weight property that's a number.

// data
const samples = [
  { value: 5, weight: 75 },
  { value: 95, weight: 25 }
];

// requested method
function randomSample (samples) {
  // [0..1) * sum of weight
  let sample =
    Math.random() *
    samples.reduce((sum, { weight }) => sum + weight, 0);

  // first sample n where sum of weight for [0..n] > sample
  const { value } = samples.find(
    ({ weight }) => (sample -= weight) < 0
  );

  return value;
}

// demo
const counts = { 5: 0, 95: 0 };

Array
  // take a million random samples
  .from({ length: 1000000 }, () => randomSample(samples))
  // count each sample
  .forEach(value => { counts[value]++; });

console.log(counts);

The data does not have to be in any particular order, nor do the weights need to add up to any particular sum.

Answer 2

function weightedChoice(array, weights) {
  let s = weights.reduce((a, e) => a + e);
  let r = Math.random() * s;
  return array.find((e, i) => (r -= weights[i]) < 0);
}

let randomArray =
    Array.apply(null, Array(32)).
    map(() => weightedChoice([5, 95], [75, 25]));
console.log(JSON.stringify(randomArray));

EDIT: Patrick was a bit faster than me, so I'll endorse his answer, and I'll just add that you don't absolutely need the sum to be 1, you can normalise the weight by finding out the sum by yourself.

EDIT EDIT: If you are really worried about performance in the case of needing many random values with the same weights, this would do better (by precalculating as much as possible):

class WeightedSampler {
  constructor(elements, weights) {
    this.total = 0;
    this.elements = Array.from(elements);
    this.cweights = weights.map(weight => this.total += weight);
  }
  get() {
    let random = Math.random() * this.total;
    return this.elements.find((element, index) => random < this.cweights[index]);
  }
}

const sampler = new WeightedSampler(["M", "I", " "], [3, 9, 1]);
let randomArray = Array.apply(null, Array(32)).map(() => sampler.get());
console.log(randomArray.join(""));