超幾何シミュレーションでは、一度にシャッフルして一度にピッキングすると間違った結果になります

Question

N個の大理石があるモデルをシミュレートしています。 N個の大理石の中からn個の大理石を選び、n個のピックアップされたもののうちの正確にk個が良いという確率が求められる。

私はこの2つのやり方をしました。どちらも、私はK 'の真値とN-Kの偽値を含む配列を生成しました。しかし、最初の方法では、私はこの配列をシャッフルして最初の値を取り出し、どれくらいが「真」であるのかを数えました。 2番目の方法では、インデックスをランダムに選択し、配列からその要素を削除し、このn回ループしました（もちろん、実際の要素を数える）。

結果の分布はHyperGeometric(N, K, n)である必要があります。最初の方法は私に間違った結果をもたらしたが、2番目の方法は正しい結果を与えた。シャッフルされた配列の最初の要素を選んでも問題ないのですが、何が間違っていますか？ここに私の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

あなたは、配列が偏っているシャッフルの方法、私はフィッシャー-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

以下のコードは、あなたのシャッフルメカニズムが間違っていることを証明しています。コードはランダムな可能性のあるすべての結果でサイズ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; 
    } 
} 

出力この位置0になるように番号「1」のためのチャンスが1/3よりも大きいことを意味

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

です。それは10/27です。