java - Java 中无替换的概率样本

Question

我有一个包含 10 个概率的列表(假设这些概率按降序排序):<p1, p2, ..., p10> 。我想对 10 个元素进行采样(不进行替换)，以便选择第 i 个索引的概率为 p_i。

在常见库(如 Random 等)中是否有现成的 Java 方法可供我用来执行此操作？

示例:5 元素列表:<0.4,0.3,0.2,0.1,0.0>

选择 5 个索引(无重复)，其选择概率由上面列表中该索引的概率给出。因此，索引 0 将以 0.4 的概率被选择，索引 1 以 0.3 的概率被选择，依此类推。

我已经编写了自己的方法来做到这一点，但觉得现有的方法会更好用。如果您知道这种方法，请告诉我。

Answer 1

这就是通常的做法:

    static int sample(double[] pdf) {
        // Transform your probabilities into a cumulative distribution
        double[] cdf = new double[pdf.length];
        cdf[0] = pdf[0];
        for(int i = 1; i < pdf.length; i++)
            cdf[i] += pdf[i] + cdf[i-1];
        // Let r be a probability [0,1]
        double r = Math.random();
        // Search the bin corresponding to that quantile
        int k = Arrays.binarySearch(cdf, random.nextDouble());
        k = k >= 0 ? k : (-k-1);
        return k;
    }

如果你想返回概率，请执行以下操作:

    return pdf[k];

编辑:我刚刚注意到你在标题中说不进行替换采样。这对于快速完成来说并不是那么简单(我可以给你一些我拥有的代码)。无论如何，在这种情况下你的问题没有任何意义。您无法从概率分布中进行无放回抽样。您需要绝对频率。

即如果我告诉你，我有一个盒子，里面装着两个球:橙色和蓝色，比例分别为 20% 和 80%。如果你不告诉我每个人有多少个球(绝对值)，我就无法告诉你几轮后你将拥有多少个球。

EDIT2:更快的版本。这不是通常的情况，但我在网上找到了这个建议，并且我也在我的项目中使用了它。

    static int sample(double[] pdf) {
        double r = random.nextDouble();
        for(int i = 0; i < pdf.length; i++) {
            if(r < pdf[i])
                return i;
            r -= pdf[i];
        }
        return pdf.length-1;  // should not happen
    }

要测试这个:

// javac Test.java && java Test

import java.util.Arrays;
import java.util.Random;

class Test
{
    static Random random = new Random();

    public static void sample(double[] pdf) {
        ...
    }

    public static void main(String[] args) {
        double[] pdf = new double[] { 0.3, 0.4, 0.2, 0.1 };
        int[] counts = new int[pdf.length];
        final int tests = 1000000;
        for(int i = 0; i < tests; i++)
            counts[sample(pdf)]++;
        for(int i = 0; i < counts.length; i++)
            System.out.println(counts[i] / (double)tests);
    }
}

您可以看到我们得到的输出与所使用的 PDF 非常相似:

0.3001356
0.399643
0.2001143
0.1001071

这是我运行每个版本时得到的时间:

• 第一个版本:0m0.680s
• 第二版:0m0.296s