한 번에 한 번씩 임의로 골라내는 초고속 시뮬레이션으로 잘못된 결과가 나타납니다.

Question

N 구슬이있는 모델을 시뮬레이션 중이며 그 중에서 K 구슬이 좋습니다. 우리는 N 개의 구슬에서 대리석을 골라 낸 다음, 엄선 된 것 중에서 정확히 k가 좋은 확률을 묻습니다.

나는이 두 가지 방법으로 만들었습니다. 둘 다 K 'true'값과 N-K 'false'값을 포함하는 배열을 생성했습니다. 그러나 첫 번째 방법에서는이 배열을 뒤섞고 첫 번째 값을 선택하고 이들 중 얼마나 많은 수가 '참'인지 계산했습니다. 두 번째 방법에서는 무작위로 색인을 선택하고 배열에서 해당 요소를 제거하고이 n 번 반복합니다 (물론 내가 가진 '참'요소를 계산합니다).

결과 분포는 HyperGeometric(N, K, n)이어야합니다. 첫 번째 방법은 나에게 잘못된 결과를 주었지만 두 번째 방법은 올바른 결과를주었습니다. shuffled 배열의 첫 번째 요소를 선택하는 것이 좋지 않은 이유는 무엇입니까? 아니면 내가 뭘 잘못 했습니까? , K = 6, N = 5 (시뮬레이션 500,000 회)

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 :

옐로우 도트 여기 내 자바 스크립트 코드의 은 초 고밀도 pmf의 값이다.

Answer 1

어레이는 바이어스 셔플 방법, 나는 피셔 - 예이츠 대신 셔플 사용하는 제안 :

는

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

출력이 1/3보다 큰 숫자 "1"에 대한 기회가 위치 0에있을 것을 의미

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

이다. 그것은 10/27입니다.