ランダムウォークとパーコレーション

数理統計学 I ^前期

ランダムウォークとパーコレーション

(Random Walks and Percolations)

担当 平場 誠示

平成 13 年 4 月 17 日〜 ( 火 1-2 限実施 )

はじめに (Preface)

数理統計学の目的は，観察によって得られるランダムな現象のデータから,もとの現象をなるべく正確に 推定することにある. そのための手法について解説するのが通常の数理統計学であるが,現実には,調べる 対象に応じた,確率モデルに対する数学的結果が必要となる. そこで本講演ではランダムウォークとパーコ レーションと呼ばれる単純な確率モデルについて得られる数学的結果について解説する.

「ランダムウォーク」とは. 例えば,コイン投げによって１歩進むか戻るかを決めるというモデルで,そ れが果たして出発点に戻ることが出来るかという問題について考える.

「パーコレーション」とはズポンジへの水の浸透や,木々への病気の感染という現象を単純化した確率モ デルで,その浸透率,あるいは感染率（確率）に応じて,どのような現象が起きるかについて解析する.

普通,確率論関係の話をするときには「測度論」「ルベーグ積分論」の知識を必要とする. 本講義では初 めにそのことについて基本的な定義や性質について述べるが,後の話ではあまりそれを表に出さずに,直感 的に理解できるよう工夫した. 但し,証明の都合上,どうしても「積分論」の知識を必要とする事柄に関し ては補章に述べた.

(測度論,ルベーグ積分論について簡単に一通り勉強したい人は講義ノート「ルベーグ積分論速習講座」

を参照して欲しい.)

目 次

