잠재 기록열은 A,B,C입니다. 처음 A를 담고 B가 오면1/2로 교체해요. 이때 후보가 B이면 바로 끝내 N=2로 둬요. 후보가 A이면 C를 읽고 이전 결정과 독립으로1/3확률로 C와 교체한 뒤 N=3에서 반드시 끝내요. 다음 후보표를 완성하라. N=3인 파일에서 읽은 세 기록의 최종 후보확률이 각각1/3일까요?
B를 담는 순간 종료하므로(N=2,B)의 확률은1/2입니다. B를 담지 않은1/2의 경로에서 A를 유지할 확률2/3, C로 바꿀 확률1/3을 곱하면 두 나머지 결합확률이 나와요.
| 종료 길이 N | 최종 후보 | 결합확률 |
|---|---|---|
| 2 | B | 1/2 |
| 3 | A | 1/3 |
| 3 | C | 1/6 |
N=3이라는 조건은 이미 두 번째 결정에서 B를 택하지 않았다는 정보를 줘요. 고정 길이3까지 무조건 진행했다면 B가 살아남는 경로도 포함해 각1/3이지만, 이 종료법은 그 경로를 제거해요. N=2인 종료 표본도 전부 B이므로 A와 B가 반반이 아니에요. 길이를 미리 모른다는 조건만으로 종료길이와 추출 난수가 독립이라는 결론을 낼 수 없어요.
원문의 Algorithm R은 각 고정 접두길이의 균등 표본을 유지해요. 이 자체 종료법은 그 알고리즘의 반례라기보다 원문 파일 끝 조건에 새 선택 정보를 끼워 넣었을 때 어떤 결론을 더는 가져올 수 없는지 보여 줘요. N이 알고리즘 난수와 독립으로 정해졌다면 N=n을 조건으로 해도 고정시점의 분포를 그대로 쓸 수 있어요.
교사는 “공정한 알고리즘도 무조건 불공정하다”라는 결론을 받아들이지 않아요. 고정 시점의 표본분포와 종료가 확인된 표본분포를 각각 표로 쓰고, 어느 경로가 종료조건 때문에 빠지는지 표시하게 해요.
착안 원문: Jeffrey Scott Vitter, Random Sampling with a Reservoir (1985). 수치·표·문항·풀이를 새로 만든 교육용 모형이며 원문 자료의 실제 관측값을 보고한 것이 아니에요.