4.3 模倣可能な確率変数
4.3.2 停止時刻に関して可測な確率変数
あるm∈Nに対してBm-可測であるような確率変数は明らかに模倣可能である．47一方，
どのようなmに対してもBm-可測とならないようなB-可測関数(無限精度関数と呼ぼう) でも，場合によっては実際的な計算の上で扱うことが可能である．次の例を見よ．
46無限個の変数を持つ関数を汎関数という．ここではW(x)が 無限個の値di(x)，i=1,2, . . .の関数と見な せる，ということ．
47もちろん，mが天文学的に巨大だと現実のコンピュータでは扱うことができなくなる．ここでいう模倣 可能性は，あるチューリング機械で計算できる，という意味である．
例10 (到達時刻) ルベーグ確率空間上で定義された確率変数
σ(x) := inf{n≥1|d1(x)+d2(x)+· · ·+dn(x)=5}, x∈T1,
は硬貨を投げ続けて，表の出た回数が5となる最初の時刻である(ただし，inf∅=∞と解 釈する). 明らかに σは非有界な無限精度関数である．しかし，表が出た回数が5になっ た時点でその後のdi(x)の値は不要だから直ちに計算を終えてσ(x)を算出することができ る．すなわち，確率1でσ(x)の計算は有限時間で終わる．
例10を含むような，モンテカルロ法で実際に扱い得る無限精度関数の一般的なクラス を考えよう．
定義20 関数τ:T1 →N∪ {∞}は
{τ≤m} := {x∈T1|τ(x)≤ m} ∈ Bm, ∀m∈N.
を満たすとき，{Bm}m-停止時刻(cf. [2])という．{Bm}m-停止時刻τに対して，Bの部分σ -加法族Bτを
Bτ := {A∈ B |A∩ {τ≤ m} ∈ Bm, ∀m∈N}
で定義する．Bτ-可測関数を以下簡単のためτ-可測な関数という．また，Lp(T1,Bτ,P)を単 にLp(Bτ)と書く．
補題13 関数 f :T1 →R∪ {±∞}がτ-可測な関数であるための必要十分条件は
f (x) = f bxcτ(x), x∈T1, (114) となることである．
証明. 必要性：もし f がτ-可測ならば，各m∈N，t∈Rに対して，{τ≤mかつ f ≤t} ∈ Bm
である．このことからτ(x)≤ mならば f (x) = f (bxcm)が分かる．従って f (x) =
X∞ m=1
f (x)1{τ(•)=m}(x)+ f (x)1{τ(•)=∞}(x)
= X∞ m=1
f (bxcm) 1{τ(•)=m}(x)+ f (bxc∞) 1{τ(•)=∞}(x)
= X∞ m=1
f bxcτ(x)
1{τ(•)=m}(x)+ f bxcτ(x)
1{τ(•)=∞}(x)
= f bxcτ(x)
X∞
m=1
1{τ(•)=m}(x)+ f bxcτ(x)
1{τ(•)=∞}(x) = f bxcτ(x)
.
十分性：もし f が(114)を満たせば，各m∈N，t∈Rに対して {f ≤ t} ∩ {τ≤m} = {f b•cτ(•)
≤t} ∩ {τ≤ m} = {f (b•cm)≤ t} ∩ {τ≤m} ∈ Bm
だから，f はτ-可側である．
例10の確率変数σは{Bm}m-停止時刻であり，もちろん，σはσ-可測である．
定理21 τを確率1で有限な{Bm}m-停止時刻とするとき，任意のτ-可測な f はモンテカ ルロ法で扱うことができる．48
証明. 硬貨投げの確率過程 {di(x)}∞i=1 は d1(x),d2(x), . . . の順で供給されるとする．f が
{Bm}m-停止時刻τに関して可測のとき，次のようなアルゴリズムを考える:
1. m=1とする．
2. t := Pm
i=12−idi(x) (= bxcm)とする．
3. もしτ(t) ≤mならば，f (t)を出力し，終了する．
4. もしτ(t) >mならばm :=m+1として2. に戻る．
τが確率1で有限なので上のアルゴリズムは必ず有限時間内に終了し，そのときの出力は
f (x)である．
さて，モンテカルロ法ではランダム源をT1-値一様分布に従うi.i.d.確率変数列{Zl}l∈Nと して議論することが多い．その文脈で停止時間に関する可測性は次のような仮定として述 べることができる．
仮定1 W を計算するためには確率1で，有限個のZ1, . . . ,ZLしか必要でない，と仮定す る．ここで，Zl たちの個数Lは確率変数であるが，各l ∈Nに対して，Z1, . . . ,Zl が与え られたとき，次のZl+1がWを計算するために必要かどうかが，Zl0, l0 ≥ l+1，に関して何 の知識がなくても，判断できなければならない．
仮定1が成り立たなければ，W を計算するためにZl たちを永遠に生成し続ける事態が生 じるから，この仮定は，確率変数をモンテカルロ法で扱うためには不可欠であることが分 かる．
実際には実数計算が有限精度，たとえば2−K，で行われることを考慮に入れて，{Zl}l∈N
の代わりにDK-値一様分布に従うi.i.d. {Zl(K)}l∈Nを(T1,B,P)上で Zn(K) :=
XK i=1
2−id(n−1)K+i, n∈N, (115) すなわち
Z1(K) = 1
2d1+ 1
22d2+· · ·+ 1 2KdK Z2(K) = 1
2dK+1+ 1
22dK+2+· · ·+ 1 2Kd2K Z3(K) = 1
2d2K+1+ 1
22d2K+2+· · ·+ 1 2Kd3K ...
48詳しくは，硬貨投げの確率過程を入力とし f を計算するチューリング機械が存在する，ということ．
のように実現する．そして，W が仮定1を満たすとき
τ(x) := inf{lK|W(x)はZ1(K)(x), . . . ,Zl(K)(x)から計算される} とおけば，τは{Bm}m-停止時刻であり，Wはτ-可測となる．49
例11 Wが常に一定の個数のZl たちから計算される場合，すなわちLが定数の場合は，
W は有限精度であり明らかに仮定1を満たす．
次の例のように，停止時刻τは実際の数値計算においては，多くの場合，あからさまに 意識する必要がない．
例12 (フォン・ノイマンの棄却法 [16]) [0,1)-値一様分布に従う独立な確率変数列{Zl}∞l=1 が与えられたとき，[a,b]上で有界可測なある確率密度関数p(x)の分布に従う確率変数W を生成したいとせよ．M> 0を pの上界の一つとする．(ξ, η)を[a,b]×[0,M]で一様に分 布する確率変数とするとき，
Pr(ξ ∈[x,x+dx)|p(ξ)≥ η) = p(x)dx, a.e.-x, であることに注意する．そこで，次のようなアルゴリズムを考える．
1. l :=1とする．
2. (ξ, η) :=((b−a)Z2l−1+a,MZ2l)とする．
3. もしp(ξ)≥ ηならば，W := ξとして，これを出力する．
4. もしp(ξ)< ηならばl := l+1として2. に戻る．
このアルゴリズムで得られる確率変数W の分布は望みのものになっている．このときW は仮定1を満たしている．
例13 (例10の言い換え) {Yn}∞n=1を Yn :=
0, if Zn ∈[0,1/2)
1, if Zn ∈[1/2,1) n=1,2, . . . , とする．{Yn}∞n=1は硬貨投げの確率過程である．このとき
W := inf{n≥1|Y1+Y2+· · ·+Yn= 5}
とすればW は仮定1を満たす．W は硬貨を投げ続けて，表の出た回数が5となる最初の 時刻である．
49従って定理21の逆も成り立つ．