1 確率論の基礎 (Basic of Proability Theory) 1 1.1 確率空間と確率変数(Probability Spacees and Random Variables . . . . 1 1.2 期待値,平均値(Expectations, Means) . . . . 2 1.3 大数の弱法則(Weak Law of Large Numbers) . . . . 3

2 ランダムウォーク (Random Walks) 4

2.1 マルコフ連鎖(Markov Chains) . . . . 4 2.2 d次元ランダムウォーク(d-dimensional Random Walks) . . . . 10 2.3 1次元非対称ランダムウォーク

(One-dimensional anti-symmetric Random Walks) . . . . 13

3 パーコレーション (Percolations) 15

3.1 数学的モデルの説明 . . . . 15 3.2 1/3≤pH≤2/3 . . . . 16

4 補章 18

4.1 マルコフ連鎖の正再帰性の判定定理(定理2.2(iii))の証明 . . . . 18 4.2 大数の強法則について . . . . 19

1 確率論の基礎 (Basic of Proability Theory)

1.1 確率空間と確率変数 (Probability Spacees and Random Variables

確率論においては,必ず, ある適当な確率空間(Ω,F, P)があり, その上で定義された,ある確率変数X を対象として,その色々な性質について調べて行こうとする.

ここで(Ω,F, P)が確率空間(probability space) とは

• Ωはある集合(元をω∈Ωで表す)

• F (⊂2^Ω)はΩ上のσ 集合体 (σ-field); (2^Ωは Ωの全部分集合族) (i) Ω∈ F

(ii)A∈ F ⇒A^c∈ F

(iii)An ∈ F (n= 1,2, . . .)⇒

An ∈ F

• P = P(dω) は可測空間 (Ω,F) 上の確率測度 (probability measure), i.e., 全測度 1 の測度;

P :F →[0,1]は集合関数で次をみたす.

(i)P(Ω) = 1

(ii)An ∈ F (n= 1,2, . . .)が互いに素⇒P(

An) =

P(An) (σ 加法性) 問 1.1  (Ω,F, P)を確率空間とするとき,以下が成立することを示せ.

(i)σ-集合体は可算個の集合演算に関して閉じていることを示せ. 即ち,

F をσ-集合体とし，A, B, An ∈ F とする．次もF に属することを示せ．

∅, A∩B, A\B, AB:= (A\B)∪(B\A), ∞ n=1

An.

これからlimAn= lim supAn :=

N≥1

n≥N

An, limAn= lim infAn :=

N≥1

n≥N

An∈ F も分かる.

(lim = inf sup, lim = sup inf と覚えると良い.)

(ii)P(∅) = 0, A, B∈ F;A⊂B ⇒P(A)≤P(B) (単調性).

(iii)Ak∈ F (k= 1,2, . . . , n)が互いに素⇒P(_n

k=1Ak) =_n

k=1P(Ak) (有限加法性).

(iv)An∈ F,An↑ ⇒ P An

= lim

n→∞P(An).

(v)An∈ F,An↓ ⇒ P An

= lim

n→∞P(An).

(vi)An∈ F (n≥1) ⇒P An

≤ P(An).

(vii) (Borel-Cantelli の補題)   An ∈ F (n ≥ 1),

P(An) < ∞ ⇒ P

lim sup

n→∞ An = 0, i.e., P

lim inf

n→∞ A^c_n

= 1.

この確率空間(Ω,F, P)上で定義された関数X =X(ω) : Ω→Rが{X≤a}:={ω∈Ω;X(ω)≤a} ∈ F (^∀a∈R). をみたすとき確率変数 (random variable)という. 特にXk が可算個の値S={aj}j≥1 しか とらないとき,この条件は{X =aj} ∈ F (^∀j≥1) となる.

Xk を確率空間 (Ω,F, P) 上の実数値確率変数とする (k = 1,2, . . . , n). このとき {Xk}ⁿ_k=1 が独立 (independent)であるとは

P(X1≤a1,· · ·, Xn≤an) =P(X1≤a1)· · ·P(Xn≤an) (^∀ak ∈R, k= 1, . . . , n).

さらに上でnが無限のとき{Xk}k≥1 が独立であるとは^∀N ≥1 に対して{Xk}^N_k=1 が独立なときをいう.

特にXk が可算個の値S={aj}j≥1しかとらないとき,上の式は次のように変えても良い:

P(X1=b1,· · ·, Xn=bn) =P(X1=b1)· · ·P(Xn=bn) (bk∈S, k= 1, . . . , n).

またµ(A) = P(X ∈ A) を X の分布 (distribution) といい, F(x) = P(X ≤ x) を X の分布関数 (distribution function)という.

1.2 期待値, 平均値 (Expectations, Means)

以下では話を簡単にするため全ての確率変数X はZ:=Z∪ {±∞}に値をとるものとする. このときX の平均 (expectation, mean)EX =E[X] =

XdP =

Ω

X(ω)P(dω)を次のように定義する.

(1)X≥0 のとき

EX:=

∞ n=0

nP(X=n) +∞ ·P(X =∞).

(P(X =∞) = 0 なら∞ ·P(X=∞) = 0とする. またP(X =∞)>0 ならEX=∞.)

(2)X 一般のときはX⁺:=X ∨0,X⁻:= (−X)∨0とおき(このときX^±≥0,X =X⁺−X⁻ となる

→確かめよ.) EX:=EX⁺−EX⁻ とおく. 但し,∞ − ∞となるときは定義されないとする.

この定義を形式的に表せば EX =

n∈Z

nP(X =n) で, 一般の関数 f : Z → R に対しても, 形式的に Ef(X) =

n∈Z

f(n)P(X =n)と定義する. (厳密には上のように

n;f(n)>0

と

n;f(n)<0

で分けて定義する.) 確率変数X に対して,その分散をV(X) :=E[(X−EX)²] =E[X²]−E[X]²で定義する.

定理 1.1 (Chebichev の不等式)  p≥1 とする. このとき^∀a >0 に対し, P(|X| ≥a)≤ E[|X|^p]

a^p . [証明] P(|X| ≥a) =P(|X|^p≥a^p)よりp= 1として示せば十分.

E|X|=

n≥1

nP(|X|=n)≥

n≥a

nP(|X|=n)≥a

n≥a

P(|X|=n) =aP(|X| ≥a).

定理 1.2  X1, . . . , Xn をZに値をとる確率変数として,E[X_k²]<∞(k= 1, . . . , n)とする. このと き X1, . . . , Xn が独立なら,E[XjXk] =E[Xj]E[Xk] (j=k). さらに平均が0 (E[Xk] = 0)なら

E



 _n

k=1

Xk

₂

= n k=1

E[X_k²].

[証明] (1)j=kなら独立性からP(Xj=m, Xk =n) =P(Xj=m)P(Xk=n)より E[XjXk] =

m,n

mnP(Xj=m, Xk =n) =

m,n

mnP(Xj =m)P(Xk =n) =E[Xj]E[Xk].

(2)展開式 _n

k=1

Xk

₂

= n k=1

X_k²+

j=k

XjXk と(1)よりj =kならE[XjXk] =E[Xj]E[Xk] = 0とな ることから明らか.

1.3 大数の弱法則 (Weak Law of Large Numbers)

コイン投げで, 投げる回数を増やしていくと表の出る割合が1/2 に近づいていくという現象がある. こ れが大数の法則の典型的な例であるが, このとき1 回毎にコインを投げるという行為は独立である.

定理 1.3 (大数の弱法則 (Weak Law of Large Numbers))  X1, X2, . . .を独立な確率変数で，平 均一定EXn=m，分散が有界v := sup_nV(Xn)<∞であるとする．このとき次が成り立つ：^∀ >0に 対して,

n→∞lim P

1 n

n k=1

Xk−m ≥

= 0, i.e., lim

n→∞P

1 n

n k=1

Xk−m <

= 1. [証明] {Xn} が独立であるから{Xn=Xn−m}も独立となる(確かめよ). よって

1 n

n k=1

Xk−m= 1 n

n k=1

(Xk−m)

から,Xn の代わりにXnを考えることによって，初めから m= 0, i.e.,E[Xn] = 0として示せばよい．こ のときV(Xn) =E[Xn²]で,前命題から

E



 _n

k=1

Xk

₂

= n k=1

E[X_k²] = n k=1

V(Xk)≤nsup

n V(Xn) =nv.

よって^∀ >0 に対して, P

1 n

n k=1

Xk

≥

= P

n k=1

Xk

≥n

≤ E[(_n

k=1Xk)²] ²n²

≤ nv ²n²

= v

²n

→ 0 (n→ ∞).

注意 1.1  実際には上の条件のもとで,もっと強い結果P

n→∞lim 1 n

n k=1

Xk=m

= 1が成り立つ.

このことについては補章でまた触れる.

一般に確率変数Xn, X^に対して,^∀ >0,P(|Xn−X| ≥)→0 (n→ ∞)のとき,Xn→X in pr. と表し,Xn が X に確率収束するという. またP(Xn→X) = 1のとき,Xn→X,P-a.s. と表し,XnがX に概収束するという. (a.s. ^はalmost surely^の略)

問1.2 “概収束 ⇒確率収束”, i.e.,Xn→X,P-a.s. ⇒Xn→X in pr. ^を示せ. (ヒント P(Xn→X) = 1 ⇐⇒

P

k≥1

N≥1

n≥N

|Xn−X|< 1 k

= 1 ⇐⇒ P

k≥1

N≥1

n≥N

|Xn−X| ≥ 1 k

= 0

=⇒^∀k≥1, lim

N→∞P

n≥N

|Xn−X| ≥ 1 k

=P

N≥1

n≥N

|Xn−X| ≥ 1 k

= 0

また確率収束の方は^∀k≥1に対し,ε= 1/kとして,

n→∞lim P(|Xn−X| ≥1/k) = 0 ⇐⇒ ^∀m≥1,^∃N≥1;^∀n≥N, P(|Xn−X| ≥1/k)<1/m.)

2 ランダムウォーク (Random Walks)

ランダムウォークは日本語で「酔歩」というが,確率過程の中でも,最も単純なモデルで様々な性質が研 究されている. 本講義では「酔っ払いは果たして家に帰り着くことができるか？」,即ち,「ランダムウォー クは再帰的か？」という問題について議論する. もう少し正確にはd≥1を次元を表す自然数として,d次 元ランダムウォークの再帰性と過渡性の結果と証明について述べる.

Z^d (j= (j1, . . . , jd))を d次元格子 (lattice) という.

(Xn, P)がd次元単純ランダムウォーク(simple random walk)であるとは,毎回, 2d個の隣接点から 1 点を等確率で選び,進んで行く運動をいう. つまりYn=Xn−Xn−1 (n≥1) とすると{X0, Y1, Y2, . . .}

は独立で,{Yn}は同分布をもち,

P(Yn=k) = 1/(2d) (|k|= 1), = 0 (|k| = 1) をみたす. ここでk= (k1, . . . , kd),|k|=

k²₁+· · ·+k²_d. また{X₀, Y1, Y2, . . .}が独立とは,任意の自然 数nとk0, k1, . . . , kn∈Zに対し,

P(X0=k0, Y1=k1, . . . , Yn =kn) =P(X0=k0)P(Y1=k1)· · ·P(Yn=kn) をみたすときをいう.

一般にZ^d 上の分布{p_k}_k∈Z^d (pk≥0,

pk = 1)が与えられているとき,これを1歩の分布として運動 する(Xn, P)を単に,d次元ランダムウォークという. つまりP(Yn =k) =pk (n≥1, k∈Z^d)をみたして いる. またPj(X1=k1, . . . , Xn =kn) :=P(X1=k1, . . . , Xn =kn|X0 =j)でPj を定義して (Xn, Pj) をj を出発するd次元ランダムウォークという.

注意 2.1  条件付確率 P(A|B) := P(A∩B)/P(B) は P(B)>0 のとき定義されるので上の条件 はそれも仮定に含まれているとみなす.

問 事象A, B∈ F が独立 ⇐⇒ P(A|B) =P(A)を示せ.

2.1 マルコフ連鎖 (Markov Chains)

確率過程とは時間とともにランダムに変化・運動していく対象を指すが,まずはランダムウォークよりは 少し,一般的な「マルコフ連鎖」と呼ばれる確率過程について解説する. 本節では次の結果を紹介する.

定理 2.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).

本講義では時間的一様でないものは扱わないので以下ではマルコフ連鎖といったときは全て, 時間的一 様なマルコフ連鎖を指すものとする.

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)で定義するというのと同じことで,実際に計算するときは こちらの方が都合が良い.)

