저수지 샘플링 (Reservoir Sampling)

전체 크기를 모르는 데이터 스트림을 딱 한 번만 지나가면서, 모든 원소가 정확히 같은 확률로 뽑히는 표본 k개를 O(k) 메모리로 유지하는 알고리즘.

1. 핵심 아이디어

표본 1개(k = 1)를 뽑는 경우부터 보자. 규칙은 딱 한 줄이다.

• 1번째 원소: 확률 1/1 로 무조건 표본에 넣는다.
• 2번째 원소: 확률 1/2 로 교체 → 두 원소 모두 최종 확률 1/2.
• 3번째 원소: 확률 1/3 로 교체. 기존 원소가 살아남을 확률은 (1/2)·(2/3) = 1/3.
• …계속하면 n개 모두 정확히 1/n.

표본이 k개인 일반형은 이렇게 확장된다: 처음 k개는 그대로 채우고, i > k인 원소는 확률 k/i 로 받아들여 저수지 안의 무작위 슬롯 하나를 덮어쓴다.

2. 알고리즘 코드

# 스트림 stream 에서 표본 k개를 균일 무작위로 뽑는다
import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):        # i = 0, 1, 2, ...
        if i < k:
            reservoir.append(item)              # 저수지 채우기
        else:
            j = random.randint(0, i)          # 0 ~ i 중 하나
            if j < k:                          # 확률 k/(i+1)
                reservoir[j] = item            # 무작위 슬롯 교체
    return reservoir

메모리 O(k), 시간 O(n), 스트림 1회 통과. n을 미리 알 필요가 전혀 없다.

3. 한 스텝씩 따라가 보기

아래에서 스트림이 하나씩 도착한다. 각 원소마다 주사위를 굴려 저수지에 넣을지 결정한다. 저수지에 들어간(살아있는) 원소는 파란색이다.

4. 정말 균일할까? — 10,000번 시뮬레이션

같은 스트림에서 표본 뽑기를 수천 번 반복하면, 모든 원소가 뽑힌 횟수가 거의 같아야 한다. 이론값은 각 원소마다 k / n. 아래 버튼으로 직접 확인해 보자.

5. 왜 확률 k/i 로 교체하면 균일해질까?

k = 1 기준으로, 스트림 길이가 n일 때 첫 번째 원소가 최종적으로 살아남을 확률을 따져 보자.

이 확률들을 모두 곱하면 예쁘게 약분된다 (망원 곱, telescoping):

P(1번 원소 생존) = 1/2 · 2/3 · 3/4 · … · (n−1)/n = 1/n

중간에 도착한 m번째 원소도 똑같다: 들어올 확률 1/m × 이후 m+1 … n에서 안 밀려날 확률 m/(m+1) · … · (n−1)/n = 1/n. 모든 원소가 대칭적으로 1/n이다. 귀납법의 핵심은 "i개까지 균일하다면 i+1개째를 확률 k/(i+1)로 받아도 여전히 균일하다" 이다.

6. 어디에 쓰이나