Javascript函数生成具有非均匀概率的随机整数
在javascript（或jquery）中有一个简单的函数，它有四个整数及其概率值：1 | 0.41,2 | 0.29,3 | 0.25,4 | 0.05
如何在考虑其概率的情况下生成这四个数字？
这个问题与这里发布的问题非常类似： 生成具有概率的随机整数
然而，解决方案发布在那里：
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]; } 注释中的状态“动态创建notRandomNumbers（给定数字及其权重/概率）”
这不足以满足我的需求。 当概率为10％，20％，60％，10％时，这很有效。
在这种情况下，使用所需的分布构造notRandomNumbers很容易，并且数组大小很小。 但是在概率可能是20.354％，30.254％等的一般情况下，数组大小对于正确建模情况来说是巨大的。
这个更普遍的问题是否有一个干净的解决方案？
编辑：谢谢格奥尔格，解决方案接受，这是我的最终版本 ，这可能对其他人有用。 我已将累积计算拆分为单独的函数，以避免在每次调用时额外添加以获取新的随机数。
function getRandomBinFromCumulative(cumulative) { var r = Math.random(); for (var i = 0; i < cumulative.length; i++) { if (r <= cumulative[i]) return i; } } function getCummulativeDistribution(probs) { var cumulative = []; var sum = probs[0]; probs.forEach(function (p) { cumulative.push(sum); sum += p; }); // the next 2 lines are optional cumulative[cumulative.length - 1] = 1; //force to 1 (if input total was 1) cumulative.shift(); //remove the first 0 return cumulative; } function testRand() { var probs = [0.1, 0.3, 0.3, 0.3]; var c = getCummulativeDistribution(probs); console.log(c); for (var i = 0; i < 100; i++) { console.log(getRandomBinFromCumulative(c)); } }
只需累加概率并返回current_sum >= random_number ：
probs = [0.41, 0.29, 0.25, 0.05]; function item() { var r = Math.random(), s = 0; for(var i = 0; i < probs.length; i++) { s += probs[i]; if(r <= s) return i; } } // generate 100000 randoms a = []; c = 0; while(c++ < 100000) { a.push(item()); } // test actual distibution c = {} a.forEach(function(x) { c[x] = (c[x] || 0) + 1; }); probs.forEach(function(_, x) { document.write(x + "=" + c[x] / a.length + "
") });
创建具有相应权重的第二个并行数组，并使用“wheel”算法来获取索引。
function randomWithProbability() { var notRandomNumbers = [1,2,3,4]; var w = [0.41, 0.29, 0.25, 0.05]; var placehldr = 0; var maxProb = 0.41; var index = Math.floor(Math.random() * w.length); var i = 0; placehldr = Math.random() * (maxProb * 2); while(placehldr > index ) { placehldr -= w[index]; index = (index + 1) % w.length } return (notRandomNumbers[index]); }
该video对其工作原理有很好的解释，通过视觉表示更容易理解。 https://www.youtube.com/watch?v=wNQVo6uOgYA
由于AJ Walker（Electronics Letters 10,8（1974），127-128; ACM Trans.Math Software 3（1977），253-256），并且在Knuth，TAOCP Vol。中描述了优雅的解决方案，仅需要单次比较。 2,120-121。 您还可以在此处找到描述， 生成具有不同概率的范围内的随机数 。