超几何模拟，一次通过洗牌一次拾取给出了错误的结果

问题描述：

我模拟的模型中有N个弹珠，其中K弹珠好。我们从N个弹子中选取n个弹珠，并被要求提供n个拾取弹子中恰好有k个为好的概率。超几何模拟，一次通过洗牌一次拾取给出了错误的结果

我做了这两种方法：在两个我生成一个数组包含K'真'值和N-K'假'值。但在第一种方法中，我对这个数组进行了洗牌，并选取了n个第一个值，并计算出其中有多少是“真实”的。在第二种方法中，我随机选取一个索引，并从数组中移除该元素，循环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的值。

答

你洗牌数组是偏颇的方式，我会建议使用费雪耶茨洗牌，而不是：

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

谢谢！我一直在使用前一种洗牌的方式，而没有考虑它是否有偏见。 Fisher-Yates shuffle产生了正确的结果（如预期的那样，因为维基百科说它没有偏见）。 – ploosu2

答

下面的代码证明了你的洗牌机制是错误的。代码是在随机的所有可能结果中混洗一个大小为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。

超几何模拟，一次通过洗牌一次拾取给出了错误的结果

相关推荐