选择随机选项,其中每个选项具有不同的被挑选概率

Question

假设你有三个"选项" A,B和C.

您的算法必须选择并返回一个随机的算法.为此,将它们放入数组{A,B,C}并生成随机数(0,1或2)非常简单,该数字将是要返回的数组中元素的索引.

现在,这个算法有一个变化:假设A被选中的几率为40%,B20%和C40%.如果是这种情况,您可以采用类似的方法:生成数组{A,A,B,C,C}并使用随机数(0,1,2,3,4)来选择要返回的元素.

这样可行.但是,我觉得这是非常低效的.想象一下,将此算法用于大量选项.您将创建一个有点大的数组,可能有100个元素,每个元素代表1%.现在,这仍然不是很大,但假设你的算法每秒使用很多次,这可能会很麻烦.

---

我考虑过创建一个名为class的类Slot,它有两个属性:.value和.size.为每个选项创建一个插槽,其中.value属性是选项的值,并且该插槽.size等于数组中此类选项的出现次数.然后生成一个从0到总发生次数的随机数,并检查该数字落在哪个插槽上.

我更关心算法,但这是我对此的Ruby尝试:

class Slot
  attr_accessor :value
  attr_accessor :size
  def initialize(value,size)
    @value = value
    @size  = size
  end
end

def picker(options)
  slots = []
  totalSize = 0
  options.each do |value,size|
    slots << Slot.new(value,size)
    totalSize += size
  end
  pick = rand(totalSize)
  currentStack = 0
  slots.each do |slot|
    if (pick <= currentStack + slot.size)
      return slot.value
    else
      currentStack += slot.size
    end
  end
  return nil
end

50.times do
  print picker({"A" => 40, "B" => 20, "C" => 40})
end

哪个输出:

CCCCACCCCAAACABAAACACACCCAABACABABACBAAACACCBACAAB

---

是否有更有效的方法来实现选择随机选项的算法,其中每个选项具有不同的被选择概率？

Answer 1

最简单的方法可能是写一个case语句:

def get_random()
  case rand(100) + 1
    when  1..50   then 'A'
    when 50..75   then 'B'
    when 75..100  then 'C'
  end
end

问题是您无法传递任何选项,因此如果您希望它能够选择,您可以编写这样的函数.下面的一个非常类似于你写的那个,但有点短:

def picker(options)
  current, max = 0, options.values.inject(:+)
  random_value = rand(max) + 1
  options.each do |key,val|
     current += val
     return key if random_value <= current
  end
end

# A with 25% prob, B with 75%.
50.times do
  print picker({"A" => 1, "B" => 3})
end
# => BBBBBBBBBABBABABBBBBBBBABBBBABBBBBABBBBBBABBBBBBBA

# If you add upp to 100, the number represent percentage.
50.times do
  print picker({"A" => 40, "T" => 30, "C" => 20, "G" => 10})
end
# => GAAAATATTGTACCTCAATCCAGATACCTTAAGACCATTAAATCTTTACT 

Answer 2

虽然这不是一个直接的答案,但我会向您展示一个帮助您概述这个问题的来源:http://www.av8n.com/physics/arbitrary-probability.htm.

编辑:

刚刚在红宝石中找到了一个很好的来源,拾取宝石.

require 'pickup'
headings = {
  A: 40,
  B: 20,
  C: 40,
}
pickup = Pickup.new(headings)
pickup.pick
#=> A
pickup.pick
#=> B
pickup.pick
#=> A
pickup.pick
#=> C
pickup.pick
#=> C

Answer 3

作为更有效算法的第一个近似,如果计算累积分布函数(这只是分布函数的一次传递,计算运行总和),那么您可以使用二进制搜索找到随机选择的整数的位置线性搜索.如果您有很多选项,这将有所帮助,因为它将搜索时间从O(#options)减少到O(log #options).

但是,有一个O(1)解决方案.这是基本的大纲.

假设我们有N个选项,1...N带有权重,其中所有的ω值都至少为0.为简单起见,我们缩放权重,使它们的均值为,或换句话说,它们的总和为.(我们只是将它们相乘.我们实际上不必这样做,但是如果没有MathJax,它会使下一段更容易输入.)ω1...ωN1NN/Σω

现在,创建一个N元素向量,其中每个元素都有两个选项标识符(lo和hi)和一个cutoff p.选项标识符只是整数1...N,并将p计算为(0, 1.0)包含范围内的实数.

我们继续填写矢量如下.i依次为每个元素:

• 如果有些确切,那么我们设置: 我们从权重列表中删除.ωj1.0
   loi = j
   hii = j
   pi = 1.0
ωj

• 否则,必须有一些和一些.(那是因为平均重量是1.0,并且没有一个具有平均值.其中一些必须少一些,一些更多,因为所有元素都不可能大于平均值或所有元素都少于比平均值.)现在,我们设置: 再次,我们从权重中删除.ωj < 1.0ωk > 1.0
   loi = j
   hii = k
   pi = ωj
   ωk = ωk - (1 - ωj)
ωj

请注意,在这两种情况下,我们都删除了一个权重,并且我们将权重之和减少了1.0.所以平均重量仍然是1.0.

我们以这种方式继续,直到整个向量被填满.(最后一个元素将有p = 1.0).

给定此向量,我们可以选择加权随机选项,如下所示:

• 产生一个随机整数i的范围1...N和一个随机的浮点值r的范围内(0, 1.0].如果那时我们选择选项; 否则,我们选择选项.r < piloihii

应该清楚为什么这可以从矢量的构造起作用.每个高于平均权重的选项的权重分布在各种向量元素中,而每个低于平均权重的选项被分配给具有相应选择概率的某个向量元素的一部分.

在实际实现中,我们将权重范围映射到整数值,并使总权重接近最大整数(它必须是倍数N,因此会有一些晃动.)然后我们可以选择一个槽和从单个随机整数中选择槽内的权重.实际上,我们可以修改算法以通过添加一些0加权选项来强制插槽的数量为2的幂来避免除法.因为整数运算不能很好地完成,所以需要稍微摆弄一下,但最终结果可以统计正确,模拟正在使用的PRNG的特性,并且它的执行速度几乎和简单一样快未加权的选择N选项(一个班次和一些额外的比较),代价是占用少于6N存储元件的向量(计算必须使插槽数量几乎翻倍的可能性).