균등 추출은 난수 생성기에서 나온 값이 균등하다는 사실만으로 끝나지 않고, 목표 범위로 줄이는 변환도 각 결과에 같은 수의 원천 값을 배정해야 성립합니다. 이 노트는 작은 전수 반례에서 출발해 정수 경계, 실패 정책, 보안 난수와 정책적 후보 집합을 분리합니다.
원천 균등성과 결과 균등성
일반 모델은 원천 표본 공간을 결과 칸에 나누어 담는 문제입니다. M = qn + r이면 r개 결과가 q+1개의 원천 값을 받고 나머지 결과가 q개만 받으므로, 단순 나머지는 r이 0일 때만 정확히 균등합니다. 이 식을 먼저 쓰면 “난수를 충분히 많이 뽑으면 평균적으로 괜찮다”와 “각 시도가 계약상 균등하다”를 구분할 수 있습니다.
질문 세 개 중 하나를 고르려고 0부터 7까지 균등하게 나오는 난수에 % 3을 적용한다고 합시다. 가능한 원천 값 여덟 개를 모두 적어 보면 문제를 바로 볼 수 있습니다.
| 나머지 | 이 결과를 만드는 원천 값 | 확률 |
|---|---|---|
| 0 | 0, 3, 6 | 3/8 |
| 1 | 1, 4, 7 | 3/8 |
| 2 | 2, 5 | 2/8 |
0과 1이 더 자주 나옵니다. 원천 범위의 크기가 후보 수로 나누어떨어지지 않아 생기는 나머지 편향(modulo bias)입니다. 난수 생성기 품질과 범위 변환의 정확성은 별개의 문제입니다.
균등 분할 가능한 수락 구간
실패를 재현하려면 M=8, n=3인 함수에 원천열 [6, 7, 5]를 주입합니다. 예측 결과는 6과 7에서 두 번 거절하고, 0부터 5 중 첫 값인 5에 대해 5 mod 3 = 2를 반환하는 것입니다. 거절 표본을 다른 결과로 재매핑하지 않아야 조건부 분포가 유지됩니다.
0~5만 사용하면 각 나머지가 정확히 두 번씩 등장합니다. 6과 7은 다른 후보에 억지로 배정하지 않고 버린 뒤 새 난수를 뽑습니다. 필요한 분포가 될 때까지 부적합한 표본을 버리는 방법이 거절 추출(rejection sampling)입니다.
그림을 글로 읽기
- 원천 x ∈ [0,8): 각 값 확률 1/8
- x < 6: 0,1,2,3,4,5
- x ≥ 6: 6,7은 버림
- x mod 3 반환: 각 결과 조건부 확률 1/3
- 원천 x ∈ [0,8) → x < 6: 수락
- 원천 x ∈ [0,8) → x ≥ 6: 다시 추출
- x < 6 → x mod 3 반환: 나머지 변환
원천 값 개수가 M이고 후보 수가 n이면 limit = floor(M/n)*n을 구합니다. 예를 들어 M=8, n=3이면 limit=6이고 수락 구간 [0,6)에서 나머지 0·1·2는 각각 두 번씩 나타납니다. 6과 7을 버리면 각 결과가 같은 수의 원천 값에 대응하므로, 수락된 표본의 나머지가 균등해집니다. 이것은 샘플을 많이 뽑아 비슷하게 보인다는 통계적 관찰보다 직접적인 근거입니다.
범위와 산술을 명시한 슈도코드
구현을 고를 때는 API가 [0,M)을 직접 주는지, 최대값을 포함하는지, M을 표현할 타입이 있는지부터 확인합니다. n=M이면 limit=M이고 첫 표본을 그대로 반환하며, n=1이면 항상 0을 반환하는 경계를 별도 테스트하면 범위 계산과 나머지 연산을 혼동한 오류를 빨리 찾을 수 있습니다.
uniformBelow(n):
require integer n and 1 <= n <= M
limit = M - (M mod n)
loop:
x = nextUniformIntegerBelowM() # 실패는 실패로 전달
require 0 <= x < M
if x < limit:
return x mod n
M은 최댓값이 아니라 가능한 값의 개수입니다. 균등한 unsigned 32비트 값은 [0,2^32)이므로 M은 2^32입니다. 최대 unsigned 32비트 값 2^32-1을 M으로 쓰면 경계 계산이 달라집니다. M 자체를 표현할 넓은 정수 타입이나 안전한 라이브러리 API가 필요합니다.
JavaScript의 Number는 2^32를 정확히 표현하지만 비트 연산은 일반적으로 32비트 변환을 수행하므로 1 << 32로 M을 만들면 안 됩니다. 실제 언어의 signed 변환·나머지 규칙과 난수 API의 포함·제외 상한을 확인하세요.
500개 후보의 거절 구간
2^32 = 4,294,967,296이고 이를 500으로 나눈 나머지는 296입니다. 따라서 limit=4,294,967,000이고 그 이상 296개 값만 버립니다. 편향이 작다고 없어지는 것은 아니며, 여러 추첨이 공정성의 계약이라면 범위 매핑을 올바르게 하는 편이 좋습니다.
수락 확률은 limit/M, 평균 원천 호출 수는 M/limit입니다. 1<=n<=M에서 기대 호출 수는 2보다 작지만 개별 호출이 반드시 두 번 안에 끝나는 것은 아닙니다. 불량 원천이 거절 값만 내놓을 수도 있습니다. 취소·기한·원천 실패 처리와 알고리즘의 균등성 전제를 분리해야 합니다.
호출 횟수 상한을 두었다면 상한 초과는 실패로 반환합니다. 그때 % n으로 아무 값이나 반환하는 fallback은 성공 결과를 다시 편향시킬 수 있습니다.
공정성과 예측 불가능성
후보를 먼저 줄이는 정책과 후보 안에서 균등하게 뽑는 알고리즘은 서로 다른 층입니다. 예를 들어 최근 노출 질문을 제외한 집합을 만들었다면 그 집합의 크기와 생성 규칙을 로그로 남기되, 토큰·추첨처럼 예측 불가능성이 필요한 용도에서는 seed 고정 테스트 경로를 운영 경로와 분리합니다.
고정 seed 의사난수는 테스트 재현에 유용합니다. 같은 seed·같은 입력·같은 알고리즘 버전이면 같은 선택을 되풀이할 수 있습니다. 그러나 공격자가 다음 값을 예측하지 못해야 하는 토큰·추첨에는 적절한 보안 난수와 별도 위협 모델이 필요합니다. 거절 추출은 약한 난수 생성기를 암호학적으로 안전하게 바꾸지 않습니다.
반대로 학습 화면에서 바로 직전 질문을 제외하거나 최근 본 질문의 가중치를 낮추는 것은 의도적인 노출 정책입니다. 그 정책이 정한 후보 집합에서 균등하게 고르는 것과 전체 목록에서 항상 균등하게 고르는 것을 구분합니다.
작은 원천 전수 검사
M=8, n=3에서 수락된 0~5의 나머지 빈도가 [2,2,2]인지 셉니다. 고정 원천 [7,6,5]를 주면 앞 두 값을 거절한 뒤 2를 반환해야 합니다. n=1, n=M, n=0, n>M, 원천 오류도 별도로 검사합니다.
큰 범위의 빈도 검사는 보조 점검입니다. 드문 편향이 작은 표본에서 보이지 않을 수 있으므로 정확한 수락 경계와 각 결과의 원천 개수를 먼저 검증하는 것이 중요합니다.