The aim of this work is to investigate computational structures of random phenomena in various fields such as pseudorandom number generations and ergodic theory.
First, we propose new empirical tests for pseudorandom numbers based on random walks on $\mathbb Z_n={0,1, …,n-1}$. The tests focus on the distribution of arrival time at zero starting from a fixed point x neq 0. Three types of random walk are defined and the exact probability density of the arrival time for each version is obtained by the Fourier analysis on finite groups. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators, which are considered to be flawless until now.
Next, we observe the limiting behavior of the generalized Khintchine constants. Let $T_p(x)=1/x^p (mod1)$ for 0 ＜ x ＜ 1 and $T_p(0)=0$. It is known that if $p ＞ p_0=0.241485…, then $T_p$ has an absolutely continuous ergodic measure. Put $a_n=\left\lfloor\left(1/T_p^{n-1}(x)\right)^p\right\rfloor$, $n ≥ 1,$ where $\lfloor t \rfloor$ is the integer part of t. For a real number q, define averages of $a_n$ by
◁수식 삽입▷(원문을 참조하세요)
Let $K_{p,q}:=lim_{n → ∞}K(p,q,n,x)$. For almost every x, we show that (i) $K_{p,q} ＜∞$ if and only if $q ＜1/p$, (ii) if q=0, then $lim_{p → ∞}(log K_{p,q})/p = 1$, (iii) if q ＜0, then $lim_{p → ∞}log K_{p,q}/log{p} = 1/|q|$,where `log` denotes the natural logarithm. The limiting behavior of $K_{p,q}$ is investigated as p downarrow $p_0$ with high precision computer simulations.
난수 발생, 에르고딕 이론등 다양한 분야에서 나타나는 랜덤 현상의 계산적 구조를 연구하였다. 먼저 순환군 $\mathbb Z_n=\{0,1,…,n-1\}$ 위에서의 랜덤 보행을 이용하여 난수 발생기를 검정하였다. 새로운 검정법은 $\mathbb Z_n$ 위의 한 점 x ≠ 0에서 출발하여 0으로 도착하는 시간의 분포에 기초하고 있다. 여러가지의 랜덤 보행에 의한 도착시간의 정확한 확률분포는 유한군 위에서의 푸리에 해석을 이용하여 구하였고 검정 결과로서 현재까지 결검이 거의 없는 것으로 알려진 CMRG, MT 등의 난수 발생기의 결점을 확인하였다.
다음으로 일반화된 킨친 상수의 극한값을 연구하였다. $T_p(x)=1/x^p (mod1)$, $0＜x＜1$, $T_p(0)=0$ 라 하자. 만일 $p>p_0=0.241485…$이면 $T_p$의 에르고딕 측도 $ ρ_p dx$가 존해함이 알려져 있다. $a_n=\left\lfloor\left(1/T_p^{n-1}(x)\right)^p\right\rfloor$, $n ≥ 1$ 라고 하고 실수 $q$에 대하여 $a_n$의 평균 K(p,q,n,x)를 다음과 같이 정의하자.
◁수식 삽입▷(원문을 참조하세요)
$K_{p,q}:=lim_{n→∞}K(p,q,n,x)$라고 하자. 확률 1로서 다음이 성립합을 증명하였다. (i) $K_{p,q}＜∞$ 일 필요충분조건은 q＜1/p이다. (ii) q=0이면 $lim_{p→∞}(log K_{p,q})/p = 1$ 이다. (iii) q＜0이면 $lim_{p→∞}log K_{p,q}/log{p} = 1/|q|$이다. 또한 p가 $p_0$로 감소하면서 접근할 때 $K_{p,q}$의 성질을 매우 정밀한 컴퓨터 실험을 통해 연구하였다.
