生成加权随机数

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

拒绝抽样(例如在您的解决方案中)首先想到的是,您可以使用其权重分布构建一个包含元素的查找表,然后在表中选择一个随机位置并将其返回.作为一个实现选择,我会创建一个更高阶的函数,它接受一个规范并返回一个函数,该函数根据规范中的分布返回值,这样就可以避免为每个调用构建表.缺点是构建表的算法性能与项目数量呈线性关系,并且对于大规格(或具有非常小或精确权重的成员的那些,可能存在大量内存使用,例如{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)并迭代权重规范,对权重求和,如果随机数小于总和则返回相关值.当然,这假设权重总和为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...

Answer 2

生成0到1之间的随机数R.

如果R在[0,0.1) - > 1

如果R在[0.1,0.2) - > 2

如果R在[0.2,1] - > 3中

如果无法直接获得0到1之间的数字,请生成一个范围内的数字,该范围将产生您想要的精度.例如,如果你有权重

(1,83.7%)和(2,16.3%),从1到1000滚动一个数字.1-837是1. 838-1000是2.

Answer 3

这或多或少是@trinithis用Java编写的通用版本:我使用int而不是浮点数来避免混乱的舍入错误.

static class Weighting {

    int value;
    int weighting;

    public Weighting(int v, int w) {
        this.value = v;
        this.weighting = w;
    }

}

public static int weightedRandom(List<Weighting> weightingOptions) {

    //determine sum of all weightings
    int total = 0;
    for (Weighting w : weightingOptions) {
        total += w.weighting;
    }

    //select a random value between 0 and our total
    int random = new Random().nextInt(total);

    //loop thru our weightings until we arrive at the correct one
    int current = 0;
    for (Weighting w : weightingOptions) {
        current += w.weighting;
        if (random < current)
            return w.value;
    }

    //shouldn't happen.
    return -1;
}

public static void main(String[] args) {

    List<Weighting> weightings = new ArrayList<Weighting>();
    weightings.add(new Weighting(0, 8));
    weightings.add(new Weighting(1, 1));
    weightings.add(new Weighting(2, 1));

    for (int i = 0; i < 100; i++) {
        System.out.println(weightedRandom(weightings));
    }
}

Answer 4

以下是javascript中的3个解决方案,因为我不确定您希望使用哪种语言.根据您的需要,前两个中的一个可能有效,但第三个可能是最容易实现的大型数字.

function randomSimple(){
  return [0,0,0,0,0,0,0,0,1,2][Math.floor(Math.random()*10)];
}

function randomCase(){
  var n=Math.floor(Math.random()*100)
  switch(n){
    case n<80:
      return 0;
    case n<90:
      return 1;
    case n<100:
      return 2;
  }
}

function randomLoop(weight,num){
  var n=Math.floor(Math.random()*100),amt=0;
  for(var i=0;i<weight.length;i++){
    //amt+=weight[i]; *alternative method
    //if(n<amt){
    if(n<weight[i]){
      return num[i];
    }
  }
}

weight=[80,90,100];
//weight=[80,10,10]; *alternative method
num=[0,1,2]

Answer 5

怎么样

int [] numbers = {0,0,0,0,0,0,0,0,2};

然后你可以从数字中随机选择,0将有80%的几率,1 10%和2 10%

Answer 6

我使用以下内容

function weightedRandom(min, max) {
  return Math.round(max / (Math.random() * max + min));
}

这是我的"加权"随机,其中我使用"x"的反函数(其中x是最小值和最大值之间的随机值)来生成加权结果,其中最小值是最重要的元素,最大值最轻的(获得结果的机会最少)

所以基本上,使用weightedRandom(1, 5)意味着得到1的机会高于高于3的2,高于4,高于5.

可能对您的用例没有用,但可能对搜索同一问题的人有用.

经过100次迭代试试,它给了我:

==================
| Result | Times |
==================
|      1 |    55 |
|      2 |    28 |
|      3 |     8 |
|      4 |     7 |
|      5 |     2 |
==================

Answer 7

晚了 8 年，但这是我的 4 行解决方案。

1. 准备一个概率质量函数数组，使得

pmf[array_index] = P(X=array_index):

var pmf = [0.8, 0.1, 0.1]

2. 为相应的累积分布函数准备一个数组，使得

cdf[array_index] = F(X=array_index):

var cdf = pmf.map((sum => value => sum += value)(0))
// [0.8, 0.9, 1]

3a) 生成一个随机数。

3b) 获取大于或等于该数字的元素数组。

3c) 返回其长度。

var r = Math.random()
cdf.filter(el => r >= el).length