Java中的离散概率分布

Question

我有一组整数,每个整数都有一个概率,来自早期的实验,例如:

0 = 0.5
1 = 0.2
2 = 0.3

符合概率分布的规范,这些权重总和为1.0.我现在正在寻找一种有效的方法来考虑其中一个值,同时考虑给定的概率,例如(pseude-code):

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

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

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

我想知道这是否是因为我错过了一个简单的解决方案.一个天真的实施似乎或多或少是直截了当的,但有效地做这件事是相当复杂的.这就是我正在寻找既定实施的原因.

Answer 1

鉴于分位数函数的简单性和手动实现的琐碎性，我认为明确地写出它没有任何危害。

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

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 个数字，事情会变得更花哨，请考虑在这种情况下构建一个表来表示分位数函数，但代价是性能有所下降。

（在速度方面很难击败我的解决方案，在最坏的情况下你有几个分支 - 你正在以最好的方式帮助分支预测器，随机数绘制将是性能瓶颈是）。

Answer 2

一个非常简单的通用解决方案是：

class Distribution<T>{
    List<Double> probs = new ArrayList<>();
    List<T> events = new ArrayList<>();
    double sumProb;
    Random rand = new Random();

    Distribution(Map<T,Double> probs){
        for(T event : probs.keySet()){
            sumProb += probs.get(event);
            events.add(event);
            this.probs.add(probs.get(event));
        }
    }

    public T sample(){
        T value;
        double prob = rand.nextDouble()*sumProb;
        int i;
        for(i=0; prob>0; i++){
            prob-= probs.get(i);
        }
        return events.get(i-1);
    }
}

您可以根据需要随意更改它，例如添加其他构造函数。当然，这里有很多东西需要改进，首先是效率，但这是你以后可以重复使用的东西。