注意 2.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_j,k⁽ⁿ⁾ =P(Xn = k | X0 =j) とおき, Q⁽ⁿ⁾ = (q_j,k⁽ⁿ⁾) をn 階推移確率(行列) (n-step transition probability (transition matrix)),特に,Q⁽¹⁾ をQ= (qj,k)で表し,単に,推移確 率(行列)という.

問 2.1  次を示せ.

(i)q_j,k⁽ⁿ⁾≥0,

kq_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⁽⁰⁾=I:= (δjk) (単位行列),Q⁽ⁿ⁾=Qⁿ (n≥1),但し,δjk= 1 (j=k), = 0 (j=k).

問 2.2  初期分布をµ={µj} とするときXn の分布が次で与えられることを示せ. P(Xn=k) =

j∈S

µjq⁽ⁿ⁾_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] = ∞ m=1

mPj(Tj=m) +∞ ·Pj(Tj =∞).

全ての j が再帰的(or 正再帰的, 零再帰的,過渡的)なら(Xn)は再帰的 (or正再帰的, 零再帰的, 過渡 的)であるという.

問 2.3  正再帰的なら再帰的であることを示せ.

マルコフ連鎖 {Xn}あるいは推移確率Q= (qj,k)とある確率分布π={πj}に対して

• πが定常分布(stationary distribution) ⇐⇒^def πk =

