3.3 ワイル変換による疑似乱数生成器に関する定理の証明
3.3.4 定理 10 の証明
を得ることができる.
補題7によれば,(68)も評価(69)を導く.すなわち,いずれの場合にも評価(69)を得る.
もはや定理13の証明は容易である.自明な評価
0max≤s≤l−1A(α(•),s) ≤ 1, と(69)から,結局
0max≤s≤l−1A(α(mn+r),s) ≤ 1− 1 2r+1
!
0max≤s≤l−1A(α(mn−1),s)
≤ 1− 1 2r+1
!2
0≤maxs≤l−1A(α(mn−2),s)
≤ · · · ·
≤ 1− 1 2r+1
!n
0≤maxs≤l−1A(α(m0),s)
≤ 1− 1 2r+1
!n
−→ 0, as n→ ∞. (70)
が得られる.これを補題7と合わせれば,(60)が分かる.
注意9 大雑把にいって,ほとんどすべてのαに対して{mn}∞n=0はほぼ「等差数列」であ ろうから,最後の評価(70)は,ほとんどすべてのαに対して収束(60)が指数的に早いこ とを意味している(定理100参照).
注意10 l ≥ 4に対して上の証明で述べたキャンセル(67)は非常に特殊なもので,展開 (62)においてはほかにも様々なキャンセルが起こっているのが普通である.ただし,l=2 のときは上の証明で述べたキャンセルが起こり得るすべてのキャンセルである.
群拡大による定式化
2次元トーラス上の関数 f を
f (x, α) := r1(x)r1(x+k1α)× · · · ×r1(x+kl−1α), (x, α)∈T2, (72) と定義する.ここでr1(x)はラデマッハ関数列の最初の関数である.このとき
Eh
X0(m)(•;α)Xk(m)
1 (•;α)× · · · ×Xk(m)
l−1(•;α)i
=
∫
T1
dx Ym
i=1
f (2i−1x,2i−1α) である.
3次元トーラス上の2進変換β:T3 →T3
β(x,y, α) := (2x,2y,2α) (73)
の群拡大(group extensionまたはskew product)を次のように定義する.
定義16 Ω:=T3× {−1,1}2,µをΩ上の一様確率測度,すなわち µ := P3⊗ δ−1+δ1
2 ⊗ δ−1+δ1
2 (74)
とする.変換Tf :Ω →Ωを
Tf(x,y, α, 1, 2) := (2x,2y,2α, 1f (x, α), 2f (y, α)) (75) で定義する.40
明らかにTf はµを保存する.T3の部分集合C を
C := {(x,y, α)|(x,y, α)は f (x, α)または f (y, α)の不連続点} (76) とすれば,明らかに C は測度 0 の β-不変集合である.T3 −C の各連結成分を Ej,j =
1, . . . ,J,とする.Ω ⊃Fjを次のようにとる.
{Fj}4Jj=1 := n
Ej× {−1} × {−1}oJ j=1
[ nEj× {−1} × {1}oJ j=1
[ nEj× {1} × {−1}oJ j=1
[ nEj× {1} × {1}oJ j=1
このとき,Ω = S4J
j=1Fj, µ-a.e.
定義17 (Ω, µ)上で定義された{1,2,3, . . . ,4J}-値確率過程{ζm}∞m=0を次で定義する.
ζm(x,y, α, 1, 2) = j :⇐⇒ Tmf (x,y, α, 1, 2)∈Fj.
40ここで紹介する群拡大の方法では安富のアイデア[32, 33]を参考にした.なお,先駆的仕事として高信 [28]では,T2× {−1,1}上の力学系T : (x, α, )7→(2x,2α, f (x, α))の強混合性を一様確率測度の下で示して いる.
補題9 {ζm}∞m=1は
p(i, j) := µ
T−f1(Fj) Fi
, i, j= 1, . . . ,4J, を推移確率行列とする既約で非周期的な定常マルコフ連鎖である.41
pm(i, j) := µ(ζm = j|ζ0 = i) とおく.すると,補題 9より直ちに次の系を得る(cf. [2]
Theorem 8.9).
系1 任意のi, j=1, . . . ,4Jに対して
pm(i, j) −→ µ(Fj), as m→ ∞, が成り立ち,しかもこの収束は指数関数的である.
補題9は後に示す.補題9によって定理100は以下のようにして示される.まず,次の 4つの写像を定義する.: i =1,2に対して
Φi :Ω→ {−1,1}, Φi(x,y, α, 1, 2) := i,
Φei :{1, . . . ,4J} → {−1,1}, eΦi( j) := Φi(Fj)=Fjのi-成分. このとき ∫
T1dx Ym
i=1
f (2i−1x,2i−1α)
=
∫
T1
dxΦ1(x,y, α, 1, 2)Φ1(Tmf (x,y, α, 1, 2))
=
∫
T1dxeΦ1(ζ0(x,y, α, 1, 2))eΦ1(ζm(x,y, α, 1, 2)) (77) と表される.なお,(77)の右辺はy, 2によらないことに注意せよ.次のような計算をする.
∫
T1
dα ∫
T1
dxeΦ1(ζ0(x,y, α, 1, 2))Φe1(ζm(x,y, α, 1, 2))
!2
=
∫
T1
dα ∫
T1
dxeΦ1(ζ0(x,y, α, 1, 2))eΦ1(ζm(x,y, α, 1, 2))
×
∫
T1
dyΦe2(ζ0(x,y, α, 1, 2))Φe2(ζm(x,y, α, 1, 2))
!
αを固定すれば,Φ1(ζm(x,y, α, 1, 2))とΦ2(ζm(x,y, α, 1, 2))は(x,y, 1, 2)に関する確率変 数と見て独立だから,上の値は
=
∫
T1dα ∫
T2dxdyΦe1(ζ0(x,y, α, 1, 2))Φe1(ζm(x,y, α, 1, 2))
×Φe2(ζ0(x,y, α, 1, 2))Φe2(ζm(x,y, α, 1, 2))
=
∫
Ω
dµeΦ3(ζ0(x,y, α, 1, 2))eΦ3(ζm(x,y, α, 1, 2))
= X
i,j
eΦ3(i)eΦ3( j)pm(i, j)µ(Fi),
41このとき,分割{Fj}jはマルコフ分割,力学系(Ω,Tf)はマルコフ変換という.なお,マルコフ連鎖に関 する用語(既約(irreducible),非周期的(aperiodic),定常(stationary))などは,たとえば[2] Section 8を見よ.
ここで,Φe3 :=Φe1×Φe2とおいた.系1によれば,m→ ∞のとき X
i,j
eΦ3(i)eΦ3( j)pm(i, j)µ(Fi) −→ X
i,j
Φe3(i)eΦ3( j)µ(Fj)µ(Fi) =
X
i
Φe3(i)µ(Fi)
2
= ∫
Ω12dµ
!2
= 0 であり,この収束は指数関数的である.よって
X∞ m=1
∫
T1
dα ∫
T1
dxΦe1(ζ0(x,y, α, 1, 2))Φe1(ζm(x,y, α, 1, 2))
!2
(78)
= X∞
m=1
X
i,j
eΦ3(i)Φe3( j)pm(i, j)µ(Fi) < ∞
だが,(78)の各項が指数減衰であることから,ある0< ρ1< 1が存在して,
X∞ m=1
ρ−1m
∫
T1
dα ∫
T1
dxΦe1(ζ0(x,y, α, 1, 2))eΦ1(ζm(x,y, α, 1, 2))
!2
< ∞. (79)
従って
∫
T1
dαX∞
m=1
ρm/21
∫
T1
dxeΦ1(ζ0(x,y, α, 1, 2))eΦ1(ζm(x,y, α, 1, 2))
!2
< ∞.
よって ρ−1m/2
∫
T1dxeΦ1(ζ0(x,y, α, 1, 2))Φe1(ζm(x,y, α, 1, 2)) → 0, as m→ ∞, a.e.α. (80) このことは,ほとんどすべてのαに対して一様な指数減衰の評価(71)ができることを示す.
マルコフ性の証明
補題9の証明を考えよう.Tf がµを保存するので{ζm}mの定常性は明らかである.定 常性より,
µ(ζm= j|ζm−1= i) = p(i, j), i, j=1, . . . ,4J, m∈N.
以下の証明では
T−fm:= (Tmf )−1, β−m:=(βm)−1 (81) と略記する.
補題10 T−fmFj,j = 1, . . . ,4J,の連結集合全体のなすΩの分割を ∆−m とする.このと
き,m0 < mならば∆−mは∆−m0 の細分,すなわち,任意の A∈∆−m,A0 ∈∆−m0 に対して,
A⊂ A0 またはA∩A0 = ∅のどちらか一方が成り立つ.
証明. ˜C := ∪1,2=−1,1C × {1} × {2}とおく.C˜ は Tf-不変集合,すなわち,TfC˜ ⊂ C˜ であ る.もし A ∈ ∆−m が A0, B0 ∈ ∆−m0 (B0 , A0)に対して A∩A0 , ∅ かつA∩B0 , ∅ならば A∩C˜−m0 , ∅となる.この両辺にTmf を作用させれば,Tmf C˜−m0 =Tmf −m0C˜ ⊂C˜ によって
Tmf A∩C˜ ⊃ Tmf A∩TmfC˜−m0 ⊃Tmf (A∩C˜−m0),∅.
しかし,Tmf(A)はあるFj に他ならないので,これは矛盾である.
それでは{ζm}∞m=0のマルコフ性を証明しよう.µ(ζ0= i0, . . . , ζm−1= im−1)>0を仮定する.
µ(ζm = j|ζ0 =i0, . . . , ζm−1= im−1)
=µ
T−fmFj Fi0 ∩T−f1Fi1 ∩ · · · ∩T−fm+1Fim−1
= µ
Fi0 ∩T−f1Fi1 ∩ · · · ∩T−fm+1Fim−1 ∩T−fmFim µ
Fi0 ∩T−f1Fi1 ∩ · · · ∩T−fm+1Fim−1
= µ
Fi0 ∩T−f1Fi1 ∩ · · · ∩T−fm+1
Fim−1 ∩T−f1Fim
µ
Fi0 ∩T−f1Fi1 ∩ · · · ∩T−fm+1Fim−1
.
T−fm+1Fim−1 は8m−1 個の同測度の連結成分よりなり,補題10によれば,そのうちのいくつ か,l個としよう,がF := Fi0∩T−f1Fi1 ∩ · · · ∩T−fm+2Fm−2にすっぽり含まれ,他の8m−1−l 個はFと共通部分を持たない.この事情はT−fm+1
Fim−1 ∩T−f1Fim
でも同様である.従って
µ
F∩T−fm+1
Fim−1 ∩T−f1Fim
= l 8m−1µ
T−fm+1
Fim−1 ∩T−f1Fim , µ
F∩T−fm+1Fim−1
= l 8m−1µ
T−fm+1Fim−1 . これより,Tf のµ-不変性を用いて
µ(ζm= j|ζ0 =i0, . . . , ζm−1 =im−1) = µ
T−fm+1
Fim−1 ∩T−f1Fim µ
T−m+1f Fim−1
= µ
Fim−1 ∩T−1f Fim µ(Fim−1)
= µ(ζm= j|ζm−1= im−1)
が従い,{ζm}mのマルコフ性が分かる.
エルゴード性の証明
{ζm}mの既約性はTf のエルゴード性から従う.次の補題から始めよう.
補題11 φi :T3→C, i=1,2,は可測関数で
φ1(x,y, α) = φ1(2x,2y,2α) f (x, α), a.e. (82) φ2(x,y, α) = φ2(2x,2y,2α) f (x, α) f (y, α), a.e. (83) を満たすとする.このとき,φ1 =φ2 =0,a.e. である.
証明. 以下i =1,2とする.まず,f は0点を持たないことより,φi(x,y, α)の0点集合は φi(2x,2y,2α)の0点集合と一致するので,それは2進変換βに関して不変,従ってその測 度はエルゴード性によって0か1である.その測度が1なら証明終わり.それでφi , 0,
a.e.,と仮定しよう.さらに,φiの実部または虚部の符合がやはり同じ関係式を満たすか
ら,はじめから,φi ∈ {−1,1}としてよい.
次の領域A⊂ T3 に注目する.
A :=
(x,y, α)
12 < x<1, 12 < x+nk−2α <1, 1< x+nk−1α < 32,
1
2 < y<1, 12 < y+nk−1α <1
. (84)
容易に分かるように,Aは空集合でない開集合である.(x,y, α)∈Aならば r1(x) = r1(x+n1α) = · · · = r1(x+nk−2α) = −1, r1(x+nk−1α) = 1, r1(y) = r1(y+n1α) = · · · = r1(y+nk−1α) = −1,
だから,kが偶数であることと関数 f の定義(72)より
f (x, α) = −1, f (y, α)=1, (x,y, α)∈A, (85) が分かる.(81)の略記法を思い出しておこう.
β−mA := {(x,y, α)∈T3|βm(x,y, α)∈A}.
β−1Aの各連結成分はAに相似であるが,とくに B(0−1) :=
(x,y, α)
34 < x<1, 34 < x+nk−2α <1, 1< x+nk−1α < 54,
3
4 <y<1, 34 < y+nk−1α <1
. はAの部分集合である.従って(85)よりB(0−1)上で f (x, α)= −1, f (y, α)=1である.
さて,与えられた関係式(82)(83)より
φi(x,y, α)φi(2x,2y,2α)= −1, (x,y, α)∈B(0−1), (86) である.もし,A上でφi(x,y, α)≡ 1,a.e. ならば,B(0−1)上でφi(2x,2y,2α)≡1,a.e.である から,(86)と矛盾する.だから,A上でφi . 1.同様にA上でφi(x). −1.従ってとくに
1
|A|
∫
A
φi(x,y, α)dxdydα =: ai ∈ (−1,1) (87) である.ここに|A|は Aのルベーグ測度.
次に各mにつき,β−mAの任意の連結成分B(−m)上で f は一定符号であることに注意し よう.これは補題10と同様に示せる.実際,f (x, α)と f (y, α)の不連続点全体Cは2進変 換βに関して不変なので,もし,f (x, α)あるいは f (y, α)が B(−m)上で符合を変えるなら ば,D := B(−m)∩C, ∅である.これにβmを作用させれば,βmD⊂ AかつβmD⊂ βmC =C となり,これは A∩C = ∅,すなわち,f (x, α)あるいは f (y, α)がAで符合を変えること を意味するから,矛盾である.
従って,各mにつき,β−mAの任意の連結成分 B(−m)上で,(82)(83)より
φi(x,y, α)φi(2x,2y,2α) ≡ 1 または φi(x,y, α)φi(2x,2y,2α) ≡ −1. (88) そこで
B(1−m)∫
B(−m)
φi(x,y, α)dxdydα = ±ai (89) であることを帰納法で示そう.
まず,m=1のときは(88)と変数変換 x0 =2x, y0 = 2y, α0= 2αによって,
∫
B(−1)
φi(x,y, α)dxdydα = ±
∫
B(−1)
φi(2x,2y,2α)dx = ±1 8
∫
A
φi(x0,y0, α0)dx0dy0dα0 (90) である.|B(−1)|= 18|A|だから
B(1−1)∫
B(−1)
φi(x,y, α)dxdydα = ±ai. (91) m−1まで(89)が正しい仮定してmのときは(88)より(90)のようにして
∫
B(−m)
φi(x,y, α)dxdydα= ±
∫
B(−m)
φi(2x,2y,2α)dxdydα= ±1 8
∫
βB(−m)
φi(x,y, α)dxdydα.
ここで,βB(−m) はβ−m+1Aの連結成分の一つ( B(−m+1) としよう)である.やはり|B(−m)| =
1
8|B(−m+1)|だから B(1−m)∫
B(−m)
φi(x,y, α)dxdydα = ± 1 B(−m+1)∫
B(−m+1)
φi(x,y, α)dxdydα.
従って,帰納法の仮定によりmの場合も(89)が成り立つ.
さて,集合 ∪∞m=1β−mA はT3 で稠密であり,一辺が 0 < ρ < 1 の任意の立方体は m = b−log2ρc+1として,β−mAの少なくとも一つの連結成分を含む.従って,あるδ > 0が 存在し,任意の立方体Sに対して
−1+δ < 1
|S|
∫
S
φi(x,y, α)dxdydα < 1−δ. (92) 一方,φi は {−1,1}-値可測関数だからルベーグの密度定理によれば,S(x,y, α;ρ) を一辺
ρ >0の(x,y, α)を中心とする立方体とするとき
limρ→0
1
|S(x,y, α;ρ)|
∫
S(x,y,α;ρ)φi(x0,y0, α0)dx0dy0dα0 = −1または1, a.e.(x,y, α)∈T3. これは(92)と矛盾する.すなわち,(82)(83)を満たす可測関数φi は0以外に存在しない
ことが分かる.
それでは,補題9の証明のためにTf のエルゴード性を示そう.可測関数φ:Ω = T3× {−1,1}2→ CがTf-不変,すなわち
φ(x,y, α, 1, 2)=φ(2x,2y,2α, 1f (x, α), 2f (y, α)), µ-a.e.,
ならば,φ≡定数µ-a.e. であることを示す.
ψ1(x,y, α) := P
1,2φ(x,y, α, 1, 2)とすれば ψ1(x,y, α) = X
1,2
φ(2x,2y,2α, 1f (x, α), 2f (y, α))
= X
1,2
φ(2x,2y,2α, 1, 2)
= ψ1(2x,2y,2α)
であるから,2進変換βのエルゴード性より,ψ1 ≡c= 定数,a.e. となる.φの代わりに φ−c/4とすれば,ψ1 ≡0, a.e.とできるので,そのように仮定する.
ψ2(x,y, α, 1) :=P
2φ(x,y, α, 1, 2)とおけば ψ2(x,y, α, 1) = X
2
φ(2x,2y,2α, 1f (x, α), 2f (y, α))
= X
2
φ(2x,2y,2α, 1f (x, α), 2)
= ψ2(2x,2y,2α, 1f (x, α)) であるから
ψ2(x,y, α,−1) = ψ2(2x,2y,2α,−f (x, α))
= ψ2(2x,2y,2α,−1)δ1( f (x, α))+ψ2(2x,2y,2α,1)δ−1( f (x, α)) φ2(2x,2y,2α,−1)+φ2(2x,2y,2α,1)= ψ1(x,y, α)≡0だったから
ψ2(x,y, α,−1) = ψ2(2x,2y,2α,−1) (δ1( f (x, α))−δ−1( f (x, α)))
= ψ2(2x,2y,2α,−1) f (x, α).
補題11より,ψ2(x,y, α,−1) ≡ 0, a.e. が分かる.これより,ψ2(x,y, α,1) ≡ 0, a.e. だから,
結局,ψ2(x,y, α, 1)≡ 0, a.e.(x,y, α, 1)である.従って
φ(x,y, α, 1,−1)+φ(x,y, α, 1,1)=ψ2 ≡0 であるから
φ(x,y, α, 1, 2)=φ(x,y, α, 1,1)2
と書ける.いま,1と2の役割を入れ替えれば同じ議論により φ(x,y, α, 1, 2)=φ(x,y, α,1, 2)1
この二つの式より,直ちに
φ(x,y, α, 1, 2)= φ(x,y, α,1,1)12. 従って,φがTf 不変であることは
φ(x,y, α,1,1)= φ(2x,2y,2α,1,1) f (x, α) f (y, α)
を意味するが,補題11により,これを満たすφは0しかない.これで,Tf のエルゴード 性,従って{ζm}mの既約性の証明が完了した.
非周期性の証明
補題9の証明は残るところ非周期性の証明であるが,すでに既約性は示したので,µ(ζ0 = ζ1)> 0であればよい.それには
F0:=
(x,y, α)
0< x< 12, 0< x+nk−1α < 12, 0<y< 12, 0< y+nk−1α < 12
, F00 :=
(x,y, α)
0< x< 14, 0< x+nk−1α < 14, 0<y< 14, 0< y+nk−1α < 14
,
として,F := F0×{1}×{1} ⊂Ωとすれば,これはΩの分割{Fj}4Jj=1に属する一つの集合Fjで ある.H := F00×{1}×{1}とおけばH⊂ Fであり,(x,y, α)∈F00ならば f (x, α)= f (y, α)=1 なので,(x,y, α, 1, 2)∈Hならば
ζ0(x,y, α, 1, 2)=ζ1(x,y, α, 1, 2)= j である.µ(H)>0だから,{ζm}mの非周期性がいえた.
これで,補題9の証明,従って定理100(定理10)の証明が完了した.