H 세 개와 T 세 개를 일렬로 놓는 서로 다른 20개 문자열을 같은 확률로 골라요. 같은 글자가 연속한 최대 묶음을 run이라 불러요. HHHTTT는 run이 2개예요. run 수 R의 분포와 P(R≤2)를 구해 볼까요?
각 색의 양의 길이 묶음을 나누어 세면 다음 분포가 나와요.
| R | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 문자열 수 | 2 | 4 | 8 | 4 | 2 |
R=2는 HHHTTT와 TTTHHH뿐이므로
R=4인 문자열은 H로 시작하면 H 묶음 두 개와 T 묶음 두 개예요. 각 색 3개를 양의 두 길이로 나누는 방법은 2가지이므로 4개이고, T로 시작하는 4개를 더해요. R=3과 5는 시작 색의 묶음이 하나 더 많다는 점을 따로 세어요. 모든 칸의 수가 20이 되어 전체 목록과도 맞아요.
NIST의 run 정의에서 관측 순서를 새 통계량으로 읽는 관점을 가져왔어요. 이 확률은 H가 세 번이라는 조건 아래의 균등 문자열 모형이에요. 공정한 동전을 조건 없이 여섯 번 던진 64개 결과를 분모로 쓰지 않아요. 표가 작으므로 큰 표본 정규근사로 확률을 바꾸지 않아요.
성공 횟수만 세어 모든 문자열이 같다고 생각했다면 HHHTTT와 HTHTHT를 비교해 봐요. 두 결과의 H 개수는 같아도 순서가 주는 자료는 달라요.
착안: NIST/SEMATECH e-Handbook, 1.3.5.13 Runs Test for Detecting Non-randomness. 수치·문항·해설은 자체 교육용으로 작성했어요.