jπjqj,k (k∈S),

• πが可逆分布(reversible distribution) ⇐⇒^def πkqk,j=πjqj,k (j, k∈S) と定義する.

問 2.4  可逆分布は定常分布であることを示せ.

問 2.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_j,k⁽ⁿ⁾>0 をみたすときをいう. つまり,どこから出発しても何ステップかで,どこへ でもいける可能性があるということである. (もう少し分りやすくいうと,トラップと通過するだけの点,絶 対に行けない点がないということである.)

次の事実が時間的一様なマルコフ連鎖に対する,本節のメインの結果である:

定理 2.2   j, k∈S とする.

(i)j が再帰的という条件は次のそれぞれと同値:

a) ∞ n=0

q_j,j⁽ⁿ⁾=∞.

b) Pj({Xn} は j に無限回戻る ) = 1. 

(ii) j が過渡的という条件は次のそれぞれと同値: a)

∞ n=0

q_j,j⁽ⁿ⁾<∞.

b) Pj({Xn} は j に無限回戻る ) = 0.

(iii) {Xn} が既約なマルコフ連鎖なら, 再帰的か, 過渡的かのどちらかになるが, もっと詳しく正再帰

的,零再帰的,過渡的のいずれかになる. さらに正再帰的となるための必要十分条件は定常分布(πj) [ ^∀k,

jπjqj,k=πk] が存在することで,このときπj= 1/Ej[Tj]で与えられる(従って定常分布は存在すれば 一意にきまる).

まず(i), (ii)のb)について述べ,それからa)の判定定理, (iii)の前半について証明を与える. (iii)の正 再帰性の判定定理の証明は最後の補章で述べる.

次の命題の証明で用いる問いを 2つ挙げておく.

問 O-1 事象列{Bk}ⁿ_k=1 が互いに素で,事象A, Cに対し,P(A|Bk) =P(A|C) (1≤k≤n)をみた しているとする. このときP(A|

Bk) =P(A|C)が成り立つことを示せ.

