超几何模拟，通过洗牌一次选择全部给出错误的结果

Question

我正在模拟有 N 个弹珠的模型，其中 K 个弹珠是好的。我们从 N 颗弹珠中挑选出 n 颗弹珠，并被问及在这 n 颗弹珠中恰好有 k 颗是好的概率。

我用两种方式做到了这一点：在这两种方式中，我都生成了一个包含 K 'true' 值和 N-K 'false' 值的数组。但是在第一种方法中，我打乱了这个数组并选择了前 n 个值并计算了其中有多少是 'true'。在第二种方法中，我随机选择一个索引并从数组中删除该元素，循环 n 次（当然还要计算我得到的 'true' 个元素）。

生成的分布应该是 HyperGeometric(N, K, n)。第一种方法给了我错误的结果，而第二种方法给出了正确的结果。为什么不能选择洗牌数组的前 n 个元素或者我做错了什么？这是我的 Javascript 代码：

function pickGoodsTest(N, K, n) {
    var origArr = generateArr(N, i=> i<K);
    shuffle(origArr);
    var goods = 0;
    for (let i=0; i<n; i++) if(origArr[i]) goods++;
    return goods;
}

function pickGoodsTest2(N, K, n) {
    var origArr = generateArr(N, i=> i<K);
    var goods = 0;
    for (let i=0; i<n; i++) {
        let rndInd = randInt(0, origArr.length-1);
        let wasGood = origArr.splice(rndInd, 1)[0];
        if (wasGood) goods++;
    }
    return goods;
}

//helper functions:

function generateArr(len, indFunc) {
    var ret = [];
    for (let i=0; i<len; i++) {
        ret.push(indFunc(i));
    }
    return ret;
}

function randInt(a, b){return a+Math.floor( Math.random()*(b-a+1) );}

function shuffle(arr) {
    let arrLen = arr.length;
    for (let i=0; i<arrLen; i++) {
        let temp = arr[i];
        let rndInd = randInt(0, arrLen-1);
        arr[i] = arr[rndInd];
        arr[rndInd] = temp;
    }
}

这些是值 N=10、K=6、n=5（模拟 500000 次）的结果图：

黄点是超几何pmf的值。

Answer 1

你打乱数组的方式有偏见，我建议改用 Fisher-Yates 打乱：

function shuffle(arr) {
    let arrLen = arr.length;
    for (let i=0; i<arrLen; i++) {
        let temp = arr[i];
        let rndInd = randInt(0, i);
        arr[i] = arr[rndInd];
        arr[rndInd] = temp;
    }
}

Answer 2

下面的代码证明你的shuffle机制是错误的。代码在所有可能的随机结果中洗牌大小为 3 的数组，并收集数字位于特定位置的机会统计信息。

import java.util.Arrays;

public class TestShuffle {
    public static void main(String[] args) {
        int[][] stat = new int[3][3];

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    int[] y = {0, 1, 2};
                    swap(y, 0, i);
                    swap(y, 1, j);
                    swap(y, 2, k);

                    stat[0][y[0]]++;
                    stat[1][y[1]]++;
                    stat[2][y[2]]++;
                }
            }
        }

        System.out.println(Arrays.deepToString(stat));
    }

    private static void swap(int[] y, int i, int k) {
        int tmp = y[i];
        y[i] = y[k];
        y[k] = tmp;
    }
}

输出为

[[9, 10, 8], [9, 8, 10], [9, 9, 9]]

这意味着数字“1”出现在位置0的几率大于1/3。现在是 10/27。

超几何模拟，通过洗牌一次选择全部给出错误的结果

Hypergeometric simulation, picking all at once by shuffling once gives wrong result

javascript

arrays

algorithm

simulation

probability-distribution