在Java中用概率取样，不需要替换

Question

我有一个10个概率的列表（假设这些概率是按降序排列的）。<p1, p2, ..., p10>. 我想对10个元素进行抽样（不需要替换），使其选择的概率为 i-th index是p_i。

在Random等常用库中有没有现成的Java方法可以让我用它来实现？

例子：5元素列表：<0.4,0.3,0.2 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];

EDIT: 我注意到你在标题中说 采样不更换. 这并不是那么琐碎的事情，要快速完成（我可以给你一些我的代码）。总之，你的问题在这种情况下没有任何意义。你不能从一个概率分布中进行无替换的采样。你需要绝对频率。

即：如果我告诉你，我有一个盒子，里面装了两个球：橙色和蓝色，比例分别是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

Answer 2

使用sample[i]作为你的值数组的索引。

Public static int[] WithoutReplacement(int m, int n) {

    int[] perm = new int[n];
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
    //take sample
    for (int i = 0; i < m; i++) {
        int r = i + (int) (Math.random() * (n - 1));
        int tmp = perm[i];
        perm[i] = perm[r];
        perm[r] = tmp;
    }
    int[] sample = new int[m];
    for (int i = 0; i < m; i++) {
        sample[i] = perm[i];
    }
    return sample;
}