問 O-2 m, n≥1,j1, . . . , jm, k0, k1, . . . , kn∈S に対して

P(Xn+1=j1, . . . , Xn+m=jm|X0=k0, X1=k1, . . . , Xn=kn)

=P(Xn+1=j1, . . . , Xn+m=jm|Xn =kn).

命題 2.1  (i)j∈S が再帰的ならPj({Xn} は j に無限回戻る ) = 1. (ii) j∈S が過渡的なら Pj({Xn}は j に無限回戻る) = 0.

証明 直感的には理解できるであろう. 再帰的な場合は,有限時間で戻る確率が1 だから, 1回目に戻っ たときから考えれば, 再び有限時間で戻るからそれを繰り返せばよい. 過渡的な場合は戻る確率が 1 より 小さいからそれを繰り返していけば,確率は0 に近づく.

m回目に j に戻る時間をT_j^(m)とおく.

T_j⁽¹⁾=Tj, T_j^(m)= min{n > T_j^(m−1);Xn=j} (=∞ if{·}=∅).

まずPj(T_j^(m)<∞) =Pj(Tj<∞)^mを示す. 自然数s, tに対し,マルコフ性と時間的一様性を用いて, Pj(T_j^(m)=s+t|T_j^(m−1)=s) =Pj(Tj =t)

が示せて(実際, [左辺]=P(Xs+t=j, Xs+u=j (1≤u≤t−1))で, {Xu=j}=

ku∈S;ku=j{Xu=ku} と{T_j^(m−1)=s}が{X1, . . . , Xs(=j)}の状態によって決まることに注意して,上の 2つの問O-1, O-2を 用いれば良い.) これから

Pj(T_j^(m−1)=s, T_j^(m)=s+t) =Pj(T_j^(m−1)=s)Pj(Tj=t) をえる. よって

Pj(T_j^(m)<∞) = Pj(T_j^(m−1)< T_j^(m)<∞)

= ∞ s=m−1

∞ t=1

Pj(T_j^(m−1)=s, T_j^(m)=s+t)

= Pj(T_j^(m−1)<∞)Pj(Tj<∞) より,Pj(T_j^(m)<∞) =Pj(Tj <∞)^m が分かる. これより

Pj({Xn}はjに無限回戻る) = Pj(

m

{T_j^(m)<∞})

= lim

m→∞Pj(T_j^(m)<∞)

= lim

m→∞Pj(Tj <∞)^m. これはPj(Tj <∞) = 1 なら1,そうでないなら0 である.

[実際の講義では,以下1.1節の終わりまでを次節1.2の問2.12の後に.]

再帰的,過渡的の判定定理の証明のためにまずいくつか記号を定義する. j, k∈Sに対し,f_j,k^(m):=Pj(Tk = m) (m≥1)とおき

Qjk(s) :=

∞ n=0

q⁽ⁿ⁾_j,ksⁿ (|s|<1), Fjk(s) :=

∞ m=1

f_j,k^(m)sⁿ (|s| ≤1)

とおく. それぞれ{q⁽ⁿ⁾_j,k}n≥0, {f_j,k^(m)}m≥1 の母関数 (generating functions) という.

Fjk(1) =Pj(Tk <∞)に注意せよ.

補題 2.1  j, k∈S に対し,次が成り立つ: q⁽ⁿ⁾_j,k =

n m=1

f_j,k^(m)q_k,k^n−m(n≥1), Qjk(s) =δjk+Fjk(s)Qkk(s) (|s|<1). 証明 {Tk=m}={Xm=k, Xs=k(1≤s≤m−1)}に注意して

n m=1

f_j,k^(m)q^(n−m)_k,k = n m=1

Pj(Tk=m)Pj(Xn=k|Xm=k)

= n m=1

Pj(Tk=m)Pj(Xn=k|Tk =m)

= n m=1

Pj(Xn =k, Tk =m)

= Pj(Xn=k)

= q⁽ⁿ⁾_j,k. またこれを用いて

Qjk(s) = δjk+ ∞ n=1

q_j,k⁽ⁿ⁾sⁿ

= δjk+ ∞ n=1

n m=1

f_j,k^(m)q_k,k^(n−m)sⁿ

= δjk+Fjk(s)Qkk(s).

命題 2.2  j∈S が再帰状態 ⇐⇒

∞ n=0

