Reservoir Sampling

Q. 전체 모집단의 갯수(n)를 알지 못하는 상황에서 편향 없이 1개를 샘플링하면 각 샘플링의 확률은 1/n이 된다. 어떻하면 이를 코드로 구현할 수 있을까?

 

https://www.youtube.com/watch?v=A1iwzSew5QY

위의 영상에 방법이 나와 있다. 모자 n개가 있고, i 번째 모자를 최종적으로 쓰고 있으려면

(i 번째 모자를 쓰고), (i+1번째 모자를 쓰지 않고), (i+2번째 모자를 쓰지 않고)... (n번째 모자를 쓰지 않으면 된다)

 

즉, (i번째 모자를 최종적으로 쓰고 있을 확률) = (i 번째를 선택할 확률)

= (1 / i) * (1 - (1/(i+1))) * (1 - (1/(i+1))) ...  *(1 - 1/(n))

 

이 식을 정리하면 1 / n 이 된다. 

 

따라서, 코드로 정리하면 다음과 같다. 전체 모자 갯수(n)을 알지 못하는 상황에서

i 는 계속 증가 시키면서 우연히 i가 나누어 떨어지는 경우. res = node->val이 된다(즉 모자를 쓰게 된다)

아래와 같이 구현하면, n개의 모집단을 편향 없이(un-biased) 선택하게 된다.

    /** Returns a random node's value. */
    int getRandom() {
        int res = head->val;          // 첫번째 모자는 확률이 1이므로 쓴다. 
        ListNode* node = head->next;  // 따라서, i는 2부터 시작한다. 
        int i = 2;
        while(node){
            int j = rand()%i;
            if(j==0)
                res = node->val;
            i++;
            node = node->next;
        }
        return res;
    }

 

풀어볼 문제)

https://leetcode.com/problems/linked-list-random-node/

Linked List Random Node - LeetCode