Scala:我如何根据预期的分布生成数字？

Question

有时,当想要生成较小范围的随机数或者您已经知道某些数字已经附加了相关概率时,Scala的随机性无效.显然,scala.util.Random.nextInt不会完成整个工作.

如何根据重量选择数字？

Answer 1

这是一个简单的解释.想象一下,您对值A,B,C有多项式,它们具有以下概率:

• A = 0.5
• B = 0.3
• C = 0.2

如果你想根据它的概率对一个值进行采样,那么这意味着大约50%的时间你想得到A,30%的时间是B,20%是时间C.

想象一下你的发行是一根破碎的棍子:

       A         B      C
      0.5       0.3    0.2
|------------|-------|-----|
0           0.5     0.8   1.0

从多项式采样的过程从p在0和1之间均匀采样的随机值开始.然后检查棒的哪个部分p落入,并返回相应的值.

那么如果p = 0.7,那么:

       A         B      C
      0.5       0.3    0.2
|------------|-------|-----|
0           0.5     0.8   1.0
                  ^
                 p=0.7

你会回来B.

代码方面,然后看起来像:

final def sample[A](dist: Map[A, Double]): A = {
  val p = scala.util.Random.nextDouble
  val it = dist.iterator
  var accum = 0.0
  while (it.hasNext) {
    val (item, itemProb) = it.next
    accum += itemProb
    if (accum >= p)
      return item  // return so that we don't have to search through the whole distribution
  }
  sys.error(f"this should never happen")  // needed so it will compile
}

你可以像这样检查:

val dist = Map('A -> 0.5, 'B -> 0.3, 'C -> 0.2)
sample(dist)  // 'A

Vector.fill(1000)(sample(dist)).groupBy(identity).mapValues(_.size) // Map('A -> 510, 'B -> 300, 'C -> 190)

其他事情:

• 如果dist不是概率分布(即,权重不总和为1),那么您只需使用p = nextDouble * dist.values.sum.因此,如果dist总和为0.5,则p在0.0和0.5之间均匀; 如果总和为20,则p在0.0和20.0之间均匀.

您可以执行其他优化,例如首先对具有最大概率的条目进行排序,以便在累积p概率质量之前最小化您必须查看的条目数,但这应该可以帮助您了解基本概念.