q⁽ⁿ⁾_j,j =∞.

証明 上の補題よりQjj(s)(1−Fjj(s)) = 1 (|s|<1)が成り立つからFjj(1) =Pj(Tj<∞)と lims↑1Qjj(s) =

∞ n=0

q⁽ⁿ⁾_j,j ≤ ∞ に注意してs↑1とすれば分かる. 形式的に次のように表せる:

∞ n=0

q_j,j⁽ⁿ⁾(1−Pj(Tj <∞)) = 1.

問 2.6  上の証明を参考にj=kのときを考えることにより

j∈S 過渡的 ⇒

n=0

q_k,j⁽ⁿ⁾<∞(^∀k∈S) が分かり,逆に

∃k∈S;

n=0

q⁽ⁿ⁾_k,j =∞ ⇒ j: 再帰的 となることを示せ.  (

nq⁽ⁿ⁾_k,j =Fkj(1)

nq⁽ⁿ⁾_j,j.)

補題 2.2  j が再帰的のときj →k[i.e., ^∃n;q_j,k⁽ⁿ⁾>0]ならPk(Tj<∞) = 1.

証明 まず,任意のi, j ∈S に対して

Pi(Tj <∞) =qi,j+

k∈S;k=j

qi,kPk(Tj <∞)

が示せる. (実際,マルコフ性と時間的一様性より

Pi(X1=k, Tj=n) =qi,kPk(Tj=n−1) をえて

Pi(Tj<∞) = ∞ n=1

k∈S

Pi(X1=k, Tj=n)

に代入することにより分かる.) そこでi=jとするとjの再帰性より,k1;qj,k1 >0に対し,Pk1(Tj<∞) = 1 が分かる. 再び上の式より,k2;qk1,k2 >0, i.e, q_j,k⁽²⁾₂ >0 に対し,Pk2(Tj <∞) = 1 が分かる. 今, 仮定の q⁽ⁿ⁾_j,k >0より^∃(k1, . . . , kn−1);qj,k1qk1,k2qk2,k3· · ·qkn−1,k>0に注意して上の議論を繰り返せば,題意をえ る.

問 2.7  前の問2.6と上の補題から次が成り立つことを示せ:

j 再帰的,かつj→k ⇒

n=0

q⁽ⁿ⁾_k,j =∞.

j, k∈S に対しj →kかつk→j のときj↔k と表す.

命題 2.3   j, k∈S;j↔kに対し,j が正再帰的,零再帰的,過渡的ならそれに応じてkもそうなる. 従って,既約なマルコフ連鎖は正再帰的,零再帰的,過渡的のいずれかになる.

証明 仮定より^∃l, m≥0;q^(l)_j,k>0, q_k,j^(m)>0. また

q^(l+m+n)_j,j ≥q_j,k^(l)q⁽ⁿ⁾_k,kq_k,j^(m) (n≥0) より

Qjj(s)≥s^l+mq^(l)_j,kq_k,j^(m)Qkk(s). これからもしj が過渡的なら

lims↑1Qjj(s) = ∞ n=0

q⁽ⁿ⁾_j,j <∞

で, 上のことから ∞ n=0

q⁽ⁿ⁾_k,k <∞をえて,kも過渡的となる. j, kを入れ替えても同じである.

次に正再帰性について考える. 補題2.1のQjj(s)(1−Fjj(s)) = 1よりF_jj(s) =Q_jj(s)/Qjj(s)². よっ てj を正再帰的とすると

lims↑1

Q_jj(s)

Qjj(s)² =F_jj(1−) =Ej[Tj]<∞.

さらに上と同様に

Qkk(s) ≥ s^l+mq^(m)_k,j q^(l)_j,kQjj(s), Q_jj(s) ≥ ^∞

n=0

(l+m+n)s^l+m+n−1q_j,j^(l+m+n)

≥ s^l+mq^(l)_j,kq_k,j^(m)Q_kk(s) が分かるので

Q_kk(s)

Qkk(s)² ≤ 1

s^3(l+m)(q^(l)_j,k)³(q^(m)_k,j )³ Q_jj(s) Qjj(s)². をえる. 従って

Ek[Tk] =F_kk(1−) = lim

s↑1

Q_kk(s) Qkk(s)² <∞ となりkも正再帰的である. やはりj, kを入れ替えても同じである.

問 2.8  k∈S が正再帰的のとき Ek[Tk] =F_kk(1−)を確かめよ.

