저수지 샘플링 Reservoir Sampling

 어떤 array에서 random한 i번째 element를 뽑고 싶다고 하자. 일반적으로 전체 배열의 size를 알아내고 rand () % size를 한 후 해당 index를 가져오는 방식을 택할 것이다. 그러나 모종의 이유로 전체 배열 size를 알 수 없는 상황에서도 무작위 추출을 할 수 있다. 예를 들어 array가 아니라 singly linked list여서 끝을 모르고, 단 1번 순회해야 한다는 조건이라면? 1번의 순회로 size를 알아내도 index에 접근하는 데 O(n)이 걸리기 때문에 해결할 수 없다. 이런 상황에서 Reservoir sampling을 사용한다.

 

Reservoir Sampling

정의

 Reservoir sampling은 어떤 배열을 1번에 1개의 element만 보며 순회할 때 무작위 추출할 수 있는 알고리즘이다.

 

 오직 1개의 값만 저장할 수 있는 공간을 만든다. 이 공간에 i번째 element는 $\frac{1}{i}$의 확률로 가져오고, $\frac{i-1}{i}$의 확률로 이전 element를 유지한다. 이 간단한 방법으로 단 1번 순회하면서 무작위 추출을 할 수 있다.

 

 예를 들어...

 1번째 순회에는 1번째 element를 1의 확률로 가져온다. 1번째 element를 가져오지 않을 확률은 없다.

 2번째 순회에는 2번째 element를 1/2의 확률로 가져오고, 1/2의 확률로 원래 있던 element를 유지한다.(1번째 element)

 3번째 순회에는 3번째 element를 1/3의 확률로 가져오고, 2/3의 확률로 원래 있던 element를 유지한다.(2번째 순회에서 살아남은 element)

...

 n번째 순회에는 n번째 element를 1/n의 확률로 가져오고, $\frac{n-1}{n}$의 확률로 원래 있던 element를 유지한다.(n-1번째 순회에서 살아남은 element)

 

 

pseudo code : 1번의 순회, O(n)

 pseudo code는 아래와 같다. singly linked list를 탐색한다는 조건이다.

// input : head vertex of singly linked list
// node has value element and next element
// node->value : value of each node
// node->next : next pointer of each node
procedure Reservoir(head)
    count = 1
    curNode = head // 순회에 사용할 vertex
    curValue // 리턴값
    
    while curNode != NULL do
        if rand() % count == 0 then // k번째 vertex는 1/k의 확률로 남김
            curValue = curNode->value
        end if
        curNode = curNode->next
        count++
    end while
    
    return curValue

 

 처음부터 끝까지 단 1번 순회하기 때문에 time complexity는 O(n)이며, 별다른 추가 공간을 사용하지 않기 때문에 space complex는 O(1)이다.

 

 

증명

 n번째 element가 선택될 확률은 n번째 순회에서 n번째 element가 선택될 확률과 같으므로 1/n이다.

 

 n-1번째 element가 선택될 확률은

• n-1번째 순회에서 n-1번째 element가 선택될 확률 $\frac{1}{n-1}$
• n번째 순회에서 n번째 element가 선택되지 않을 확률 $\frac{n-1}{n}$
• 이 둘의 곱이므로 $\frac{1}{n}$이다.

n-2번째가 선택될 확률은 

• n-2번째 순회에서 n-2번째 element가 선택될 확률 $\frac{1}{n-2}$
• n-1번째 순회에서 n-1번째 element가 선택되지 않을 확률 $\frac{n-2}{n-1}$
• n번째 순회에서 n번째 element가 선택되지 않을 확률 $\frac{n-1}{n}$
• 이 셋의 곱이므로 $\frac{1}{n}$이다.

...

 

1번째가 선택될 확률은

• 1번째 순회에서 1번째 element가 선택될 확률 1
• 2번째 순회에서 2번째 element가 선택되지 않을 확률 1/2
• 3번째 순회에서 3번째 element가 선택되지 않을 확률 2/3
• ...
• n-1번째 순회에서 n-1번째 element가 선택될 확률 $\frac{n-2}{n-1}$
• n번째 순회에서 n번째 element가 선택되지 않을 확률 $\frac{n-1}{n}$
• 이들의 곱이므로 $\frac{1}{n}$이다.

 

수식으로 증명한다면

 어떤 수열 $A = A_1, A_2, ... , A_n$이 있다고 하자. i번째 sampling 결과를 $S_i$라고 하자.

 objective : Reservoir sampling을 따랐을 때 $A_1, A_2, ... , A_n$이 뽑힐 확률이 모두 $\frac{1}{n}$이다.

 

 Reservoir sampling을 따르면 i번째 sampling 결과는 

$S_i = 
\begin{cases}
 & A_i \text{ with p = 1/i } \\
 & S_{i-1} \text{ otherwise }
\end{cases}$

 

 이다. 이 때 $1 <= j <= n$인 어떤 j에 대해 $A_{j} = S_{n}$일 확률을 구하면 된다.

 

$P[A_j = S_n] \\
= P[S_n = S_{n-1} = S_{n-2} = ... = S_{j+1} = S_{j} = A_{j}]  \\
= P[(S_{n} = S_{n-1}) \ \cap \ (S_{n-1} = S_{n-2}) \ \cap \ ... \ \cap \ (S_{j+1} = S_{j}) \ \cap \ (S_{j} = A_{j})] \\
= P[(S_{n} = S_{n-1})] \ \times \ P[(S_{n-1} = S_{n-2})] \ \times \ ... \ \times \ P[(S_{j+1} = S_{j})] \ \times \ P[(S_{j} = A_{j})] \\
= \frac{n-1}{n} \ \times \ \frac{n-2}{n} \ \times \ ... \ \times \ \frac{j}{j+1} \ \times \ \frac{1}{j} \\
= \frac{1}{n}$

 

 1->2 : $A_j$가 $S_n$이 $S_n = S_{n-1}$이어야 하고, $S_{n-1} = S_{n-2}$, ... , $S_{j+1} = S{j}$여야 하며 $S_j = A_j$여야 한다.

 2->3 : 각 확률의 intersect로 표현되기 때문에 바뀐다.

 3->4 : 각 확률을 나타낸다.

 정리하면 $\frac{1}{n}$이 된다. 

 

 즉, $1 <= j <= n$인 어떤 j에 대해 $A_{j} = S_{n}$가 성립한다. 따라서 array의 모든 index가 뽑힐 확률이 $\frac{1}{n}$이다. 

 

 Q.E.D.