서로 다른 기록 A,B,C,D,…가 정해진 순서로 와요. 처음에는 A를 한 칸에 담아요. n번째가 오면 이전 후보를 새 기록으로 교체할 확률이 pₙ이고 아니면 그대로 둬요. 각 결정에는 이전 결정과 독립인 새 난수를 쓰고 pₙ은 n에만 의존해요. 최종 길이는 추출 난수와 무관한 파일 끝으로 정해지지만 미리 몰라요. 모든 고정 시점 n에서 지금까지 온 기록이 같은 확률로 후보가 되게 하려면 pₙ을 어떻게 정해야 하나요? 언제나1/2로 교체해도 되나요?
n번째 기록은 그 도착 순간에 교체해야만 후보가 되므로 그 확률 pₙ이 바로1/n이어야 해요. 이것이 필요한 조건이에요. 이전 n−1개가 각1/(n−1)로 남아 있었다면 교체하지 않을 확률(n−1)/n을 곱해 각1/n이 돼요. 처음 A가 유일한 시점부터 귀납하면 이 조건은 충분하기도 해요.
반반으로만 교체하면 네 기록 뒤 A,B,C,D의 확률은1/8,1/8,1/4,1/2입니다. 먼저 온 기록이 살아남아야 하는 교체 횟수가 더 많기 때문이에요. 각 교체 결정이 반반이라는 국소 설명은 최종 네 기록의 균등한 기회를 뜻하지 않아요. 파일이 고정 길이 N일 때 i번째 기록은 도착 때 채택확률과 이후 생존확률을 곱하면1/N이 돼요. i=1은 초기 후보라는 별도 시작조건으로 처리해요.
Vitter의 논문은 길이를 미리 모르는 순차 파일을 다루고 Waterman의 Algorithm R을 설명해요. 여기서는 한 칸만 남기는 경우에 공정성을 요구해 교체 법칙의 필요성과 충분성을 직접 따졌어요. 파일 끝이 후보의 정체에 따라 달라지는 경우는 지금의 끝 조건에 포함하지 않아요.
교사는 “이 단계에서 교체가 공정하다”와 “처리된 모든 기록의 기회가 같다”를 따로 쓰게 해요. 1/n은 외울 상수가 아니라 새 기록도1/n의 기회를 가져야 한다는 요구에서 나와요.
착안 원문: Jeffrey Scott Vitter, Random Sampling with a Reservoir (1985). 수치·표·문항·풀이를 새로 만든 교육용 모형이며 원문 자료의 실제 관측값을 보고한 것이 아니에요.