java - Java 中的离散概率分布

Question

我有一组整数，每个整数都有一个分配的概率，从早期的实验中得出，例如:

0 = 0.5
1 = 0.2
2 = 0.3

根据概率分布的规范，这些权重总和为 1.0。我现在正在寻找一种有效的方法来对其中一个值进行采样，同时考虑给定的概率，例如(伪代码):

Distribution distribution = new DiscreteDistribution(new double[]{0.5, 0.3, 0.2});
distribution.sample();

根据给定的数字，这应该导致一半时间为 0。但是，不要假设其中有任何模式或规律。

我一直在使用 Apache Commons Math对于我以前的实验，但它似乎没有为这种情况提供解决方案，Colt 也没有。 .

我想知道这是否是因为我错过了一个简单的解决方案。天真的实现看起来或多或少是直截了当的，但要有效地做到这一点却相当复杂。这就是我寻找既定实现的原因。

Answer 1

考虑到 quantile 函数的简单性和手动实现的琐碎性，我认为将其明确写出来没有任何害处。

在 [0, 1] 中抽取随机数 r 后，使用

if (r <= 0.5/*micro-optimisation: most likely case first*/){
    return 0;
} else if (r <= 0.8/*then the next most likely case*/){
    return 2;
} else {
    return 1;
}

对于超过 3 个数字，事情可能会变得更有趣，考虑在这种情况下构建一个表来表示分位数函数，但代价是性能有所下降。

(就速度而言很难打败我的解决方案，在最坏的情况下，您有几个分支 - 而您正在以尽可能最好的方式帮助分支预测器 ，而随机数的抽取将是性能瓶颈所在)。