javascript - 生成加权随机数

Question

我正在尝试设计一种(好的)方法从一系列可能的数字中选择一个随机数，其中该范围内的每个数字都被赋予一个权重。简单来说:给定数字范围 (0,1,2)，选择一个数字，其中 0 有 80% 的概率被选中，1 有 10% 的概率，2 有 10% 的概率。

自从我上大学统计课以来已经过去了大约 8 年，所以你可以想象我现在忘记了正确的公式。

这是我想出的“廉价而肮脏”的方法。该解决方案使用 ColdFusion。您可以使用您想要的任何语言。我是一名程序员，我想我可以处理移植它。最终我的解决方案需要在 Groovy 中 - 我在 ColdFusion 中编写了这个解决方案，因为在 CF 中快速编写/测试很容易。

public function weightedRandom( Struct options ) {

    var tempArr = [];

    for( var o in arguments.options )
    {
        var weight = arguments.options[ o ] * 10;
        for ( var i = 1; i<= weight; i++ )
        {
            arrayAppend( tempArr, o );
        }
    }
    return tempArr[ randRange( 1, arrayLen( tempArr ) ) ];
}

// test it
opts = { 0=.8, 1=.1, 2=.1  };

for( x = 1; x<=10; x++ )
{
    writeDump( weightedRandom( opts ) );    
}

我正在寻找更好的解决方案，请提出改进​​或替代方案。

Answer 1

Rejection sampling (例如在您的解决方案中)是首先想到的，您可以构建一个查找表，其中的元素按其权重分布填充，然后在表中选择一个随机位置并将其返回。作为一种实现选择，我将创建一个高阶函数，它接受一个规范并返回一个函数，该函数根据规范中的分布返回值，这样您就不必为每个调用构建表。缺点是构建表的算法性能与项目数量成线性关系，并且大规范(或具有非常小或精确权重的成员的规范，例如 {0:0.99999, 1 :0.00001})。优点是选择值的时间恒定，如果性能至关重要，这可能是可取的。在 JavaScript 中:

function weightedRand(spec) {
  var i, j, table=[];
  for (i in spec) {
    // The constant 10 below should be computed based on the
    // weights in the spec for a correct and optimal table size.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
    for (j=0; j<spec[i]*10; j++) {
      table.push(i);
    }
  }
  return function() {
    return table[Math.floor(Math.random() * table.length)];
  }
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...

另一种策略是在[0,1)中选择一个随机数，并迭代权重规范，对权重求和，如果随机数小于总和，则返回关联值。当然，这是假设权重之和为一。该解决方案没有前期成本，但平均算法性能与规范中的条目数量成线性关系。例如，在 JavaScript 中:

function weightedRand2(spec) {
  var i, sum=0, r=Math.random();
  for (i in spec) {
    sum += spec[i];
    if (r <= sum) return i;
  }
}
weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution...