超幾何模擬，一次通過洗牌一次拾取給出了錯誤的結果

我模擬的模型中有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的值。

來源

2017-09-28 ploosu2

你洗牌數組是偏頗的方式，我會建議使用費雪耶茨洗牌，而不是：

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

來源

2017-09-28 09:39:53 user1470500

謝謝！我一直在使用前一種洗牌的方式，而沒有考慮它是否有偏見。 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。

來源

2017-09-28 09:57:33 Gedrox

超幾何模擬，一次通過洗牌一次拾取給出了錯誤的結果

回答

相關問題