[2008/10/12] 카오스를 이용해서 간단하게 난수(random number) 생성하기

Written by Pilwon Hur (2008/10/12)

난수(random number) 는 일상의 보이지 않는 곳에서 의외로 많이 쓰이고 있다. 예를 들어 플래시 게임에서 배경으로 자주 등장하는 흩날리는 눈(snow)이나 윌리를 찾아라 에서 처럼 군중들의 움직임을 나타내기 위해서 난수를 사용하기도 한다. 어떤 컨트롤 모델에서 외부에서 작용하는 외란을 시뮬레이션 상으로 구현하기 위해서 난수를 사용하기도 하며, 은행에서 보안카드에 입력하기 위한 카드의 순번을 난수로 생성기도 한다. 아무튼 난수는 여기 저기서 많이 사용하며, 난수를 생성하는 방법도 여러가지이다.

여기서는 정말 간단하게 난수를 생성하는 방법을 말하고자 한다. 결론부터 이야기 하면 카오스(Chaos) 를 이용하는 것이다. 카오스는 보통 다음과 같이 2가지로 특징 지어진다.

1. Sensitive dependence on initial condition

2. Trajectory is dense

먼저 Sensitive dependence on initial condition 란, 모든 카오스 시스템은 초기값(initial condition) 에 아주 민감하게 반응한다는 의미이다. 초기값이 아주 조금만 바뀌어도 그 결과에 따른 time series 값은 아주 달라진다. 예전에 한창 유행했던 나비효과라는 것도 이런 이유와 관련이 있다. 두번째로, Trajectory is dense 란 궤적(Trajectory) 이 모든 state 를 다 방문한다는 의미이다. 물론, 여기서 중복은 하나도 되지 않는다. 중복이 일어나게 되면 그 시스템은 카오스가 아니라 주기 운동(periodic motion) 을 하게 된다. 중복이 하나도 일어나지 않는다는 말 자체가 이상하게 느껴질 뿐 아니라 컴퓨터를 통해서 시뮬레이션 (10만번 이상 iteration)을 하면 중복이 일어나는 것 처럼 보이는 이유는 해상도(resolution) 가 낮고, 정밀도(precision) 의 제한이 있기 때문이다.

결국 이 두가지 성질을 이용하면 난수를 생성할 수 있을 거라는 것은 어려운 생각이 아니다. 그렇다면 어떠한 카오스 시스템을 이용할까? 가장 쉬운 경우는 Logistic map 이다.

아래의 Bifurcation diagram 을 살펴보면 \(r\) 이 4가 될때 \(X_n\) 은 \([0, 1]\) 의 범위에서 완벽한 카오스가 된다.

그러므로 적당한 초기값 \(X_0\) 를 주고 Eq. (1) 에 recursive 하게 대입을 하면 거기서 나오는 \(X_n\) 값이 난수가 된다. 초기값으로는 보통 현재의 시간값을 seed로 주게 된다.

물론 이렇게 구한 난수는 약간 문제가 있다. Perron-Frobenius operator 에 의해서 distribution 의 변화를 보면 invariant distribution 을 구할 수 있다. 초기 distribution 을 uniform distribution 이라고 가정하면 Logistic map 에 의해서 매 iteration 마다 변화되는 distribution 은 궁극적으로 다음의 invariant distribution 으로 바뀐다.

이고, 여기서

는 invariant distribution 이고, \(P\) 는 Perron-Frobenius operator 이다. 이제, 앞에서 말한 문제점이란 바로 \(f_* (x)\) 가 uniform distribution 이 아니라 \(U\) 자 모양의 distribution 이라는 점이다. 그러므로, \([0 1]\) 사이의 숫자들이 모두 골고루 나오는 것이 아니라 양 극단으로 갈수록 더 많은 확률로 숫자들이 나온다는 것이다. 이것은 그렇게 좋은 난수 발생기는 되지 못한다. 하지만, 이러한 방법으로 난수를 발생할 수 있다는 것을 설명한 것에 의의를 둔다.

지금 Espresso Royale 에 앉아 있다.ㅋㅋ