§E20.33擬似乱数生成器

証明.(1)を示す。$s_0,\ldots,s_{|S|}$は$S$の元の$|S|+1$項の列であるから、鳩の巣原理により、ある$0\le i<n\le|S|$に対して$s_i=s_n$が成り立つ。$s_n\in\{s_0,\ldots,s_{n-1}\}$を満たす最小の正整数$n$を$n_0$とすると、$n_0\le|S|$であり、$n_0$の最小性により$s_0,\ldots,s_{n_0-1}$は相異なる。$s_{n_0}=s_\mu$を満たす$\mu<n_0$はただ一つであり、$\lambda:=n_0-\mu$と置けば、組$(\mu,\lambda)$は二条件を満たし、$\mu+\lambda=n_0\le|S|$である。逆に組$(\mu',\lambda')$が二条件を満たすとし、$n:=\mu'+\lambda'$と置く。$s_n=s_{\mu'}$であるから$s_n\in\{s_0,\ldots,s_{n-1}\}$である。$1\le n'<n$ならば$s_0,\ldots,s_{n'}$は相異なるから、$s_{n'}\notin\{s_0,\ldots,s_{n'-1}\}$である。したがって$n=n_0$であり、$s_{\mu'}=s_{n_0}$かつ$\mu'<n_0$であるから$\mu'=\mu$、$\lambda'=\lambda$である。

(2)を示す。任意の整数$i\ge\mu$に対して$s_{i+\lambda}=s_i$であることを、$i$についての帰納法で示す。$i=\mu$のときは(1)の等式である。$s_{i+\lambda}=s_i$ならば$s_{i+1+\lambda}=T(s_{i+\lambda})=T(s_i)=s_{i+1}$である。整数$j\ge0$に対し、$j<\mu$のとき$\rho(j):=j$と置き、$j\ge\mu$のとき$j-\mu$を$\lambda$で割った余りを$r$として$\rho(j):=\mu+r$と置く。$j\ge\mu$ならば、ある整数$t\ge0$に対して$j=\rho(j)+t\lambda$であり、上の等式を$t$回適用して$s_j=s_{\rho(j)}$を得る。$j<\mu$ならば$s_j=s_{\rho(j)}$は定義から成り立つ。$\rho(j)$と$\rho(k)$は$\{0,\ldots,\mu+\lambda-1\}$に属し、$s_0,\ldots,s_{\mu+\lambda-1}$は相異なるので、$s_j=s_k$は$\rho(j)=\rho(k)$と同値である。$j<\mu$ならば$\rho(j)<\mu$であり、$j\ge\mu$ならば$\rho(j)\ge\mu$であるから、$\rho(j)=\rho(k)$は、$j=k<\mu$であるか、$j,k\ge\mu$かつ$\lambda\mid j-k$であることと同値である。

(3)を示す。(2)の証明で示した等式により、状態列は$\mu$以降で周期$\lambda$をもつ。状態列が$\mu'$以降で周期$\lambda'$をもつとすると、$s_{\mu'+\lambda'}=s_{\mu'}$かつ$\mu'+\lambda'\ne\mu'$であるから、(2)により$\mu'\ge\mu$かつ$\lambda\mid\lambda'$である。$\lambda\mid\lambda'$から$\lambda\le\lambda'$であるので、$\lambda$は状態列の最小周期である。

(4)を示す。$T$が全単射であり、$\mu\ge1$であると仮定する。$T(s_{\mu-1+\lambda})=s_{\mu+\lambda}=s_\mu=T(s_{\mu-1})$であり、$T$は単射であるから、$s_{\mu-1+\lambda}=s_{\mu-1}$が成り立つ。他方、$\mu-1<\mu-1+\lambda\le\mu+\lambda-1$であり、$s_0,\ldots,s_{\mu+\lambda-1}$は相異なるから、$s_{\mu-1+\lambda}\ne s_{\mu-1}$である。この二つは両立しないので、$\mu=0$である。

(5)を示す。$j\ge\mu$ならば$z_{j+\lambda}=O(s_{j+\lambda})=O(s_j)=z_j$である。出力列の最小周期を$\lambda_z$とし、出力列が$\mu_z$以降で周期$\lambda_z$をもつとする。$\nu:=\max\{\mu,\mu_z\}$と置き、$\lambda=a\lambda_z+r$、$a\ge0$、$0\le r<\lambda_z$と表す。$j\ge\nu$ならば、$j+r\ge\mu_z$であるから周期$\lambda_z$を$a$回用いて$z_{j+r}=z_{j+r+a\lambda_z}=z_{j+\lambda}$であり、$j\ge\mu$であるから$z_{j+\lambda}=z_j$である。$r\ge1$ならば出力列は$\nu$以降で周期$r$をもち、$r<\lambda_z$は$\lambda_z$の最小性と両立しない。したがって$r=0$であり、$\lambda_z\mid\lambda$である。

(6)を示す。$s'_j:=T'^j(\varphi(s_0))$と置く。$\varphi(s_j)=s'_j$を$j$についての帰納法で示す。$j=0$のときは定義である。$\varphi(s_j)=s'_j$ならば$\varphi(s_{j+1})=\varphi(T(s_j))=T'(\varphi(s_j))=T'(s'_j)=s'_{j+1}$である。したがって$z'_j=O'(s'_j)=O'(\varphi(s_j))=O(s_j)=z_j$である。$S'=S$、$T'=T$、$O'=O$、$\varphi=\id_S$の場合が最後の主張である。▨

証明. 写像$\Phi\colon S\to Z^k$を$\Phi(s):=(O(s),O(T(s)),\ldots,O(T^{k-1}(s)))$で定める。$\Phi$の像は高々$|S|$個の元からなり、$|Z^k|=|Z|^k>|S|$であるから、$\Phi$の像に属さない$w=(w_0,\ldots,w_{k-1})\in Z^k$が存在する。$(Z_0,\ldots,Z_{k-1})=\Phi(\sigma)$であるから、$P(Z_0=w_0,\ldots,Z_{k-1}=w_{k-1})=0$である。他方、$Z_0,\ldots,Z_{k-1}$が相互独立であり、各$Z_j$が$Z$上の一様分布に従うならば、§E11.7 命題 1.2を一点集合$\{w_0\},\ldots,\{w_{k-1}\}$へ適用して、$P(Z_0=w_0,\ldots,Z_{k-1}=w_{k-1})=|Z|^{-k}>0$となる。この二つの値は両立しないので、主張が成り立つ。▨

証明.(1)を示す。$s\in U_m$ならば$\gcd(as,m)=1$であり、$T_a(s)\equiv as\pmod m$であるから$\gcd(T_a(s),m)=1$であり、$T_a(s)\in U_m$である。$d:=\operatorname{ord}_m(a)$と置く。$j$についての帰納法により$s_j\equiv a^js_0\pmod m$である。$0\le j<k$とする。$\gcd(a^js_0,m)=1$であるから$a^js_0$は法$m$の逆元をもち、$a^js_0\equiv a^ks_0\pmod m$は$a^{k-j}\equiv1\pmod m$と同値である。§A4.12 命題 1.2により、$a^{k-j}\equiv1\pmod m$は$d\mid k-j$と同値である。$s_j,s_k\in\{0,\ldots,m-1\}$であるから、$s_j=s_k$は$s_j\equiv s_k\pmod m$と同値であり、したがって$d\mid k-j$と同値である。よって$s_0,\ldots,s_{d-1}$は相異なり、$s_d=s_0$であるから、命題 1.2 (1)の組は$(0,d)$である。命題 1.2 (3)により、状態列は$0$以降で周期$d$をもつ純周期的な列であり、その最小周期は$d$である。

(2)を示す。$m$が素数ならば$\Z/m\Z$は位数$m$の体であり、§E8.7 定理 2.1により、その乗法群は位数$m-1$の巡回群である。その生成元を剰余類とする整数$a'$をとると、$\gcd(a',m)=1$であり、$a'^k\equiv1\pmod m$を満たす最小の正整数$k$は生成元の位数$m-1$に等しいので、$\operatorname{ord}_m(a')=m-1$である。$m$が素数ならば$U_m=\{1,\ldots,m-1\}$である。$\operatorname{ord}_m(a)=m-1$ならば、(1)により状態列は純周期的で最小周期は$m-1$であるから、命題 1.2 (3)により命題 1.2 (1)の組は$(0,m-1)$である。したがって$s_0,\ldots,s_{m-2}$は$U_m$の相異なる$m-1$個の元であり、$U_m$の各元をちょうど一度ずつとる。▨

証明.(1)を示す。$n$で割った余りが$j$である非負整数は、整数$t\ge0$による$j+tn$であり、$j+tn\le L-1$は$tn\le qn+(r-1-j)$と同値である。$j<r$ならば$0\le r-1-j<n$であるから、この不等式は$t\le q$と同値であり、元の個数は$q+1$である。$j\ge r$ならば$j\le n-1$から$-n\le r-1-j<0$であるから、この不等式は$t\le q-1$と同値であり、元の個数は$q$である。

(2)を示す。$P(R=j)$は$\{0,\ldots,M-1\}$のうち$n$で割った余りが$j$である元の個数を$M$で割った値であるから、(1)を$L=M$に適用して、確率の式を得る。$r=0$ならば任意の$j$に対して$P(R=j)=q/M=1/n$である。$r\ge1$ならば$n-1\ge r$であるから、$P(R=0)=(q+1)/M\ne q/M=P(R=n-1)$であり、$R$は一様分布に従わない。$r=0$は$n\mid 2^b$と同値であり、素因数分解の一意性により、$n\mid2^b$は$n=2^i$を満たす整数$0\le i\le b$が存在することと同値である。$n\le M$であるから、後者は$n$が$2$の冪であることと同値である。▨

証明.$B:=\{L,\ldots,M-1\}$と置き、$0\le j<n$に対して、$\{0,\ldots,L-1\}$のうち$n$で割った余りが$j$である元の集合を$C_j$と置く。$L=qn$であるから、命題 3.1 (1)により$|C_j|=q$である。整数$k\ge1$と$0\le j<n$に対して

と置く。相互独立性の定義により$X_1,\ldots,X_k$は相互独立であり、$B$と$C_j$は有限集合であるから Borel 集合である。§E11.7 命題 1.2により

である。

$n\le M$であるから$q\ge1$であり、$L\ge n\ge1$であるから$\theta>0$である。$0\le1-\theta<1$であるから、§E11.5 補題 1.1により

である。事象$A_{k,j}$$(k\ge1,\ 0\le j<n)$は互いに素であり、その和集合は$\Omega\setminus\Omega_\infty$である。実際、各$X_k$は$\{0,\ldots,L-1\}\cup B$に値をとり、$\{0,\ldots,L-1\}$は$C_0,\ldots,C_{n-1}$の互いに素な和集合であるから、$\omega\in\Omega\setminus\Omega_\infty$は$A_{N(\omega),Y(\omega)}$にだけ属し、$\Omega_\infty$の元はどの$A_{k,j}$にも属さない。したがって$P(\Omega\setminus\Omega_\infty)=1$であり、(2)が成り立つ。$\{N=k,\ Y=j\}$は、$(k,j)\ne(1,0)$ならば$A_{k,j}$に等しく、$(k,j)=(1,0)$ならば$A_{1,0}\cup\Omega_\infty$に等しい。よって$N$と$Y$は確率変数であり、$P(\Omega_\infty)=0$から$P(N=k,\ Y=j)=P(A_{k,j})$であるので、(1)が成り立つ。

(3)を示す。(1)と§E11.5 補題 1.1により、$0\le j<n$に対して

であり、$k\ge1$に対して$P(N=k)=n(1-\theta)^{k-1}q/M=\theta(1-\theta)^{k-1}$である。したがって$P(N=k,\ Y=j)=P(N=k)P(Y=j)$である。 Borel 集合$D_1,D_2\subset\R$に対し、$N$と$Y$は整数値であるから、確率の可算加法性により

であり、§E11.7 命題 1.2により$N$と$Y$は独立である。

(4)を示す。$M-L$は$M$を$n$で割った余りであるから$M-L<n\le qn=L$であり、$M<2L$から$\theta>1/2$である。$L\le M$から$\theta\le1$である。整数$i\ge0$に対して$P(N-1=i)=\theta(1-\theta)^i$であるから、$N-1$は$\operatorname{Geom}(\theta)$に従う。§E11.5 命題 1.5により$E[N-1]=(1-\theta)/\theta<\infty$であるから、非負確率変数$N-1$は可積分である。§E11.4 命題 1.2により$N=(N-1)+1$は可積分であり、

である。$\theta>1/2$から$E[N]<2$である。▨