4 Random Number in a nutshell

2017 July

우리가 알고 있는 무작위 수는 사실 무작위 수가 아니다.

이번 글에서는 의사 무작위 수로 불리는 이유를 볼 것이다. 무작위 수의 성질을 3가지로 볼 수 있다.

  1. 무작위성(Randomness) : 말 그대로 수열이 무작위로 되어있는 성질
  2. 예측 불가능성 :다음 수를 예측할 수 없다는 성질
  3. 재현 불가능성 : 같은 수열을 재현할 수 없다는 성질

무작위 수를 분류한다면 약한 의사 무작위 수, 강한 의사 무작위 수 그리고 진정한 무작위 수가 된다. 약한 의사 무작위 수는 무작위성만 가지고 있으며, 강한 의사 무작위 수는 예측 불가능성까지, 진정한 무작위 수는 재현 불가능성까지 가진다.

기본적인 무작위 수 생성기인 선형 합동 생성기(Linear congruential generator, LCG)를 보자.

LCG의 수식 \({x}_{n+1} \leftarrow (k \times x_n + c)\; mod \; m\)

// 실제 stdlib/rand.c에서 쓰이는 LCG 코드
// ISO9899
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

선형 합동법의 단점을 보려는 것은 아니다. 선형합동법을 이용한 무작위 수 생성을 보면 재밌는 사실이 있다.

\(45 \;6\; 65\; 86\; 85\; 66\; 5\; 46 \; 25\; 26\; 45\; 6\; 65\; 86\; 85\; 66\; 5\; 46 \;25 \;26 \;45\; 6\; 65 \;86 \;85 \;66 \;…\)

첫 번째 수인 \(45\)가 \(11\)번째 에서 다시 나타난다. 반복되는 수열 부분을 주기(period)라고 한다. 당연히 주기를 갖는 수열은 재현이 불가능하지는 않을것이다. 무작위 수 생성기로 사용해봤지만 수열이 반복한다면 생성한 수열의 예측이 가능하게 된다.

\({x}_{n+1} \leftarrow r \times x_n \times (1 - x_n)\)

초기 시드값을 \(0\)과 \(1\)사이의 값으로 해보면 좀 더 그럴듯한 난수열을 만들 수 있을 것이다. 수식을 반복해서 계산해보면 수열의 값은 \([0,1]\)의 부분구간인 \([a,b]\)에서 뛰게될것이다. \(x_n\) 으로 변환하면

\(y_n \leftarrow \frac{x_n - a}{b-a}\)

“무작위” 수 \(y_n\)를 생성하는 수식을 얻을 수 있다 .

무작위 수열을 생성하는 컴퓨터 프로그램의 아이디어는 체이틴-콜모고로프 이론에 기초한다. 논문의 내용을 요약하면 이렇다. 무작위 수열을 생성하는 가장 짧은 프로그램의 짧은 길이를 가진 유한 수열의 무작위성을 정의한다. 그리고 프로그램이 길어질수록 수열은 더욱 무작위성을 띈다. 또한 프로그램이 만드는 수열이 수열의 길이만큼 복잡할 경우 가장 무작위하다는 것을 제안하고 있다.

간단하게 수열을 이진법으로 한다면 \(01101\)으로 된 수열을 \(m\)만큼 반복하여 만드는 짧은 프로그램을 생각해볼 수 있다.

for i <- to m
    output 0,1,1,0,1

프로그램은 23개의 아스키 문자와 변수 \(m\)을 포함하고 있다. 그리고 \(m\)은 프로그램 길이의 식인 \(23 + log M\) 이 된다. 그리고 프로그램은 \(n=5m\) 의 길이를 가지는 수열을 생성한다. 무작위성을 측정하는 방법 중 하나는 문자열의 길이와 프로그램 길이 비율을 맞추는 것이다. m의 반복으로 만들어지는 수열 \(0,1,1,0,1\)은 다음과 같은 무작위성을 가진다.

\(r \leq \frac{23 + \log{m} }{5m}\)

이 무작위성 비율의 \(m\)이 증가할수록 수열에서 \(0\) 혹은 \(1\)이 많아지는 경향이 있음을 알 수 있다. 극한으로 본다면 무작위성 비율은 0이다. 엄밀히 말해 무작위는 아니라는 의미다.

자 그러면, 특정 무작위 수열 \(S\)가 무작위 임을 증명하려면 어떻게 해야할까? \(S\)보다 짧은 프로그램이 없어야한다. 콜모고로프는 어떤 수열이 자기 자신의 길이와 같은 크기의 복잡성을 가질 때 그런 수열을 무작위적(randomness)라 부르자고 제안했다. \(S\)보다 짧은 프로그램이 없어야 한다는 의미는 “길이 \(N\)의 수열이 주어졌을때 이 수열이 복잡성 \(N\)을 가진다라는 것을 증명할 수 있는가?”라는 질문으로 바뀔 수 있다.

여기서 체이틴과 콜모고로프는 알고리즘적 정보이론을 만들면서 베리의 역설을 응용했음을 알 수 있다.

“베리의 역설은 원래 영어에 대해 이야기하지만, 이는 너무 모호하다. 나는 대신 컴퓨터 프로그래밍 언어를 선택한다.” - 인포메이션 pp. 461

베리의 역설을 응용하면 아스키문자를 사용하여 정의될 수 없는 가장 작은 수가 무엇인가?가 된다. 만일 이 수가 발견된다면 역설이 등장할것이다. 다시 말해 수열이 프로그램 \(P\)에 의해서만 생성될수 있는지 확인하면 된다라는 말이 된다.

여기서 재밌는 결론이 나올 수 있는데, 괴델은 정의한 \(PM\)에서 어떤 공리 체계는 불완전하다는 것, 즉 \(PM\)에서 증명할 수 없는 정리가 있음을 보여주었다. 물론 길이가 긴 수열이 무작위라고 주장하는 다양한 정리가 있지만, 의사 무작위일 뿐이다. 체이틴-콜모고로프 논문의 핵심은 수열이 무작위 인지 아닌지 결코 알 수 없지만 적어도 프로그램으로 생성된 수열의 무작위성 정도를 측정할 수 있다는 것이다.

그리고 명제와 프로그램은 수학적으로 엄밀이 정의될 수 있다는 것이다. 러셀의 역설에서 시작한 괴델의 불완전성 정리도 튜링 기계의 멈춤 문제도 프로그램 내에서 정의될 수 있다는 의미가 된다.

진정한 무작위 수는 어디서 얻을 수 있을까?

Reference

  • 각 언어별 의사 무작위 수 생성 방법
  • 무작위성
  • 컴퓨터 프로그래밍의 예술 2 vols. 도널드 크누스 지음. 류광 옮김. 한빛미디어. 2006년. pp. 
  • 인포메이션. 제임스 글릭 지음. 박래선, 김태훈 옮김. 김상욱 감수. 동아시아. 2017년. pp. 441~
  • Numerical Recipes - The Art of Scientific Computing 3rd pp. 430-
  • Gregory J. Chaitin. Algorithmic Information Theory. Cambridge University Press, Cambridge, 1993. pp. 179-183