균등난수(uniform random number) 만들어보자 #1

 

 

 

 

이번 글에서는 확률분포 중 가장 기본이 되는 연속 균등 확률분포(uniform distribution)와 균등 분포(uniform random number) 난수 생성에 대해서 이야기해보겠습니다.

실수 구간 $[0,1]$에서 정의된 연속 균등 확률분포는 말 그대로 확률변수가 고르게 분포되어 있다는 뜻입니다. 확률변수를 $X$라 할 때, 기호로는

$$ X \sim \mathcal{U}[0,1]$$

이라 씁니다.  확률밀도함수(pdf, probability density function)는

$$f(x) = 1 , x\in [0,1]$$

이죠. 임의의 자연수 $n$에 대해서 모멘텀이라 불리는 $X^n$의 기댓값은

$$\mathbb{E}(X^n) = \int_0^1 x^n f(x) df = \int_0^1 x^n = \frac{1}{n}$$

입니다. 특히 평균과 분산은 각각,

$$
\begin{align}
\mathbb{E}(X) &= \frac 12 \\
\mathbb{V}(X) &= \mathbb{E}(X^2) -(\mathbb{E}(X))^2 = \frac 13 - \frac14 = \frac1{12}
\end{align}
$$

입니다.

---

그러면 $\mathcal{U}[0,1]$ 을 따르는 균등 난수(uniform random number)는 어떻게 만들 수 있을까요?  사실 버스정류장 하나 골라 그 앞에서 기다리며 버스가 몇 분에 오는지를 기록하고, 그 숫자를 60으로 나눈 것도 균등 분포가 되겠죠. 하지만 이렇게 해서 난수를 신속하게 얻기도 힘들고, 만일 버스들이 정해진 시간을 맞춰 다니는 버스라면 난수라는데 의문이 들것입니다.

알고리즘을 이용하여 처음으로 난수 생성을 연구한 사람은 바로 폰 노이만(von Neumann)이라는 수학자였다고 합니다.

두책 [The Man from the Future: The Visionary Life of John Von Neumann]의 표지

폰 노이만의 방법은 다음과 같습니다.

1. $M=10000$으로 설정한다
2. $m_0 \in (0, 9999) $인 자연수 $m_0$을 하나 고른다.
3. $m_{i+1} = [m_i^2/100] \mod M$ 인 점화식으로 $\{m_i\}$들을 생성한다.

이것이 제대로 작동을 할까요? 폰 노이만이라는 천재가 만든 것인데요. 우선 딱 보기에도 $M$으로 나눈 나머지를 가지고 만든 수열(위의 3번 항)이라 나올 수 있는 값을 최대 $M$개입니다. ($M$으로 나눈 나머지는 $0,1,\cdots, M-1$ 밖에 없죠). 게다가,

만일 어떤 수열항 $k$에 대하여 우연히 $m_k =$이 나왔다 하면, 3번 항에 의해 $m_{k+1} = m_{k+2}=\cdots $는 모두 $0$이 됩니다. 난수 생성이 아닌, 0 생성이 되겠죠.

[빵 생산공장?]

간단하게 python으로 확인해 보겠습니다.

import math
import numpy as np


def vonNeumannRNG():
    M = 10000
    m0 = 9745
    res = []
    nCnt = 10000
    res.append(m0 / M)
    isTerminated = False
    for i in range(nCnt):
        m1 = (math.trunc(m0 ** 2 / 100)) % M
        if m1 == 0:
            isTerminated = True

        res.append(m1 / M)
        m0 = m1
    distinct_values = len(set(res))
    print('생성된 난수(처음10개): {}'.format(res[:10]))
    print('생성된 난수중 서로다른 수의 개수: {}'.format(distinct_values))
    print('생성된 난수열 중간에 0이 나오는가? {}'.format(isTerminated))

    print('생성된 난수 평균: {:.4f}'.format(np.mean(res)))
    print('생성된 난수 분산: {:.4f}'.format(np.var(res)))

    print('이론적인 난수 평균: {:.4f}'.format(1/2))
    print('이론적인 난수 분산: {:.4f}'.format(1/12))


if __name__ == '__main__':
    vonNeumannRNG()

코드 설명은 따로 다른 글에서 자세히 하도록 하겠습니다.

$m_0 = 9745$ 라 해 봤습니다. 그랬더니 결과가

생성된 난수(처음10개): [0.9745, 0.965, 0.1225, 0.5006, 0.06, 0.36, 0.96, 0.16, 0.56, 0.36]
생성된 난수중 서로다른 수의 개수: 9
생성된 난수열 중간에 0이 나오는가? False
생성된 난수 평균: 0.5100
생성된 난수 분산: 0.0875
이론적인 난수 평균: 0.5000
이론적인 난수 분산: 0.0833​

이렇게 나오네요. 평균과 분산은 이론가와 비교해서 얼추 잘 맞아떨어진 것 같은데요. 난수 중 서로 다른 개수가 9개밖에 안됩니다!  이래서야 난수 생성기라고 할 수 업겠죠. 다른 예를 들어 보겠습니다.

$m_0 = 1000$ 을 대입해 봤더니

 

생성된 난수(처음10개): [0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
생성된 난수중 서로다른 수의 개수: 2
생성된 난수열 중간에 0이 나오는가? True
생성된 난수 평균: 0.0000
생성된 난수 분산: 0.0000
이론적인 난수 평균: 0.5000
이론적인 난수 분산: 0.0833

Process finished with exit code 0

10000번을 돌렸는데, 서로 다른 난수는 2개이고 심지어 난수열 중간에 0이 나온네요.(True). 그러다 보니, 난수 평균과 분산은 죄다 0 이 나오는 게 당연합니다.

 

그럼에도 폰 노이만의 이러한 연구가 의미를 갖는 것은 바로 이런 난수발생 접근이 합동 생성(congruential generator)의 개념으로 발전을 하게 되기 때문인데요. 이에 대해서는 다음 글에서 알아보도록 하겠습니다.