数理統計学 I 前期
ランダムウォークと投票者モデル
(Random Walks and Voter models)
担当 平場 誠示
平成 12 年 4月 18 日〜 (火 1-2 限実施)
はじめに (Preface)
数理統計学の目的は，観察によって得られるランダムな現象のデータから,もとの現象をなるべ く正確に推定することにある．そのための手法について解説するのが通常の数理統計学であるが, 現実には, 調べる対象に応じた, 確率モデルに対する数学的結果が必要となる. そこで本講演では ランダムウォークと投票者モデルと呼ばれる単純な確率過程について得られる数学的結果について 解説する.
普通,確率論関係の話をするときには「測度論」「ルベーグ積分論」の知識を必要とするが,本講 義ではそれを表に出さずに, 直感的に理解できるよう工夫したつもりである. 但し,証明の都合上, どうしても「積分論」の知識を必要とする事柄に関しては補章に述べた.
(測度論,ルベーグ積分論について勉強したい人は講義ノート「ルベーグ積分論」を参照して欲し
い. 確率論の基礎の基礎についても触れてある.)
目 次
1 ランダムウォーク (Random Walks) 1
1.1 マルコフ連鎖(Markov Chains) . . . . 1 1.2 d次元ランダムウォーク(d-dimensional Random Walks). . . . 7 1.3 1次元非対称ランダムウォーク
(One-dimensional anti-symmetric Random Walks) . . . . 14
2 投票者モデル (Voter Models) 20
2.1 投票者モデル(Voter Models) . . . . 20 2.2 出会い確率(Rendezvous Probability) . . . . 20 2.3 格子構造と放射状構造での結果 . . . . 21
3 補章 23
3.1 マルコフ連鎖の正再帰性の判定定理(定理1.2(iii))の証明 . . . . 23 3.2 条件[AP]のもとq0,0(n)の n→ ∞での漸近挙動の結果(定理1.6)の証明 . . . . . 24 3.3 大数の法則について . . . . 26
1 ランダムウォーク (Random Walks)
ランダムウォークは日本語で「酔歩」というが,確率過程の中でも,最も単純なモデルで様々な 性質が研究されている. 本講義では「酔っ払いは果たして家に帰り着くことができるか？」,即ち,
「ランダムウォークは再帰的か？」という問題について議論する.
1.1 マルコフ連鎖 (Markov Chains)
確率過程とは時間とともにランダムに変化・運動していく対象を指すが,まずはランダムウォー クよりは少し,一般的な「マルコフ連鎖」と呼ばれる確率過程について解説する. 本節では次の結 果を紹介する.
定理1.1 可算集合S に値をとる既約で時間的一様なマルコフ連鎖は正再帰的か,零再帰的 か,過渡的のいずれかの状態になる.
さて数学が一般に嫌われるのは,「同じ日本語なのに聞いていて, チンプンカンプンで理解不能 だから」と良く言われるが,初めて聞く人にとってはこれがまさにそうだろう. 原因は単純で,それ は数学用語の定義が分っていないからである.
「既約」「時間的一様」「マルコフ連鎖」「正再帰的」「零再帰的」「過渡的」
マルコフ連鎖とは,次にどう動くかが,現在の状況のみに依存して,過去には無関係であるような ものをいうが, いい加減な表現をすれば「行き当りばったりプロセス」あるいは「その場しのぎプ ロセス」といっても良いだろう. 正確な定義は次のとおりである.
S を有限または可算無限集合として, S に値をとる確率過程(Xn, P) = (Xn(ω), P(dω)) (n= 0,1,2, . . .)が次をみたすときマルコフ連鎖 (Markov Chain)という:
(M1) [マルコフ性] n≥1, j0, j1, . . . , jn, k∈S に対し,
P(Xn+1=k|X0=j0, X1=j1, . . . , Xn=jn) =P(Xn+1=k|Xn=jn).
さらに次の性質をみたすとき時間的一様なマルコフ連鎖という. (M2) [時間的一様性] n≥1, j, k∈S に対し,
P(Xn+1=k|Xn=j) =P(X1=k|X0=j).
注意1.1 条件付確率 P(A|B) =P(A∩B)/P(B)は P(B)>0 のとき定義されるので上 の条件はそれも仮定に含まれているとみなす.
本講義では時間的一様でないものは扱わないので以下ではマルコフ連鎖といったときは全て,時 間的一様なマルコフ連鎖を指すものとする.
X0 の分布 µ={µj}; µj =P(X0=j)を初期分布 (initial distribution) といい, 特に,ある j ∈Sに対し,P(X0=j) = 1のとき確率P をPj で表し, (Xn, Pj)をj を出発するマルコフ連鎖 という. (これはP(X0=j)>0のとき,Pj(·) :=P(· |X0=j)で定義するというのと同じことで, 実際に計算するときはこちらの方が都合が良い.)
注意1.2 Pj は次で定義されるという言い方もできる(最後の等号は時間的一様性による):
Pj(X1=k1, . . . , Xn =kn) := P(X1=k1, . . . , Xn =kn|X0=j)
= P(Xm+1=k1, . . . , Xm+n=kn|Xm=j) (m≥0).
n≥0, j, k∈S に対し, q(n)j,k =P(Xn =k|X0=j)とおき,Q(n)= (q(n)j,k)をn 階推移確率(行 列) (n-step transition probability (transition matrix)), 特に, Q(1) を Q= (qj,k) で表し, 単に,推移確率(行列)という.
問 1.1 次を示せ. (i)q(n)j,k ≥0,P
kq(n)j,k = 1 (j∈S), (ii)n≥1,j0, j1, . . . , jn ∈S に対して
P(X0=j0, X1=j1, . . . , Xn =jn) =µj0qj0,j1· · ·qjn−1,jn, (iii)m, n≥1,j1, . . . , jm, k0, k1, . . . , kn ∈S に対して
P(Xn+1=j1, . . . , Xn+m=jm|X0=k0, X1=k1, . . . , Xn=kn) =qkn,j1qj1,j2· · ·qjm−1,jm. (iv)Q(0)=I:= (δjk) (単位行列),Q(n)=Qn (n≥1),但し,δjk= 1 (j=k), = 0 (j6=k).
問 1.2 初期分布を µ={µj} とするときXn の分布が次で与えられることを示せ.
P(Xn=k) =X
j∈S
µjq(n)j,k.
今,j∈S への再帰時間 (recurrence time): Tj を次で定義する: Tj= inf{n≥1;Xn=j} (=∞ if{·}=∅).
• j が再帰的 (recurrent) ⇐⇒def Pj(Tj <∞) = 1,
• j が過渡的 (transient) ⇐⇒def Pj(Tj <∞)<1
と定義する. またj が再帰的のとき, Tj は有限な整数値となるが,さらに
• j が正再帰的(positive-recurrent) ⇐⇒def Ej[Tj]<∞,
• j が零再帰的(null-recurrent) ⇐⇒def Ej[Tj] =∞,Pj(Tj <∞) = 1 と定義する. ここでEj[Tj]はTj の Pj のもとでの平均で, 次で定義される:
Ej[Tj] = X∞ m=1
mPj(Tj=m) +∞·Pj(Tj =∞).
全てのj が再帰的(or正再帰的,零再帰的,過渡的)なら(Xn)は再帰的(or正再帰的,零再帰的, 過渡的)であるという.
問 1.3 正再帰的なら再帰的であることを示せ.
マルコフ連鎖{Xn}あるいは推移確率 Q= (qj,k)とある確率分布π={πj} に対して
• πが定常分布 (stationary distribution) ⇐⇒def πk=P
jπjqj,k (k∈S),
• πが可逆分布 (reversible distribution) ⇐⇒def πkqk,j =πjqj,k (j, k∈S) と定義する.
問 1.4 可逆分布は定常分布であることを示せ.
問 1.5 次を示せ.
(i)初期分布 πが定常分布なら,全てのn≥1 に対し,Xn の分布も πとなる.
(ii) 初期分布 π が可逆分布なら, {Xn} は時間反転性をもつ: 任意の n≥1, j0, . . . , jn ∈ S に 対し,
P(X0=j0, . . . , Xn=jn) =P(X0=jn, . . . , Xn=j0).
マルコフ連鎖{Xn} あるいは推移確率Q= (qj,k)が既約(irreducible)であるとは任意のj, k に対し,あるn≥1が存在し,q(n)j,k >0をみたすときをいう. つまり,どこから出発しても何ステッ プかで,どこへでもいける可能性があるということである. (もう少し分りやすくいうと, トラップ と通過するだけの点,絶対に行けない点がないということである.)
次の事実が時間的一様なマルコフ連鎖に対する,本節のメインの結果である:
定理1.2 j, k∈S とする.
(i)j が再帰的という条件は次のそれぞれと同値: a)
X∞ n=0
q(n)j,j =∞.
b) Pj({Xn}は j に無限回戻る ) = 1.
(ii) j が過渡的という条件は次のそれぞれと同値: a)
X∞ n=0
q(n)j,j <∞.
b) Pj({Xn}は j に無限回戻る ) = 0.
(iii) {Xn} が既約なマルコフ連鎖なら,再帰的か,過渡的かのどちらかになるが,もっと詳しく
正再帰的,零再帰的,過渡的のいずれかになる. さらに正再帰的となるための必要十分条件は定常 分布(πj) [∀k,P
jπjqj,k=πk]が存在することで,このときπj= 1/Ej[Tj] で与えられる(従って 定常分布は存在すれば一意にきまる).
まず(i), (ii) の b)について述べ, それから a) の判定定理, (iii) の前半について証明を与える.
(iii)の正再帰性の判定定理の証明は最後の補章で述べる.
命題1.1 (i) j∈S が再帰的なら Pj({Xn} は j に無限回戻る ) = 1.
(ii)j∈S が過渡的ならPj({Xn} は j に無限回戻る) = 0.
証明 直感的には理解できるであろう. 再帰的な場合は, 有限時間で戻る確率が1 だから, 1 回 目に戻ったときから考えれば, 再び有限時間で戻るからそれを繰り返せばよい. 過渡的な場合は戻 る確率が1より小さいからそれを繰り返していけば,確率は0 に近づく.
m回目にj に戻る時間をTj(m) とおく.
Tj(1)=Tj, Tj(m)= min{n > Tj(m−1);Xn=j} (=∞ if{·}=∅).
まずPj(Tj(m)<∞) =Pj(Tj<∞)m を示す. 自然数s, tに対し,マルコフ性と時間的一様性を用 いて,
Pj(Tj(m)=s+t|Tj(m−1)=s) =Pj(Tj =t) が示せて
Pj(Tj(m−1)=s, Tj(m)=s+t) =Pj(Tj(m−1)=s)Pj(Tj=t) をえる. よって
Pj(Tj(m)<∞) = Pj(Tj(m−1)< Tj(m)<∞)
= X∞ s=m−1
X∞ t=1
Pj(Tj(m−1)=s, Tj(m)=s+t)
= Pj(Tj(m−1)<∞)Pj(Tj <∞) より,Pj(Tj(m)<∞) =Pj(Tj<∞)mが分かる. これより
Pj({Xn}はjに無限回戻る) = Pj(\
m
{Tj(m)<∞})
= lim
m→∞Pj(Tj(m)<∞)
= lim
m→∞Pj(Tj <∞)m. これはPj(Tj<∞) = 1なら1,そうでないなら0である.
[実際の講義では,以下1.1 節の終わりまでを次節1.2の問1.12の後に.]
再帰的,過渡的の判定定理の証明のためにまずいくつか記号を定義する. j, k∈Sに対し,fj,k(m):=
Pj(Tk=m) (m≥1)とおき Qjk(s) :=
X∞ n=0
q(n)j,ksn (|s|<1), Fjk(s) :=
X∞ m=1
fj,k(m)sn (|s|≤1) とおく. それぞれ{qj,k(n)}n≥0,{fj,k(m)}m≥1の母関数(generating functions) という. Fjk(1) =Pj(Tk <∞)に注意せよ.
補題1.1 j, k∈S に対し,次が成り立つ: q(n)j,k =
Xn m=1
fj,k(m)qk,kn−m (n≥1), Qjk(s) =δjk+Fjk(s)Qkk(s) (|s|<1).
証明 {Tk=m}={Xm=k, Xs6=k(1≤s≤m−1)} に注意して Xn
m=1
fj,k(m)q(nk,k−m) = Xn m=1
Pj(Tk=m)Pj(Xn=k|Xm=k)
= Xn m=1
Pj(Tk=m)Pj(Xn=k|Tk =m)
= Xn m=1
Pj(Xn =k, Tk=m)
= Pj(Xn=k)
= q(n)j,k.
またこれを用いて
Qjk(s) = δjk+ X∞ n=1
qj,k(n)sn
= δjk+ X∞ n=1
Xn m=1
fj,k(m)qk,k(n−m)sn
= δjk+Fjk(s)Qkk(s).
命題1.2 j ∈S が再帰状態 ⇐⇒
X∞ n=0
qj,j(n)=∞.
証明 上の補題よりQjj(s)(1−Fjj(s)) = 1 (|s|<1)が成り立つからFjj(1) =Pj(Tj <∞)と lims↑1Qjj(s) =
X∞ n=0
q(n)j,j ≤ ∞ に注意してs↑1 とすれば分かる. 形式的に次のように表せる:
X∞ n=0
qj,j(n)(1−Pj(Tj <∞)) = 1.
問 1.6 上の証明を参考にj 6=kのときを考えることにより
j∈S 過渡的 ⇒ X
n=0
qk,j(n)<∞(∀k∈S) が分かり,逆に
∃k∈S; X
n=0
q(n)k,j =∞ ⇒ j: 再帰的 となることを示せ. (P
nqk,j(n)=Fkj(1)P
nqj,j(n).)
補題1.2 j が再帰的のときj→k [i.e.,∃n; qj,k(n)>0]ならPk(Tj<∞) = 1.
証明 まず,任意のi, j∈S に対して
Pi(Tj <∞) =qi,j+ X
k∈S;k6=j
qi,kPk(Tj <∞) が示せる. (実際,マルコフ性と時間的一様性より
Pi(X1=k, Tj=n) =qi,kPk(Tj=n−1) をえて
Pi(Tj<∞) = X∞ n=1
X
k∈S
Pi(X1=k, Tj=n)
に代入することにより分かる.) そこでi = j とすると j の再帰性より, k1;qj,k1 > 0 に対し, Pk1(Tj <∞) = 1が分かる. 再び上の式より,k2;qk1,k2 >0, i.e,qj,k(2)
2 >0に対し,Pk2(Tj<∞) = 1 が分かる. 今,仮定のq(n)j,k >0より∃(k1, . . . , kn−1); qj,k1qk1,k2qk2,k3· · ·qkn−1,k >0に注意して上 の議論を繰り返せば,題意をえる.
問 1.7 前の問1.6 と上の補題から次が成り立つことを示せ: j 再帰的,かつj→k ⇒ X
n=0
q(n)k,j =∞.
j, k∈S に対しj→kかつk→j のときj↔kと表す.
命題1.3 j, k∈S;j↔kに対し,j が正再帰的,零再帰的,過渡的ならそれに応じてkもそ うなる. 従って,既約なマルコフ連鎖は正再帰的,零再帰的,過渡的のいずれかになる.
証明 仮定より∃l, m≥0;q(l)j,k>0, qk,j(m)>0. また
q(l+m+n)j,j ≥qj,k(l)q(n)k,kqk,j(m) (n≥0) より
Qjj(s)≥sl+mq(l)j,kqk,j(m)Qkk(s).
これからもし j が過渡的なら
lims↑1Qjj(s) = X∞ n=0
q(n)j,j <∞
で,上のことから X∞ n=0
q(n)k,k<∞をえて,kも過渡的となる. j, kを入れ替えても同じである. 次に正再帰性について考える. 補題1.1のQjj(s)(1−Fjj(s)) = 1よりFjj0 (s) =Q0jj(s)/Qjj(s)2. よってj を正再帰的とすると
lims↑1
Q0jj(s)
Qjj(s)2 =Fjj0 (1−) =Ej[Tj]<∞. さらに上と同様に
Qkk(s) ≥ sl+mq(m)k,j q(l)j,kQjj(s), Q0jj(s) ≥
X∞ n=0
(l+m+n)sl+m+n−1qj,j(l+m+n)
≥ sl+mq(l)j,kqk,j(m)Q0kk(s) が分かるので
Q0kk(s)
Qkk(s)2 ≤ 1
s3(l+m)(q(l)j,k)3(q(m)k,j )3 Q0jj(s) Qjj(s)2. をえる. 従って
Ek[Tk] =Fkk0 (1−) = lim
s↑1
Q0kk(s) Qkk(s)2 <∞ となり kも正再帰的である. やはりj, kを入れ替えても同じである. 問 1.8 k∈S が正再帰的のときEk[Tk] =Fkk0 (1−) を確かめよ.
注意1.3 前の問 1.6, 1.7で述べたことから既約なマルコフ連鎖に対しては
• 再帰的なら∀j, k∈S に対し,P
nq(n)j,k =∞.
• 過渡的なら∀j, k∈S に対し,P
nq(n)j,k <∞. 逆に,あるj, k∈S に対し, P
nq(n)j,k が無限なら再帰的となり,有限なら過渡的となる.
1.2 d 次元ランダムウォーク(d-dimensional Random Walks)
d≥1を次元を表す自然数として, d次元ランダムウォークの再帰性と過渡性の結果と証明につ いて述べる.
Zd3j= (j1, . . . , jd)を d次元格子 (lattice)という.
(Xn, P)がd次元単純ランダムウォーク(simple random walk)であるとは,毎回, 2d個の隣 接点から1 点を等確率で選び,進んで行く運動をいう. つまりYn =Xn−Xn−1 (n≥1)とすると {X0, Yn;n≥1} は独立で, {Yn}は同分布をもち,
P(Yn=k) = 1/(2d) (|k|= 1), = 0 (|k| 6= 1) をみたす. ここでk= (k1, . . . , kd),|k|=p
k12+· · ·+kd. またと {X0, Yn;n≥1}が独立とは, 任 意の自然数nとk0, k1, . . . , kn∈Z に対し,
P(X0=k0, Y1=k1, . . . , Yn =kn) =P(X0=k0)P(Y1=k1)· · ·P(Yn=kn) をみたすときをいう.
一般に Zd 上の分布{pk}k∈Zd が与えられているとき,これを 1 歩の分布として運動するとき, (Xn, P)を単に,d次元ランダムウォークという. つまりP(Yn =k) =pk (n≥1, k∈Zd)をみた している. またPj(X1=k1, . . . , Xn =kn) :=P(X1=k1, . . . , Xn =kn |X0=j)で Pj を定義し て (Xn, Pj)をj を出発するd次元ランダムウォークという.
明かに, このランダムウォークはマルコフ連鎖である. しかもその推移確率 Q = (qj,k) は qj,k=pk−j で与えれる. また単純ランダムウォークは既約である.
問 1.9 このことを確かめよ. (マルコフ性,時間的一様性,推移確率,既約性) 問 1.9改 (Xn, P)をd次元ランダムウォークとする.
(i)Xn+1−Xn と(X0, X1, . . . , Xn)が独立であることを示せ, i.e., P(Xn+1−Xn=j, X0=k0, X1=k1, . . . , Xn=kn)
= P(Xn+1−Xn=j)P(X0=k0, X1=k1, . . . , Xn=kn).
特に k0, k1, . . . , kn−1 ∈ Zd で和をとることにより, Xn+1−Xn と Xn が独立であることも 分る.
(ii)P(Xn+1=j|X0=k0, X1=k1, . . . , Xn=kn) =P(Xn+1=j|Xn=kn) =pj−kn を示せ.
これから {Xn}が時間的一様なマルコフ連鎖で, qj,k=pk−j も分る.
(iii)単純ランダムウォークは既約的であることを示せ. (kj−kk:=|j1−k1|+· · ·+|jd−kd|を用 いてj 6=k, j =kで分けて考える.)
従って,このQ= (qj,k) = (pk−j)を用いて, 正再帰性,零再帰性,過渡性について議論すること ができる.
まず、前節の結果を用いることにより,単純ランダムウォークに関しては次のことが比較的容易 に分る:
定理1.3 d 次元単純ランダムウォークは
(i)d= 1,2 なら零再帰的(i.e.,Ej[Tj] =∞かつPj(Tj <∞))であり,
(ii)d≥3 なら過渡的である.
ここでは3 次元以下について示す.
まず既約性により(正・零)再帰的か過渡的のいずれかに分れるから,q0,0(n) のnについての和の 収束・発散を調べればよい. q(2n+1)0,0 = 0は明らかだから,q0,0(2n)について考えればよい. そこで次 を示す. (これにより再帰的か過渡的かは前節の定理1.2により判定できる.)
命題1.4 d次元単純ランダムウォークの推移確率 Q= (qj,k)に対して (i)d= 1,2 のときn→ ∞ なら
q0,0(2n)∼ (
1/√
πn (d= 1) 1/(πn) (d= 2) (ii)d= 3 なら適当な正の数C に対して
q0,0(2n)≤Cn−3/2.
注意1.4 実は,一般に,次の事実が知られている: (d= 3なら定数はp
(3/π)3/4) q(2n)0,0 ∼21−ddd/2(πn)−d/2 (n→ ∞).
ここで an ∼bn (n→ ∞) ⇐⇒def an/bn →0 (n→ ∞)である.
問 1.10 一般に正の値をとる数列{an},{bn}対して,an∼bn(n→ ∞)なら∃c1, c2>0;c1bn≤ an ≤c2bn (∀n≥1)が成り立つこと示せ.
命題の証明で使う公式を述べておく.
[スターリングの公式 (Stirling’s formula)] n!∼√
2πnn+1/2e−n (n→ ∞).
命題1.4 の証明
d= 1のときは次のことが容易に分るので,スターリングの公式より明らか: q0,0(2n)=
µ2n n
¶ 2−2n. d= 2のときは
q0,0(2n)= X
j,k≥0;j+k=n
(2n)!
(j!k!)24−2n = µ2n
n
¶Xn j=0
µn k
¶2
4−2n
で,さらに Xn j=0
µn k
¶2
= µ2n
n
¶
を用いれば1次元の結果から分る. d= 3のときは
q0,0(2n)= X
j,k,m≥0;j+k+m=n
(2n)!
(j!k!m!)26−2n
