작은 가상 프로그램이 시작 번호를0부터15까지에서 한 번 골라요. 그 뒤에는 추가 무작위 입력 없이, 정해진 규칙으로0과1을 여덟 자리 출력해요. 시작 번호가 같으면 출력도 항상 같아요. 각 자리에0이나1이 보인다는 이유로, 독립적인 동전 여덟 번과 같은 결과가 될까요?
시작 번호의 종류는16개예요. 하나의 시작 번호에서 하나의 문자열만 나오므로 서로 다른 출력은 많아도16개예요. 여러 시작값이 같은 문자열을 만들면 종류는 더 적어집니다. 출력 규칙을 복잡하게 만들거나 실행 시간을 늘려도, 추가 입력이 없다는 조건에서는 이 개수 상한이 유지돼요.
반면 서로 독립이며 앞뒤 확률이 각각1/2인 동전 여덟 번을0과1로 적으면 가능한 문자열 수는 다음과 같아요.
모든 문자열의 확률도(1/2)⁸=1/256로 같아요. 가상 프로그램은 최소256−16=240개 문자열을 전혀 만들지 못해요. 따라서 그 출력의 전체 확률분포가 독립적인 여덟 비트의 균등분포와 같을 수 없어요.
최소 몇 개의 시작값이 필요한지도 셀 수 있어요. 가능한 출력256종을 모두 만들려면 시작값도 적어도256종 있어야 해요. 이는 필요조건이며 시작값256개만으로 충분하다는 뜻은 아니에요. 서로 다른 출력으로 연결되어야 하고 균등분포를 원하면 선택 확률도 맞아야 해요. 화면에 출력된 자리 수와, 절차가 실제로 선택할 수 있는 결과의 다양성은 다른 양이에요.
참고한 수학 개념: Mathigon · True Randomness.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.