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 for my previous experiments, but it does not seem to provide a solution for this scenario, neither does 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 个以上的数字，事情可能会变得更有趣，考虑建立一个 table 来表示这种情况下的分位数函数，但代价是性能有所下降。

（就速度而言，很难击败我的解决方案，在最坏的情况下，您有几个分支 - 并且您正在帮助 分支预测器 最好的方法，随机数绘制将是性能瓶颈所在。

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);
    }
}

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

Answer 3

调用 Random.nextDouble() 是一项相当昂贵的操作。在这种情况下，您最好使用 Random.nextInt(n)

int num = rand.nextInt(10);
return num <= 5 ? 0 : num <= 8 ? 1 : 2;

Answer 4

这可能是一种更动态的方法，支持指定为双精度数组的任何概率分布：

public static int getRandomOutcome(double[] probaDist) {
    List<Double> sortedProbaDist = new ArrayList<>(probaDist.length);
    for (double d : probaDist) { sortedProbaDist.add(d); }

    Collections.sort(sortedProbaDist);

    double randomNumber = Math.random();
    
    double acc = 0;
    for (int i=0; i<sortedProbaDist.size(); i++) {
        acc += sortedProbaDist.get(i);
        if (randomNumber < acc) {
            return i;
        }
    }

    return probaDist.length;
}

请注意，该方法不会检查概率之和是否等于（接近）1。

Java 中的离散概率分布

Discrete Probability Distribution in Java

java

math

probability