키보드를 마음대로 두드려서 얻은 숫자는 난수일까?
컴퓨터에서 난수random number가 어떻게 생성되는지 생각해 본 적이 있는가? (중략)
다음과 같은 두 수열을 보자.
000100100010010001000110001000100111100010101010101000011101011
1111000110001101000111100000100010000111110000100110100010000100
두 수열 중 하나는 내가 키보드에 마음대로 두드려서 만든 것이고, 다른 하나는 컴퓨터의 난수 생성 알고리즘을 이용한 결과이다. 당신은 이 두 수열을 구별할 수 있을까? 아마도 판단하기 어려울 것이라 예상된다. - P67
만약 길이가 10,000인 0과 1, 두 값으로 이루어진 난수열random number sequence이 있다고 할 때, 가장 긴 연속하는 1의 길이가 4라면 직관적으로도 이 수열에 문제가 있음을 알 수 있다. - P68
동전을 1,000회 연속으로 던질 때 앞면이 연달아 나타나는 횟수를 라고 하면, x < 8인 확률을 구하시오(계산이 좀 번거로우니, 건너뛰고 나중에읽어도 된다). - P68
결론적으로 동전을 10,000번 던질 때 앞면이 연속으로 나타나는 횟수가 8을 넘지 않을 확률은 약 0.0056%로 계산된다. - P71
하지만 도대체 진정한 ‘랜덤‘이란 무엇일까? 의외로 이것은 매우 미묘하고 심지어 철학적이기까지 하다. 예를 들어, 동전을 던져서 생기는 수열은 ‘랜덤‘일까? - P72
첫째, 역사적 난수를 관찰할 수 있어야 하는데, ‘진짜‘ 난수는역사와 무관하다. 따라서 역사적 난수를 분석하여 난수 추측성공률을 1만분의 1이라도 증가시킬 수 있다면, 이 난수는 여전히 ‘진짜‘가 아니다. - P74
둘째, 무한한 계산 능력을 가진 컴퓨터가 허용되어도 진정한난수는 도전자의 계산 속도에 의존하지 않는다. - P75
3단계 테스트: 분산 테스트, 난수 값의 변화 정도를 본다. 평균 테스트에서 기댓값이 100이라고 하자. 그러나 실제로 매번 10,000개의 난수 평균값을 확인할 때마다 많지도 적지도 않은,
정확히 100이라는 것을 발견한다면 이런 상황은 좋은가, 나쁜가? - P76
배럴 테스트는 이미 상당히 정확한 테스트이지만 이 정확도는 배럴의 분할 밀도와 관련이 있다. - P79
바로 콜모고로프 스미르노프 검정 Kolmogorov-Smirnov test 줄여서 KS 검정‘이라고 한다. - P79
‘확실‘에서 ‘불확실성‘
앞에서 난수 검정에 대해 알아보았다. 여기서는 컴퓨터를 사용하여 난수를 생성하는 방법에 대해 설명하려고 한다. 흔히 컴퓨터의 난수 생성 알고리즘을 가짜 난수 생성 알고리즘 또는 결정식 난수 생성기 DRBG라고 하는데, 이는 한 자리 이진수 0 또는 1을 50%의 확률로 생성할 수 있다는 뜻이다. - P82
그렇다면 왜 ‘가짜 난수 생성 알고리즘‘이라고 할까? 굳이 ‘가짜‘를 붙인 이유가 궁금하다. 그 이유는 앞에서도 언급한 ‘진짜‘ 난수의 요구 사항을 충족하지 못하기 때문이다. - P82
이후 구체적인 알고리즘 예에서도 모든 가짜 난수 생성 알고리즘에는 ‘주기‘가 있다는 것이 확인된다. 이 알고리즘은 매우 많은난수를 출력한 후, 다시 이전의 출력 모드로 돌아가 자신의 출력을 반복하기 시작한다. 이것이 ‘가짜‘ 난수라고 불리는 또 다른 이유이다. - P83
|