注意 2.3  前の問2.6, 2.7で述べたことから既約なマルコフ連鎖に対しては

• 再帰的なら^∀j, k∈S に対し,

nq_j,k⁽ⁿ⁾=∞.

• 過渡的なら^∀j, k∈S に対し,

nq_j,k⁽ⁿ⁾<∞. 逆に,あるj, k∈S に対し,

nq_j,k⁽ⁿ⁾が無限なら再帰的となり, 有限なら過渡的となる.

2.2 d 次元ランダムウォーク ( d -dimensional Random Walks)

(Xn, P)をd次元ランダムウォークとする. 即ち,{pk}_k∈Z^d をZ^d 上の分布として,{X0, X1−X0, X2− X1, . . .} が独立で,P(Xn−Xn−1=k) =pk (n≥1, k∈Z^d)をみたすとする. (特に pk = 1/(2d)のとき 単純ランダムウォークという.)

明かに,d次元ランダムウォークはマルコフ連鎖である. しかもその推移確率Q= (qj,k)はqj,k=pk−j

で与えれる. また単純ランダムウォークは既約である.

問 2.9  このことを確かめよ. [マルコフ性,時間的一様性,推移確率,既約性]

問 2.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∈Z^d で和をとることにより,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)単純ランダムウォークは既約的であることを示せ. (j−k := |j₁−k1|+· · ·+|j_d−kd| を用いて j=k, j=kで分けて考える.)

従って,このQ= (qj,k) = (pk−j)を用いて,正再帰性,零再帰性,過渡性について議論することができる.

まず、前節の結果を用いることにより,単純ランダムウォークに関しては次のことが比較的容易に分る:

定理 2.3  d次元単純ランダムウォークは

(i)d= 1,2なら零再帰的 (i.e.,Ej[Tj] =∞かつPj(Tj<∞))であり, (ii)d≥3なら過渡的である.

ここでは3次元以下について示す.

まず既約性により(正・零)再帰的か過渡的のいずれかに分れるから,q_0,0⁽ⁿ⁾のnについての和の収束・発 散を調べればよい. q⁽²ⁿ⁺¹⁾_0,0 = 0は明らかだから,q_0,0⁽²ⁿ⁾について考えればよい. そこで次を示す. (これによ り再帰的か過渡的かは前節の定理2.2により判定できる.)

命題 2.4   d次元単純ランダムウォークの推移確率 Q= (qj,k)に対して (i)d= 1,2のとき n→ ∞なら

q⁽²ⁿ⁾_0,0 ∼

1/√

πn (d= 1) 1/(πn) (d= 2) (ii)d= 3なら適当な正の数 C に対して

q_0,0⁽²ⁿ⁾≤Cn^−3/2.

注意 2.4  実は,一般に,次の事実が知られている: (d= 3なら定数は

(3/π)³/4) q⁽²ⁿ⁾_0,0 ∼2^1−dd^d/2(πn)^−d/2 (n→ ∞).

ここでan∼bn (n→ ∞) ⇐⇒^def an/bn→1 (n→ ∞)である.

問 2.10  一般に正の値をとる数列{an},{bn}対して,an∼bn (n→ ∞)なら ^∃c1, c2>0;c1bn≤an ≤ c2bn (^∀n≥1) が成り立つこと示せ.

命題の証明で使う公式を述べておく.

[スターリングの公式 (Stirling’s formula)] n!∼√

2πn^n+1/2e⁻ⁿ (n→ ∞).

命題 2.4 の証明

d= 1 のときは次のことが容易に分るので,スターリングの公式より明らか:

q_0,0⁽²ⁿ⁾= 2n

n 2⁻²ⁿ. d= 2 のときは

q_0,0⁽²ⁿ⁾=

j,k≥0;j+k=n

(2n)!

(j!k!)²4⁻²ⁿ= 2n

n n j=0

n k

2

4⁻²ⁿ

で, さらに n j=0

n k

2

= 2n

n を用いれば1 次元の結果から分る.

d= 3 のときは

q_0,0⁽²ⁿ⁾=

j,k,m≥0;j+k+m=n

(2n)!

(j!k!m!)²6⁻²ⁿ で, 3項展開公式より

q⁽²ⁿ⁾_0,0 ≤cn

(2n)!

n! 3ⁿ6⁻²ⁿ

をえる. ここでcn = maxj,k,m≥0;j+k+m=n(j!k!m!)⁻¹ である. さらにこのcn に対し,次が成り立つことか ら, 再びスターリングの公式を用いれば題意をえる.

