固定比例选择

Question

我有一组元素,我需要从中选择任何一个元素.每个元素都与百分比机会相关联.百分比增加到100.

我需要从这些元素中选择一个,以便选择元素的机会等于百分比值.因此,如果一个元素有25%的几率,它应该有25%的机会被选中.换句话说,如果我们选择1 mil的元素,那么该元素应该选择接近250k次.

Answer 1

你描述的是一个多项过程.

http://en.wikipedia.org/wiki/Multinomial_distribution#Sampling_from_a_multinomial_distribution

他们生成这样的随机过程的方式是这样的:(我将使用伪代码,但它应该很容易进入实际代码.)

1. 按照概率的相反顺序对"框"进行排序:( 不需要.它只是一个优化), 所以你有例如值= [0.45,0.3,0.15,0.1]

2. 然后创建'累积'分布,它是索引<= i的所有元素的总和.伪代码:

   cumulant=[0,0,0,0]    // initiate it
   s=0
   for j=0 to size()-1 {
      s=s+values[i] ; 
      cumulant[i]=s
   }
   

   在我们的案例累积量= [0.45,0.70,0.85,1]

3. 在0和1之间制作一个统一的随机数x.对于php:http://php.net/manual/en/function.rand.php

4. 得到的随机盒索引i是

   累积量[i] <x的最高i

伪代码:

for j=0 to size()-1 {
  if !(cumulant[i]<){
     print "your index is ",i
     break;
  }

这就对了.通过回到第3点获得另一个随机索引.

如果您按照上面的建议排序,这意味着最终搜索会更快.例如,如果你有这个概率向量:0.001 0.001 0.001 0.001 0.996那么,当你对它进行排序时,你几乎总是只需要看索引i = 0,因为随机数x几乎总是低于0.996 .如果排序得到回报,取决于你是否反复使用相同的"盒子".所以,是的250k尝试它会有很大帮助.请记住,我得到的框索引是针对排序的向量.