Computational structures of random phenomena and their applications

Abstract

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.