cn≤c3^n+3/2n^−n−3/2eⁿ (c >0 はn≥1に無関係な定数). (1) 実際,nを3 で割っていくつ余るかで場合分けして

cn ≤







(m!)⁻³ (n= 3m) (m!)⁻²((m+ 1)!)⁻¹ (n= 3m+ 1) (m!)⁻¹((m+ 1)!)⁻² (n= 3m+ 2)

(2)

が分るので,スターリングの公式より,ある定数 c1, c2>0が存在して c1n^n+1/2e⁻ⁿ≤n!≤c2n^n+1/2e⁻ⁿ をみたすので上に代入すればよい.

問 2.11  1 次元と2次元のときにスターリングの公式を用いて計算せよ.

問 2.12  上の式(2)を示し,それを用いて(1)を導き,d= 3の証明(計算)を確かめよ.

[講義では次に再帰性の判定定理(定理2.2)の証明を述べた.]

d= 1,2 のとき再帰的であることは分かったが,それが零再帰的であるを示す.

命題 2.5  d= 1,2のときZ^d 上の単純ランダムウォ−クは零再帰的(i.e.,E0[T0] =∞)である.

補題 2.3  (i)α >−1のとき ∞ n=1

n^αsⁿ∼ Γ(α+ 1)

(1−s)^α+1 (s↑1). (ii)α=−1 のとき

∞ n=1

n⁻¹sⁿ= log 1 1−s.

証明 α >−1 のときはlog(1/s)∼1−s(s↑1) と次の積分との比較により容易に分かる:

_∞

0

x^αs^xdx=

log1 s

−α−1

Γ(α+ 1). α=−1 のときはlogのテイラー展開.

命題 2.5 の証明

命題 2.3 の証明で示したようにF₀₀(s) = Q₀₀(s)/Q00(s)² であるから, d = 1のとき, q⁽²ⁿ⁾_0,0 ∼1/√ πn (n→ ∞)より,上の補題を用いてs↑1 のとき

Q00(s) = 1 + ∞ n=1

s²ⁿq_0,0⁽²ⁿ⁾∼1 + ∞ n=1

s²ⁿ 1

√πn ∼ 1

√π

Γ(1/2) (1−s²)^1/2,

Q₀₀(s) = ∞ n=1

2ns²ⁿ⁻¹q_0,0⁽²ⁿ⁾∼^∞

n=1

2ns²ⁿ⁻¹ 1

√πn ∼ 2

√π

Γ(3/2) (1−s²)^3/2. よって

F₀₀(s) = Q00(s) Q00(s)² ∼ 2√

πΓ(3/2) Γ(1/2)²

1 s√

1−s² (s↑1). ゆえに

E0[T0] = lim

s↑1F₀₀(s) =∞.

d= 2ならq⁽²ⁿ⁾_0,0 ∼1/(πn) (n→ ∞)より,同様にs↑1のとき Q00(s)∼ 1

πlog 1 1−s², Q00(s)∼ 2

πs(1−s²) ∼ 2 π(1−s²) から

E0[T0] = lim

s↑12

π(1−s²)

log 1 1−s²

2₋₁

=∞.

2.3 1 次元非対称ランダムウォーク

(One-dimensional anti-symmetric Random Walks)

1 次元非対称単純ランダムウォーク

Z¹ 上のランダムウォーク{Xn} で右へ1 歩進む確率をp(0< p <1),左へ1 歩進む確率を1−pとす る. p= 1/2のとき,この{Xn=Xn^(p)}を1 次元非対称単純ランダムウォークという.

注 前にd次元単純ランダムウォークを定義したが,正確にはd次元回転不変単純ランダムウォークと呼ぶべきで, ただ「単純」といったときには隣接する点にしか移りえないとき(つまりそれ以外へ行く確率が0^のとき)^をさす.

1 次元非対称単純ランダムウォークの推移確率は

qj,j+1=q0,1=p, qj,j−1=q0,−1= 1−p で, さらにn階推移確率は

q_j,k⁽ⁿ⁾=



 n

n+j−k 2

p^(n−j+k)/2(1−p)^(n+j−k)/2 (n+j−k∈2Z)

0 (n+j−k∈2Z+ 1).

問 2.13  これを説明せよ. [ヒント +1へ l 回,−1へ m回として,n=l+m. ではk−j =?.]