パーコレーションとランダムウォーク (Percolations and Random Walks)

数理統計学 I ^前期

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

(Percolations and Random Walks)

担当 平場 誠示

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

はじめに (Preface)

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

「パーコレーション」とはズポンジへの水の浸透や, 木々への病気の感染という現象を単純化したモデル で , その浸透率・感染率（確率）に応じて , ある値を境に、様相が一変するという現象 ( 臨界現象 ) が起き る . その値 ( 臨界確率 ) がいくつなのかという問題を考える .

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

目 次

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

2 パーコレーション (Percolations) 5

2.1 数学的モデルの説明 . . . . 5 2.2 1/3 ≤ p

H

≤ 2/3 . . . . 6

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

3.1 マルコフ連鎖 (Markov Chains) . . . . 8 3.2 d 次元ランダムウォーク (d-dimensional Random Walks) . . . . 14

4 補章 18

4.1 大数の強法則について . . . . 18

4.2 マルコフ連鎖の正再帰性の判定定理 ( 定理 3.2(iii)) の証明 . . . . 18

1 ^{確率論の基礎} (Basics 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) A

_n

∈ F (n = 1, 2, . . .) ⇒ S

A

_n

∈ F

• P = P(dω) は可測空間 (Ω, F ) 上の確率測度 (probability measure), i.e., 全測度 1 の測度 ; P : F → [0, 1] は集合関数で次をみたす .

(i) P (Ω) = 1

(ii) A

n

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

A

n

) = P

P (A

n

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

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

_n

∈ F とする．次も F に属することを示せ．

∅ , A ∩ B, A \ B, A 4 B := (A \ B) ∪ (B \ A),

\

∞ n=1

A

_n

.

これから limA

_n

= lim sup A

_n

:= \

N≥1

[

n≥N

A

_n

, limA

_n

= lim inf A

_n

:= [

N≥1

\

n≥N

A

_n

∈ F も分かる . (lim = inf sup, lim = sup inf と覚えると良い.)

(ii) P( ∅ ) = 0, A

k

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

n

k=1

A

k

) = P

n

k=1

P (A

k

) ( 有限加法性 ).

(iii) A, B ∈ F ; A ⊂ B ⇒ P (A) ≤ P (B) (単調性).

(iv) A

n

∈ F , A

n

↑ ⇒ P ³[

A

n

´

= lim

n→∞

P(A

n

).

(v) A

n

∈ F , A

n

↓ ⇒ P ³\

A

n

´

= lim

n→∞

P(A

n

).  上のと合わせて確率の単調連続性という . (vi) A

n

∈ F (n ≥ 1) ⇒ P ³[

A

n

´

≤ X

P (A

n

) ( 劣加法性 ).

(vii) (Borel-Cantelli の補題)   A

_n

∈ F (n ≥ 1), X

P (A

_n

) < ∞ = ⇒ P µ

lim sup

n→∞

A

_n

¶

= 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) という . 特に X が可算個の値 S = { a

_j

}

j≥1

⊂ R しかとらないとき , この条件は { X = a

j

} ∈ F (

^∀

j ≥ 1) と置き換えて良い ( 確かめよ！ ).

X

k

を確率空間 (Ω, F , P ) 上の実数値確率変数とする (k = 1, 2, . . . , n). このとき { X

k

}

ⁿk=1

が独立 (independent) であるとは

P (X

1

≤ b

1

, · · · , X

n

≤ b

n

) = P(X

1

≤ b

1

) · · · P (X

n

≤ b

n

) (

^∀

b

k

∈ R, k = 1, . . . , n).

さらに上で n が無限のとき { X

_k

}

k≥1

が独立であるとは

^∀

N ≥ 1 に対して { X

_k

}

^Nk=1

が独立なときをいう . 特に X

k

が可算個の値 S = { a

j

}

j≥1

しかとらないとき , 上の式は次のように変えても良い : ( 確かめよ！ )

P(X

₁

= b

₁

, · · · , X

_n

= b

_n

) = P (X

₁

= b

₁

) · · · P (X

_n

= b

_n

) (b

_k

∈ S, k = 1, . . . , n).

また µ(A) = P(X ∈ A) を X の分布 (distribution) といい , 形式的に µ = P ◦ X

⁻¹

と表す . F (x) = F

_X

(x) := P (X ≤ x) を X の分布関数 (distribution function) という.

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

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

Z

XdP = Z

Ω

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

(1) X ≥ 0 のとき

EX :=

X

∞ 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 = X

n∈Z

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

n∈Z

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

n;f(n)>0

と X

n;f(n)<0

で分けて定義する .)

問 1.2   | X | = X

⁺

+ X

⁻

を示し, E | X | = X

n≥1

nP ( | X | = n) で与えれることを定義に従って, 確かめよ.

( 但し , 非負確率変数に対する平均の線形性は用いてよい .)

E | X | < ∞ のとき , 確率変数 X は可積分 (ingtegrable) であるという .

X, Y が可積分なら , その絶対収束性から , 平均について線形性が成り立つ , i.e., E[aX +bY ] = aEX +bEY (a, b ∈ R).

実は

,

もっと一般に

±∞

^も込めて

,

上の等式の左辺

,

または右辺の

,

一方でも平均が定義されれば

,

等式は成り立つ ことが証明できる

.

またベクトル値確率変数 X = (X

1

.X

2

) ( 各 X

j

が確率変数 ) についも , 同様に f : Z

²

→ R に対し , 形式 的に Ef (X) = X

n∈Z²

f (n)P (X = n) (n = (n

1

, n

2

)) と定義する .

確率変数 X に対して , その分散を V (X) := E[(X − EX)

²

] = E[X

²

] − (E[X ])

²

で定義する . 記号の簡 略化のため, EX

²

:= E[X

²

], (EX )

²

= E[X ]

²

:= (E[X ])

²

と表すこともある. V (X) = E(X − EX)

²

= EX

²

− (EX )

²

.

問 1.3   (EX )

²

≤ E[X

²

] と E | XY | ≤ (E[X

²

]E[Y

²

])

^1/2

(Schwarz の不等式) を示せ.

( ヒント  分散と E(X − tY )

²

≥ 0 (

^∀

t ∈ R) を用いる .) 定理 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 | = X

n≥1

nP( | X | = n) ≥ X

n≥a

nP ( | X | = n) ≥ a X

n≥a

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

定理 1.2   X

₁

, . . . , X

_n

を Z に値をとる確率変数として, E[X

_k²

] < ∞ (k = 1, . . . , n) とする. このと き X

1

, . . . , X

n

が独立なら , E[X

j

X

k

] = E[X

j

]E[X

k

] (j 6 = k). さらに平均が 0 (E[X

k

] = 0) なら

E



 Ã

_n

X

k=1

X

_k

!

2



 = X

n k=1

E[X

_k²

].

[ 証明 ]   (1) j 6 = k なら独立性から P(X

_j

= m, X

_k

= n) = P (X

_j

= m)P (X

_k

= n) より E[X

j

X

k

] = X

m,n

mnP (X

j

= m, X

k

= n) = X

m,n

mnP (X

j

= m)P (X

k

= n) = E[X

j

]E[X

k

].

(2) 展開式 Ã

_n

X

k=1

X

_k

!

2

= X

n

k=1

X

_k²

+ X

j6=k

X

_j

X

_k

と (1) より j 6 = k なら E[X

_j

X

_k

] = E[X

_j

]E[X

_k

] = 0 とな ることから明らか .

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

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

数式化するには n 回目にコインを投げて , 表なら X

n

= 1, 裏なら X

n

= 0 と決める . このとき確率平均 は EX

n

= 1/2 ( ちなみに分散は V (X

n

) = 1/2 で有界 ). このとき n 回まで投げて , 表の出た回数の算術平 均は 1

n X

n

k=1

X

k

で , 大数の法則とはこれが n → ∞ のとき , 確率平均の 1/2 に「近づく」ということである . 定理 1.3 (大数の弱法則 (Weak Law of Large Numbers))   X

₁

, X

₂

, . . . を独立な確率変数で，平 均一定 EX

n

= m ，分散が有界 v := sup

_n

V (X

n

) < ∞ であるとする．このとき次が成り立つ：

^∀

² > 0 に 対して ,

n

lim

→∞

P ï¯ ¯ ¯ ¯

1 n

X

n

k=1

X

k

− m

¯ ¯

¯ ¯

¯ ≥ ²

!

= 0, i.e., lim

n→∞

P ï¯ ¯ ¯ ¯

1 n

X

n

k=1

X

k

− m

¯ ¯

¯ ¯

¯ < ²

!

= 1.

[ 証明 ]   { X

_n

} が独立であるから { X e

_n

= X

_n

− m } も独立となる ( 確かめよ ). よって 1

n X

n k=1

X

k

− m = 1 n

X

n k=1

(X

k

− m)

から , X

n

の代わりに X e

n

を考えることにより，初めから m = 0, i.e., E[X

n

] = 0 として良い．このとき V (X

n

) = E[X

_n²

] で , 前命題から

E



 Ã

_n

X

k=1

X

k

!

2



 = X

n

k=1

E[X

_k²

] = X

n

k=1

V (X

k

) ≤ n sup

n

V (X

n

) = nv.

よって

^∀

² > 0 に対して , P ï¯ ¯ ¯ ¯

1 n

X

n

k=1

X

_k

¯ ¯

¯ ¯

¯ ≥ ²

!

= P ï¯ ¯ ¯ ¯ X

n

k=1

X

_k

¯ ¯

¯ ¯

¯ ≥ ²n

!

≤ E[( P

n

k=1

X

_k

)

²

]

²

²

n

²

≤ nv

²

²

n

²

= v

²

²

n → 0 (n → ∞ ).

一般に確率変数 X

_n

, X に対して ,

^∀

² > 0, P( | X

_n

− X | ≥ ²) → 0 (n → ∞ ) のとき , X

_n

→ X in pr. と表 し , X

n

が X に確率収束するという . また P (X

n

→ X ) = 1 のとき , X

n

→ X , P -a.s. と表し , X

n

が X に 概収束するという . (a.s. は almost surely の略 )

問 1.4   “概収束 ⇒ 確率収束”, i.e., X

_n

→ X, P -a.s. ⇒ X

_n

→ X in pr. を示せ.

( ヒント  次の同値性・式変形の理由を説明せよ . P (X

_n

→ X) = 1 ⇐⇒ 1 = P



 \

k≥1

[

N≥1

\

n≥N

½

| X

_n

− X | < 1 k

¾ 



≤ P



 [

N≥1

\

n≥N

½

| X

_n

− X | < 1 k

¾ 

 (

^∀

k ≥ 1)

また

^∀

k ≥ 1 に対し,

(右辺) = lim

N→∞

P



 \

n≥N

½

| X

_n

− X | < 1 k

¾ 

 ≤ lim

n→∞

P µ

| X

_n

− X | < 1 k

¶

これは確率収束と同値 ( 即ち , 1/k を ² > 0 に置き換えられる . 何故か？ )

注意 1.1  一般に , 上の問の逆は成り立たない . 即ち , 確率収束しても概収束しない例が作れる . しか し, 確率収束していれば, 適当な部分列が概収束するようにとれることは知られている.

問 1.5  「確率収束なら適当な部分列に対して概収束」 , i.e., ”X

n

→ X in pr. ⇒

^∃

{ n

k

} ; X

nk

→ X a.s.“

を示せ .

( ヒント  確率収束の仮定より , 次が分る ( 何故か ?)

^∃

{ n

_k

} ; P µ

| X

_nk

− X | ≥ 1 2

^k

¶

≤ 1

2

^k

. 和が収束する ことから Borel-Cantelli の補題が使えて P



 [

N≥1

\

k≥N

½

| X

nk

− X | < 1 2

^k

¾ 

 = 1. これから容易に分る .)

上の定理と同じ条件のもとで, もっと強い結果が成り立つ. ここでは証明はしないが, 次の定理である.

定理 1.4 ( 大数の強法則 (Strong Law of Large Numbers))   X

1

, X

2

, . . . を独立な確率変数で，

平均一定 EX

_n

= m ，分散が有界 v := sup

_n

V (X

_n

) < ∞ であるとする．このとき次が成り立つ：

P Ã

n

lim

→∞

1 n

X

n k=1

X

_k

= m

!

= 1.

注意 1.2  一般に , 平均が一定でない場合でも , 次が成り立つ . P

Ã

n

lim

→∞

1 n

X

n k=1

(X

_k

− EX

_k

) = 0

!

= 1.

2 ^{パーコレーション} (Percolations)

初めに述べたように , パーコレーションとは , スポンジへの水の浸透や , 病気の感染の広がりを表すモデ ルを単純化したもので , 無限の正方格子を考え , その各辺 ( ボンド ) に開閉の確率を p, 1 − p (0 ≤ p ≤ 1) で 与え , p に応じて , 開いた辺の繋がりの全体 ( オープンクラスター ) が無限に広がるかどうか ( の確率 ) を調 べるのである . その際 , ある値を境に , 無限に広がる確率が 0 と正に分かれる , その境になる値 p = p

c

を 臨界確率といい, その値がいくつかという問題が大きな焦点となる.

2.1 数学的モデルの説明

Z

²

を正方格子として , B

²

= { b = { x, y } ; x, y ∈ Z

²

, | x − y | = 1 } を格子上の隣合う 2 点を結ぶ辺（ボン ド, bond）の全体とする. 今, 各ボンドに独立に, 確率 p (0 ≤ p ≤ 1) で open, 確率 1 − p で closed とい う状態を与える . これを確率変数 X

b

= X

_b^(p)

= X

_b^(p)

(ω) を用いて , X

b

= 1, 0 に応じて , ボンド b ∈ B

²

が open, closed であると定義する . X = { X

_b

; b ∈ B

²

} で全体のボンドの状態を表すものとし , それを支配す る確率測度を P

p

とする . 即ち , P

p

(X

b

= 1) = p, P

p

(X

b

= 0) = 1 − p と定義する .

S = { b ∈ B

²

; X

b

= 1 } として , その中で原点 O を含む連結成分を C

O

と表し , 原点を含むオープンクラ スター (open cluster) と呼ぶ . k C

O

k で C

O

の中のボンドの個数を表す ; k C

O

k := ] { b ∈ C

O

} .

ここで , 2 つの臨界確率 (critical probability) を定義する . p

_H

: Hammersley の臨界確率を θ(p) := P

_p

( k C

_O

k = ∞ ) に対し,

p

H

:= inf { p ∈ [0, 1]; θ(p) > 0 } . また p

T

: Temperley の臨界確率を χ(p) := E

p

[ k C

O

k ]

Ã

= X

∞ n=1

nP

p

( k C

O

k = n) + ∞ · P

p

( k C

O

k = ∞ )

! , p

T

:= inf { p ∈ [0, 1]; χ(p) = ∞} .

このとき p

_H

≥ p

_T

は容易に分るが ( → 問 2.1), 「果たして p

_H

= p

_T

となるか？」 「またその値はいくら か？」さらに「無限のオープンクラスターは , もし存在するならその個数はいくつか？」という問題が考え られる . それらに対する答えが次の結果である .

定理 2.1  正方格子 Z

²

でのボンドパーコレーションにおいて, 臨界確率 p

_H

, p

_T

に対し, p

_H

= p

_T

= 1/2 が成り立ち , それを p

c

と表す . また無限のオープンクラスターは p > p

c

のとき , 確率 1 で一意的に 存在し , p ≤ p

_c

のときは確率 1 で存在しない .

注意 2.1. 一般次元の格子 Z

^d

(d ≥ 3) では , 上の定理で p

c

= 1/2 以外の結果はすべて成り立つ . 問 2.1   p

H

≥ p

T

を示せ . ( ヒント θ(p) が単調増加であることに注意して ( 本節の最後に示す ),

^∀

p < p

T

, p ≤ p

_H

を示せば十分. また, χ(p) < ∞ なら θ(p) = 0.)

本講義では , 比較的 , 簡単な議論で分かる不等式評価 1/3 ≤ p

H

≤ 2/3 についてのみ証明する .

さて我々の話において, 厳密には確率空間 (Ω, F , P ) を構成する必要があるのだが, 確率論は割といい加 減な ( 直感的な？ ) 学問で , その辺りをあまりうるさく言わなくても感覚的には大抵 , 理解できるものである . しかしあくまで数学として厳密にやりたいという気持ちもあるので , 正確な構成法を与えることにしよう . Ω = Ξ := { 0, 1 }

^B2

3 ω = ω(b); B

²

→ { 0, 1 } とし , 有限個のボンドの状態 (0 か 1) が決められた次のよ うな Ω の部分集合 ; 筒集合 (cylinder set)

A

ⁱ_b¹₁^,...,i_,...,bⁿ_n

= { ω; ω(b

₁

) = i

₁

, . . . , ω(b

_n

) = i

_n

} (b

_k

∈ B

²

, i

_k

= 0 or 1, k = 1, . . . , n)

の全体を C で表す . F = B (Ξ) := σ( C ) ( C から生成される σ-field, つまり C を含む最小の σ-field) とおく . 実際には

B (Ξ) = \

{G ⊂ 2

^Ω

; G は C を含む σ-field } で与えられる . また確率 P = P

_p

は上のような cylinder set に対し ,

P

p

(A

ⁱ_b¹₁^,_,...,b^···,in_n

) = p

^i1+···+in

(1 − p)

^{(1−i1)+···+(1−in)}

をみたすものが一意的に存在する . ( これは測度の拡張定理を用いて示される .)

別の定義の仕方として

,

各ボンド

b ∈ B

² ごとに確率空間

(Ω

b

, F

^b

, P

b,p

)

を

Ω

b

= { ω(b) : b → { 0, 1 }} , F

^b

= 2

^Ω_b

,

P

b,p

(ω(b) = 1) = p

で決め

,

さらにそれらの

b ∈ B

² についての無限直積で全体の確率空間を決めることも出来る

.

確率変数 X

_b

= X

_b^(p)

は X

_b

(ω) = ω(b) によって定義される . このとき X

_b

の分布は P

_p

(X

_b

= 1) = P

p

(ω(b) = 1) = p となり , また全体のボンドの状態を表す X = { X

b

; b ∈ B

²

} の分布は P

p

となる . つまり X(ω) = ω により分布と確率が同じものとなる . ( 一種の同一視をしている .)

最後に

θ(p) = P

p

( k C

O

k = ∞ )

が

p

に関して単調増加であることを示しておく

. (

直感的には

p

が大きくなるほど 開いたボンドが多くなるので

,

それが無限である確率は高くなる

.)

まず

θ

n

(p) := P

p

( k C

O

k ≥ n)

とおくと

θ(p) = lim

n→∞

θ

n

(p)

より

θ

n

(p)

が単調増加であることを示せばよ い

.

各ボンド

b ∈ B

² に対し

, Z

b＝

Z

b

(ω)

を

[0, 1]

上の一様乱数で

, { Z

b

}

^{が独立とする}

.

その分布を

Q

で表すと

Q(Z

b

≤ p) = p = P

p

(X

b

= 1)

となる

.

従って

S (p) = { b ∈ B

²

; Z

b

≤ p }

^として

,

その原点

O

を含む連結成分を

C

O

(p)

とすれば

,

これは明らかに

p

について単調増加な集合で

θ

n

(p) = P

p

( k C

O

k ≥ n) = Q( k C

O

(p) k ≥ n)

が成り立 つことから

θ

n

(p)

は単調増加となる

.

2.2 1/3 ≤ p

_H

≤ 2/3

臨界確率 p

H

に対して , 簡単な議論で分かる結果を紹介しよう . そこでは統計力学などで広く使われてい る Peierls の論法 を用いる .

定理 2.2   Hammersley の臨界確率 p

_H

= inf { p ∈ [0, 1]; θ(p) = P

_p

( k C

_O

k = ∞ ) > 0 } に対し, 1/3 ≤ p

H

≤ 2/3 が成り立つ .

まず言葉を一つ定義しておく .

点とボンドを交互に並べた集合 γ = { x

₀

, b

₁

, x

₁

, b

₂

, . . . , b

_n

, x

_n

} が長さ n の路 ( みち , path) であるとは (i) b = { x

i−1

, x

i

} , (ii) i 6 = j なら b

i

6 = b

j

.

但し , ボンドだけを並べて γ = { b

₁

, . . . , b

_n

} と表すこともある . 定理 2.2 の証明 

[p

H

≥ 1/3 について ]

^∀

p < 1/3, θ(p) = 0 を示せばよい .

今, 一般に γ

_n

で原点を出発する長さ n の路 (みち) を表すことにして, 1 つ固定すると P

p

(γ

n

⊂ C

O

) = P

p

(X

b

= 1,

^∀

b ∈ γ

n

) = p

ⁿ

.

またこの路 γ

_n

の数が 4 · 3

ⁿ⁻¹

を超えないことに注意して , X

∞

n=1

P

_p

(

^∃

γ

_n

⊂ C

_O

) ≤ 4 X

∞ n=1

3

ⁿ⁻¹

p

ⁿ

(< ∞ if p < 1/3) .

ここで k C

_O

k = ∞ なら

^∀

N ≥ 1,

^∃

n ≥ N;

^∃

γ

_n

⊂ C

_O

とできるから , p < 1/3 なら , 上のことから Borel- Cantelli の補題を用いて

θ(p) = P

p

( k C

O

k = ∞ ) ≤ P

p



 \

N≥1

[

n≥N

{

^∃

γ

n

⊂ C

O

}



 = 0.

従って p

_H

≥ 1/3 が成り立つ.

[p

H

≤ 2/3 について ]

^∀

p > 2/3, θ(p) > 0 を示せばよい .

まず N ≥ 1 に対し , V

_N

:= { (m, n) ∈ Z

²

; | m | ∨ | n | := max( | m | , | n | ) ≤ N } として , その中のボンド全体 を V

N

とおく . p > 2/3 のとき N = N(p) を十分大きくとると S = { b ∈ B

²

; X

b

= 1 } に対して ,

P

p

(S は V

N

から無限に伸びる連結成分をもつ ) ≥ 1

2 (1)

が成り立つ. これを認めると, 左辺の集合が { X

_b

; b 6∈ V

_N

} のみに依存し, { X

_b

; b ∈ V

_N

} とは独立であるこ とから

P

p

¡ { X

b

= 1,

^∀

b ∈ V

N

} ∩ { S は V

N

から無限に伸びる連結成分をもつ } ¢

= P

_p

(X

_b

= 1,

^∀

b ∈ V

_N

)P

_p

(S は V

_N

から無限に伸びる連結成分をもつ)

≥ 1

2 P

p

(X

b

= 1,

^∀

b ∈ V

N

) = p

^4N2

2 > 0.

明らかに P

_p

( k C

_O

k = ∞ ) ≥ ( 左辺 ) で , これから p > 2/3 なら θ(p) > 0, 即ち , p

_H

≤ 2/3 をえる .

最後に (1) を示す . Z

²

の裏格子 (Z

²

)

^∗

:= { (m + 1/2, n + 1/2); m, n ∈ Z } を用いる . (Z

²

)

^∗

のボンド b

^∗

∈ (B

²

)

^∗

と b ∈ B

²

は互いに直交するという関係で 1 対 1 に対応する . そこで X

b^∗

:= X

b

とおけば独 立な確率変数の系 { X

_b∗

; b

^∗

∈ (B

²

)

^∗

} = { X

_b∗

; b ∈ B

²

} ができる. もし k C

_O

k < ∞ なら C

_O

を取り囲む (B

²

)

^∗

内の閉じた路 (closed path) γ

^∗

が存在する . そこで原点 O の代わりに V

N

を考えると ,

P

_p

(S は V

_N

から無限に伸びる連結成分をもたない)

= P

_p

(V

_N

を囲む (B

²

)

^∗

内の閉じた路 γ

^∗

が存在する)

≤ X

γ^∗;

V

N

を囲む路

P

_p

(X

_b∗

= 0,

^∀

b

^∗

∈ γ

^∗

)

今 , k γ

^∗

k = k とすると V

N

を囲むことから k ≥ 4(2N + 1) = 8N + 4 ( ≥ 8N ) で , 更に γ

^∗

は必ず [0, k] × { 0 } と交わるから ( 即ち , { (j + 1/2, 1/2); 1 ≤ j ≤ k } のどれかの点を通るから ) γ

^∗

の数は , かなり多く見積もっ ても k · 4 · 3

^k−1

を超えない . 従って

P

_p

(S は V

_N

から無限に伸びる連結成分をもたない ) ≤ X

k≥8N

4k · 3

^k−1

(1 − p)

^k

.

p > 2/3 なら N → ∞ のとき , 右辺は 0 に収束する ( → 問 ). よってこのとき N = N (p) を十分大きくと れば (1) が成り立つ.

問 2.2   [0 ≤

^∀

p < 1/3, θ(p) = 0 ⇒ p

H

≥ 1/3] と [2/3 <

^∀

p ≤ 1, θ(p) > 0 ⇒ p

H

≤ 2/3] を示せ . 問 2.3   p > 2/3 なら P

k≥1

k3

^k−1

(1 − p)

^k

< ∞ を示せ . 問 2.4   θ(p) は右連続であることを示せ .

ヒント 前に考えた

Z

bと

S(p) = { b ∈ B

²

; Z

b

≤ p }

^を用いて

θ(p+h) = P (S (p + h)

の原点を含む連結成分は無限

)

と表されて

, h ↓ 0

なら

S(p + h) ↓ S(p), i.e., T

h>0

S(p + h) = S(p)

より

(

示せ

), θ(p + h) ↓ θ(p) (h ↓ 0)

をえる

.

別のやり方としては

, θ

n

(p) = P

p

( k C

O

k ≥ n)

が連続で

(p

の多項式となるから

), θ

n

(p) ↓ θ(p) (n → ∞ )

からも示せる

.

問

2.5

 一般に

f

n

(x)

を

[0, 1]

上の連続関数として

f

n

↓ f (

各点収束

)

なら

f(x)

は

[0, 1]

で右連続であることを示せ

.

3 ^{ランダムウォーク} (Random Walks)

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

Z

^d

( 3 j = (j

₁

, . . . , j

_d

)) を d 次元格子 (lattice) という.

(X

n

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

_n

= X

_n

− X

_n−1

(n ≥ 1) とすると { X

₀

, Y

₁

, Y

₂

, . . . } は独立で , { Y

n

} は同分布をもち ,

P(Y

n

= k) = 1/(2d) ( | k | = 1), = 0 ( | k | 6 = 1) をみたす . ここで k = (k

1

, . . . , k

d

), | k | = p

k

²₁

+ · · · + k

²_d

. また { X

0

, Y

1

, Y

2

, . . . } が独立とは , 任意の自然 数 n と k

₀

, k

₁

, . . . , k

_n

∈ Z に対し,

P (X

₀

= k

₀

, Y

₁

= k

₁

, . . . , Y

_n

= k

_n

) = P (X

₀

= k

₀

)P (Y

₁

= k

₁

) · · · P (Y

_n

= k

_n

) をみたすときをいう .

一般に Z

^d

上の分布 { p

k

}

k∈Z^d

(p

k

≥ 0, P

p

k

= 1) が与えられているとき , これを 1 歩の分布として運動 する (X

_n

, P ) を単に, d 次元ランダムウォークという. つまり P (Y

_n

= k) = p

_k

(n ≥ 1, k ∈ Z

^d

) をみたして いる . また P

j

(X

1

= k

1

, . . . , X

n

= k

n

) := P(X

1

= k

1

, . . . , X

n

= k

n

| X

0

= j) で P

j

を定義して (X

n

, P

j

) を j を出発する d 次元ランダムウォークという .

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

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

3.1 マルコフ連鎖 (Markov Chains)

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

定理 3.1  可算集合 S に値をとる既約で時間的一様なマルコフ連鎖は正再帰的か , 零再帰的か , 過渡 的のいずれかの状態になる.

さて数学が一般に嫌われるのは, 「同じ日本語なのに聞いていて, チンプンカンプンで理解不能だから」

と良く言われるが , 初めて聞く人にとってはこれがまさにそうだろう . 原因は単純で , それは数学用語の定 義が分っていないからである.

「既約」「時間的一様」「マルコフ連鎖」「正再帰的」「零再帰的」「過渡的」

マルコフ連鎖とは , 次にどう動くかが , 現在の状況のみに依存して , 過去には無関係であるようなものを いうが, いい加減な表現をすれば「行き当りばったりプロセス」あるいは「その場しのぎプロセス」といっ ても良いだろう . 正確な定義は次のとおりである .

S を可算集合として , S に値をとる確率過程 (X

_n

, P ) = (X

_n

(ω), P (dω)) (n = 0, 1, 2, . . .) が次をみたす

ときマルコフ連鎖 (Markov Chain) という :

(M1) [ マルコフ性 ] n ≥ 1, j

0

, j

1

, . . . , j

n

, k ∈ S に対し ,

P (X

_n+1

= k | X

₀

= j

₀

, X

₁

= j

₁

, . . . , X

_n

= j

_n

) = P(X

_n+1

= k | X

_n

= j

_n

).

さらに次の性質をみたすとき時間的一様なマルコフ連鎖という . (M2) [時間的一様性] n ≥ 1, j, k ∈ S に対し,

P (X

n+1

= k | X

n

= j) = P (X

1

= k | X

0

= j).

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

X

0

の分布 µ = { µ

j

} ; µ

j

= P (X

0

= j) を初期分布 (initial distribution) といい , 特に , ある j ∈ S に 対し, P(X

₀

= j) = 1 のとき確率 P を P

_j

で表し, (X

_n

, P

_j

) を j を出発するマルコフ連鎖という. (これは P (X

0

= j) > 0 のとき , P

j

( · ) := P( · | X

0

= j) で定義するというのと同じことで , 実際に計算するときは こちらの方が都合が良い .)

n ≥ 0, j, k ∈ S に対し , q

_j,k⁽ⁿ⁾

= P (X

n

= k | X

0

= j) とおき , Q

⁽ⁿ⁾

= (q

_j,k⁽ⁿ⁾

) を n 階推移確率 ( 行列 ) (n-step transition probability (matrix)), 特に , Q

⁽¹⁾

を Q = (q

j,k

) で表し , 単に , 推移確率 ( 行列 ) と いう.

問 3.1  次を示せ . (i) q

_j,k⁽ⁿ⁾

≥ 0, P

k

q

_j,k⁽ⁿ⁾

= 1 (j ∈ S), (ii) n ≥ 1, j

0

, j

1

, . . . , j

n

∈ S に対して

P (X

0

= j

0

, X

1

= j

1

, . . . , X

n

= j

n

) = µ

j0

q

j0,j1

· · · q

j_n−1,jn

, (iii) m, n ≥ 1, j

₁

, . . . , j

_m

, k

₀

, k

₁

, . . . , k

_n

∈ S に対して

P (X

n+1

= j

1

, . . . , X

n+m

= j

m

| X

0

= k

0

, X

1

= k

1

, . . . , X

n

= k

n

) = q

kn,j1

q

j1,j2

· · · q

j_m−1,jm

. (iv) Q

⁽⁰⁾

= I := (δ

jk

) ( 単位行列 ), Q

⁽ⁿ⁾

= Q

ⁿ

(n ≥ 1), 但し , δ

jk

= 1 (j = k), = 0 (j 6 = k).

問 3.2  初期分布を µ = { µ

_j

} とするとき X

_n

の分布が次で与えられることを示せ.

P(X

n

= k) = X

j∈S

µ

j

q

⁽ⁿ⁾_j,k

.

今, j ∈ S への再帰時間 (recurrence time): T

_j

を次で定義する:

T

j

= inf { n ≥ 1; X

n

= j } (= ∞ if {·} = ∅ ).

• j が再帰的 (recurrent) ⇐⇒

^def

P

_j

(T

_j

< ∞ ) = 1,

• j が過渡的 (transient) ⇐⇒

^def

P

j

(T

j

< ∞ ) < 1

と定義する . また j が再帰的のとき , T

_j

は有限な整数値となるが , さらに

• j が正再帰的 (positive-recurrent) ⇐⇒

^def

E

_j

[T

_j

] < ∞ ,

• j が零再帰的 (null-recurrent) ⇐⇒

^def

E

j

[T

j

] = ∞ , P

j

(T

j

< ∞ ) = 1

と定義する . ここで E

j

[T

j

] は T

j

の P

j

のもとでの平均で , 次で定義される : E

_j

[T

_j

] =

X

∞ m=1

mP

_j

(T

_j

= m) + ∞ · P

_j

(T

_j

= ∞ ).

全ての j が再帰的 (or 正再帰的, 零再帰的, 過渡的) なら (X

_n

) は再帰的 (or 正再帰的, 零再帰的, 過渡 的 ) であるという .

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

マルコフ連鎖 { X

n

} あるいは推移確率 Q = (q

j,k

) とある確率分布 π = { π

j

} に対して

• π が定常分布 (stationary distribution) ⇐⇒

^def

π

k

= P

j

π

j

q

j,k

(k ∈ S),

• π が可逆分布 (reversible distribution) ⇐⇒

^def

π

_k

q

_k,j

= π

_j

q

_j,k

(j, k ∈ S) と定義する.

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

(i) 初期分布 π が定常分布なら , 全ての n ≥ 1 に対し , X

n

の分布も π となる .

(ii) 初期分布 π が可逆分布なら , { X

n

} は時間反転性をもつ : 任意の n ≥ 1, j

0

, . . . , j

n

∈ S に対し , P(X

₀

= j

₀

, . . . , X

_n

= j

_n

) = P(X

₀

= j

_n

, . . . , X

_n

= j

₀

).

マルコフ連鎖 { X

n

} あるいは推移確率 Q = (q

j,k

) が既約 (irreducible) であるとは任意の j, k に対し , ある n ≥ 1 が存在し , q

_j,k⁽ⁿ⁾

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

次の事実が時間的一様なマルコフ連鎖に対する , 本節のメインの結果である : 定理 3.2   j, k ∈ S とする .

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

X

∞ n=0

q

_j,j⁽ⁿ⁾

= ∞ .

b) P

j

( { X

n

} は j に無限回戻る ) = 1.  

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

a) X

∞ n=0

q

_j,j⁽ⁿ⁾

< ∞ .

b) P

_j

( { X

_n

} は j に無限回戻る ) = 0.

(iii) { X

n

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

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

_j

) [

^∀

k, P

j

π

j

q

j,k

= π

k

] が存在することで , このとき π

j

= 1/E

j

[T

j

] で与えられる ( 従って定常分布は存在すれば

一意にきまる ).

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

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

問 O-1   m, n ≥ 1, j

₁

, . . . , j

_m

, k

₀

, k

₁

, . . . , k

_n

∈ S に対して

P (X

n+1

= j

1

, . . . , X

n+m

= j

m

| X

0

= k

0

, X

1

= k

1

, . . . , X

n

= k

n

)

= P(X

n+1

= j

1

, . . . , X

n+m

= j

m

| X

n

= k

n

).

問 O-2  事象列 { B

_k

}

ⁿk=1

が互いに素で, 事象 A, C に対し, P(A | B

_k

) = P (A | C) (1 ≤ k ≤ n) をみた しているとする . このとき P (A | S

B

k

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

命題 3.1   (i) j ∈ S が再帰的なら P

j

( { X

n

} は j に無限回戻る ) = 1.

(ii) j ∈ S が過渡的なら P

_j

( { X

_n

} は j に無限回戻る ) = 0.

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

m 回目に j に戻る時間を T

_j^(m)

とおく .

T

_j⁽¹⁾

= T

_j

, T

_j^(m)

= min { n > T

_j^(m−1)

; X

_n

= j } (= ∞ if {·} = ∅ ).

まず P

j

(T

_j^(m)

< ∞ ) = P

j

(T

j

< ∞ )

^m

を示す . 自然数 s, t に対し , マルコフ性と時間的一様性を用いて , P

_j

(T

_j^(m)

= s + t | T

_j^(m−1)

= s) = P

_j

(T

_j

= t)

が示せて (実際, [左辺]= P (X

_s+t

= j, X

_s+u

6 = j (1 ≤ u ≤ t − 1) | T

_j^(m−1)

= s) で, { X

_u

6 = j } = S

ku∈S;ku6=j

{ X

u

= k

u

} と { T

_j^(m−1)

= s } が { X

1

, . . . , X

s

(= j) } の状態によって決まることに注意して , 上 の 2 つの問 O-1, O-2 を用いれば良い .) これと P (A ∩ B ) = P (B | A)P (A) より

P

j

(T

_j^(m−1)

= s, T

_j^(m)

= s + t) = P

j

(T

_j^(m−1)

= s)P

j

(T

j

= t) をえる . よって

P

_j

(T

_j^(m)

< ∞ ) = P

_j

(T

_j^(m−1)

< T

_j^(m)

< ∞ )

= X

∞ s=m−1

X

∞ t=1

P

_j

(T

_j^(m−1)

= s, T

_j^(m)

= s + t)

= P

j

(T

_j^(m−1)

< ∞ )P

j

(T

j

< ∞ ) より, P

_j

(T

_j^(m)

< ∞ ) = P

_j

(T

_j

< ∞ )

^m

が分かる. これより

P

j

( { X

n

} は j に無限回戻る ) = P

j

( \

m

{ T

_j^(m)

< ∞} )

= lim

m→∞

P

j

(T

_j^(m)

< ∞ )

= lim

m→∞

P

j

(T

j

< ∞ )

^m

.

これは P

_j

(T

_j

< ∞ ) = 1 なら 1, そうでないなら 0 である .

再帰的 , 過渡的の判定定理の証明のためにまずいくつか記号を定義する . j, k ∈ S に対し , f

_j,k^(m)

:= P

j

(T

k

= m) (m ≥ 1) とおき

Q

jk

(s) :=

X

∞ n=0

q

⁽ⁿ⁾_j,k

s

ⁿ

( | s | < 1), F

jk

(s) :=

X

∞ m=1

f

_j,k^(m)

s

ⁿ

( | s | ≤ 1) とおく . それぞれ { q

⁽ⁿ⁾_j,k

}

ⁿ≥0

, { f

_j,k^(m)

}

^m≥1

の母関数 (generating functions) という . lim

s↑1

Q

jk

(s) =

X

∞ n=0

q

_j,k⁽ⁿ⁾

と F

jk

(1) = P

j

(T

k

< ∞ ) に注意せよ . 補題 3.1   j, k ∈ S に対し , 次が成り立つ :

q

_j,k⁽ⁿ⁾

= X

n m=1

f

_j,k^(m)

q

_k,k^(n−m)

(n ≥ 1), Q

_jk

(s) = δ

_jk

+ F

_jk

(s)Q

_kk

(s) ( | s | < 1).

証明  { T

k

= m } = { X

m

= k, X

s

6 = k (1 ≤ s ≤ m − 1) } に注意して X

n

m=1

f

_j,k^(m)

q

⁽ⁿ_k,k^−m)

= X

n

m=1

P

j

(T

k

= m)P

j

(X

n

= k | X

m

= k)

= X

n m=1

P

j

(T

k

= m)P

j

(X

n

= k | T

k

= m)

= X

n m=1

P

_j

(X

_n

= k, T

_k

= m)

= P

_j

(X

_n

= k)

= q

⁽ⁿ⁾_j,k

. またこれを用いて ( 更に和の順序交換

X

∞ n=1

X

n m=1

= X

∞ m=1

X

∞ n=m

も )

Q

jk

(s) = δ

jk

+ X

∞ n=1

q

_j,k⁽ⁿ⁾

s

ⁿ

= δ

_jk

+ X

∞ n=1

X

n m=1

f

_j,k^(m)

q

_k,k^(n−m)

s

ⁿ

= δ

_jk

+ F

_jk

(s)Q

_kk

(s).

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

X

∞ n=0

q

⁽ⁿ⁾_j,j

= ∞ .

証明 上の補題より Q

jj

(s)(1 − F

jj

(s)) = 1 ( | s | < 1) が成り立つから F

jj

(1) = P

j

(T

j

< ∞ ) と lim

s↑1

Q

jj

(s) =

X

∞ n=0

q

⁽ⁿ⁾_j,j

≤ ∞ に注意して s ↑ 1 とすれば分かる . ( 形式的に次のように表せる :

X

∞ n=0

q

_j,j⁽ⁿ⁾

(1 − P

_j

(T

_j

< ∞ )) = 1.

これから P

j

(T

j

< ∞ ) = 1 なら X

∞ n=0

q

_j,j⁽ⁿ⁾

= ∞ , P

j

(T

j

< ∞ ) < 1 なら X

∞ n=0

q

⁽ⁿ⁾_j,j

< ∞ .)

問 3.6  上の証明を参考に j 6 = k のときを考えることにより j ∈ S 過渡的 ⇒ X

n=0

q

_k,j⁽ⁿ⁾

< ∞ (

^∀

k ∈ S)

を示せ. (当然, この対偶: [

^∃

k ∈ S; X

n=0

q

_k,j⁽ⁿ⁾

= ∞ ⇒ j : 再帰的] も成り立つ.) ( P

n

q

⁽ⁿ⁾_k,j

= F

_kj

(1) P

n

q

_j,j⁽ⁿ⁾

を用いる.) 補題 3.2   j が再帰的のとき j → k [i.e.,

^∃

n; q

⁽ⁿ⁾_j,k

> 0] なら P

k

(T

j

< ∞ ) = 1.

証明 まず , 任意の i, j ∈ S に対して , 次が成り立つ . P

_i

(T

_j

< ∞ ) = q

_i,j

+ X

k∈S;k6=j

q

_i,k

P

_k

(T

_j

< ∞ ).

( 実際 , マルコフ性と時間的一様性より [ 後 , P

i

(A | B) = P (A | B ∩ { X

0

= i } ) ( → 確めよ .) も ]

P

_i

(T

_j

= n | X

₁

= k) = P(T

_j

= n | X

₀

= i, X

₁

= k) = P (T

_j

= n | X

₁

= k) = P

_k

(T

_j

= n − 1) で , これか ら P

i

(X

1

= k, T

j

= n) = q

i,k

P

k

(T

j

= n − 1) をえて

P

i

(T

j

< ∞ ) = X

∞ n=1

X

k∈S

P

i

(X

1

= k, T

j

= n) = P

i

(X

1

= j) + X

∞ n=2

X

k6=j

P

i

(X

1

= k, T

j

= n) に代入することにより分かる .)

今 , 仮定の q

_j,k⁽ⁿ⁾

> 0 より

^∃

(k

1

, . . . , k

n−1

); q

j,k1

q

k1,k2

q

k2,k3

· · · q

k_n−1,k

> 0 に注意して上で得た式で , i = j とすると j の再帰性より,

^∀

k; q

_j,k

> 0 に対し, P

_k

(T

_j

< ∞ ) = 1 が分かる. k = k

₁

として, 再び上の式で i = k

1

として , k = k

2

に対し , q

k1,k2

> 0 より , P

k2

(T

j

< ∞ ) = 1 が分かる . これを繰り返して , 題意を得 る .

問 3.7  前の問 3.6 と上の補題から次が成り立つことを示せ : j 再帰的 , かつ j → k ⇒ X

n=0

q

⁽ⁿ⁾_k,j

= ∞ .

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

命題 3.3   j, k ∈ S; j ↔ k に対し , 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,k

q

_k,j^(m)

(n ≥ 0) より

Q

jj

(s) = X

∞ n=0

q

⁽ⁿ⁾_j,j

s

ⁿ

≥ X

∞ n=0

q

^(l+m+n)_j,j

s

^l+m+n

≥ s

^l+m

q

_j,k^(l)

q

^(m)_k,j

Q

kk

(s).

これからもし j が過渡的なら

lim

s↑1

Q

_jj

(s) = X

∞ n=0

q

⁽ⁿ⁾_j,j

< ∞

で , 上の不等式から X

∞ n=0

q

⁽ⁿ⁾_k,k

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

次に正再帰性について考える . 補題 3.1 の Q

jj

(s)(1 − F

jj

(s)) = 1 より F

_jj⁰

(s) = Q

⁰_jj

(s)/Q

jj

(s)

²

. よって j を正再帰的とすると

lim

s↑1

Q

⁰_jj

(s)

Q

jj

(s)

²

= F

_jj⁰

(1 − ) = E

_j

[T

_j

] < ∞ . さらに上と同様に

Q

_kk

(s) ≥ s

^l+m

q

^(m)_k,j

q

^(l)_j,k

Q

_jj

(s), Q

⁰_jj

(s) ≥

X

∞ n=0

(l + m + n)s

^l+m+n−1

q

_j,j^(l+m+n)

≥ s

^l+m

q

^(l)_j,k

q

_k,j^(m)

Q

⁰_kk

(s) が分かるので

Q

⁰_kk

(s)

Q

_kk

(s)

²

≤ 1

s

^3(l+m)

(q

^(l)_j,k

)

³

(q

^(m)_k,j

)

³

Q

⁰_jj

(s) Q

_jj

(s)

²

. をえる. 従って

E

_k

[T

_k

] = F

_kk⁰

(1 − ) = lim

s↑1

Q

⁰_kk

(s) Q

kk

(s)

²

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

問 3.8   k ∈ S が正再帰的のとき E

k

[T

k

] = F

_kk⁰

(1 − ) を確かめよ .

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

• 再帰的なら

^∀

j, k ∈ S に対し , P

n

q

_j,k⁽ⁿ⁾

= ∞ .

• 過渡的なら

^∀

j, k ∈ S に対し , P

n

q

_j,k⁽ⁿ⁾

< ∞ . 逆に, ある j, k ∈ S に対し, P

n

q

_j,k⁽ⁿ⁾

が無限なら再帰的となり, 有限なら過渡的となる.

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

(X

n

, P ) を d 次元ランダムウォークとする . 即ち , { p

k

}

k∈Z^d

を Z

^d

上の分布として , { X

0

, X

1

− X

0

, X

2

− X

₁

, . . . } が独立で, P (X

_n

− X

_n−1

= k) = p

_k

(n ≥ 1, k ∈ Z

^d

) をみたすとする. (特に p

_k

= 1/(2d) のとき 単純ランダムウォークという .)

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

_j,k

) は q

_j,k

= p

_k−j

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

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

_n

, P ) を d 次元ランダムウォークとする.

(i) X

n+1

− X

n

と (X

0

, X

1

, . . . , X

n

) が独立であることを示せ , i.e.,

P(X

_n+1

− X

_n

= j, X

₀

= k

₀

, X

₁

= k

₁

, . . . , X

_n

= k

_n

)

= P (X

_n+1

− X

_n

= j)P (X

₀

= k

₀

, X

₁

= k

₁

, . . . , X

_n

= k

_n

).

特に k

0

, k

1

, . . . , k

n−1

∈ Z

^d

で和をとることにより , X

n+1

− X

n

と X

n

が独立であることも分る .

(ii) P(X

n+1

= j | X

0

= k

0

, X

1

= k

1

, . . . , X

n

= k

n

) = P (X

n+1

= j | X

n

= k

n

) = p

j−kn

を示せ . これから { X

_n

} が時間的一様なマルコフ連鎖で, q

_j,k

= p

_k−j

も分る.

(iii) 単純ランダムウォークは既約的であることを示せ . ( k j − k k := | j

1

− k

1

| + · · · + | j

d

− k

d

| を用いて j 6 = k, j = k で分けて考える .)

従って , この Q = (q

j,k

) = (p

k−j

) を用いて , 正再帰性 , 零再帰性 , 過渡性について議論することができる . まず、前節の結果を用いることにより, 単純ランダムウォークに関しては次のことが比較的容易に分る:

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

(i) d = 1, 2 なら零再帰的 (i.e., E

j

[T

j

] = ∞ かつ P

j

(T

j

< ∞ )) であり , (ii) d ≥ 3 なら過渡的である .

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

まず既約性により ( 正・零 ) 再帰的か過渡的のいずれかに分れるから , q

_0,0⁽ⁿ⁾

の n についての和の収束・発 散を調べればよい . 奇数歩で出発点に戻ってくることは無いから , q

_0,0⁽²ⁿ⁺¹⁾

= 0 で , 偶数歩の q

_0,0⁽²ⁿ⁾

について 考えればよい . そこで次を示す . ( これにより再帰的か過渡的かは前節の定理 3.2 により判定できる .)

命題 3.4   d 次元単純ランダムウォークの推移確率 Q = (q

_j,k

) に対して (i) d = 1, 2 のとき n → ∞ なら

q

_0,0⁽²ⁿ⁾

∼ ( 1/ √

πn (d = 1) 1/(πn) (d = 2) ここで a

_n

∼ b

_n

(n → ∞ ) ⇐⇒

^def

a

_n

/b

_n

→ 1 (n → ∞ ) である.

(ii) d = 3 なら適当な正の数 C に対して

q

_0,0⁽²ⁿ⁾

≤ Cn

^−3/2

.

問 3.10  一般に正の値をとる数列 { a

n

} , { b

n

} 対して , a

n

∼ b

n

(n → ∞ ) なら

^∃

c

1

, c

2

> 0; c

1

b

n

≤ a

n

≤ c

₂

b

_n

(

^∀

n ≥ 1) が成り立つこと示せ.

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

(3/π)

³

/4) q

⁽²ⁿ⁾_0,0

∼ 2

^1−d

d

^d/2

(πn)

^−d/2

(n → ∞ ).

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

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

2πn

^n+1/2

e

⁻ⁿ

(n → ∞ ).

命題 3.4 の証明

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

⁽²ⁿ⁾_0,0

=

µ 2n n

¶

2

⁻²ⁿ

∼ 1

√ πn (n → ∞ ).

d = 2 のときは

q

_0,0⁽²ⁿ⁾

= X

j,k≥0;j+k=n

(2n)!

(j!k!)

²

4

⁻²ⁿ

= µ 2n

n

¶ X

n j=0

µ n k

¶

2

4

⁻²ⁿ

で , さらに X

n j=0

µ n k

¶

2

= µ 2n

n

¶

を用いれば 1 次元の結果から分る . d = 3 のときは

q

_0,0⁽²ⁿ⁾

= X

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

(2n)!

(j!k!m!)

²

6

⁻²ⁿ

で , 3 項展開公式より

q

⁽²ⁿ⁾_0,0

≤ c

n

(2n)!

n! 3

ⁿ

6

⁻²ⁿ

をえる . ここで c

n

= max

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

(j!k!m!)

⁻¹

である . さらにこの c

n

に対し , 次が成り立つことか ら, 再びスターリングの公式を用いれば題意をえる.

c

n

≤ c3

^n+3/2

n

^−n−3/2

e

ⁿ

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

c

n

≤

 



 

(m!)

⁻³

(n = 3m)

(m!)

⁻²

((m + 1)!)

⁻¹

(n = 3m + 1) (m!)

⁻¹

((m + 1)!)

⁻²

(n = 3m + 2)

(3)

が分るので , スターリングの公式より , ある定数 c

1

, c

2

> 0 が存在して c

1

n

^n+1/2

e

⁻ⁿ

≤ n! ≤ c

2

n

^n+1/2

e

⁻ⁿ

をみたすので上に代入すればよい.

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

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

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

命題 3.5   d = 1, 2 のとき Z

^d

上の単純ランダムウォ−クは零再帰的 (i.e., E

0

[T

0

] = ∞ ) である . 補題 3.3   (i) α > − 1 のとき

X

∞ n=1

n

^α

s

ⁿ

∼ Γ(α + 1)

(1 − s)

^α+1

(s ↑ 1).

(ii) α = − 1 のとき

X

∞ n=1

n

⁻¹

s

ⁿ

= log 1 1 − s .

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

_∞

0

x

^α

s

^x

dx = µ

log 1 s

¶

₋α−1

Γ(α + 1).

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

命題 3.5 の証明

命題 3.3 の証明で示したように E

₀

[T

₀

] = lim

s↑1

F

₀₀⁰

(s), F

₀₀⁰

(s) = Q

⁰₀₀

(s)/Q

₀₀

(s)

²

であるから, d = 1 のと き , q

_0,0⁽²ⁿ⁾

∼ 1/ √

πn (n → ∞ ) より , 上の補題を用いて s ↑ 1 のとき Q

00

(s) = 1 +

X

∞ n=1

s

²ⁿ

q

_0,0⁽²ⁿ⁾

∼ 1 + X

∞ n=1

s

²ⁿ

1

√ πn ∼ 1

√ π

Γ(1/2) (1 − s

²

)

^1/2

,

Q

⁰₀₀

(s) = X

∞ n=1

2ns

²ⁿ⁻¹

q

_0,0⁽²ⁿ⁾

∼ X

∞ n=1

2ns

²ⁿ⁻¹

1

√ πn ∼ 2

√ π

Γ(3/2) (1 − s

²

)

^3/2

. よって

F

₀₀⁰

(s) = Q

⁰₀₀

(s) Q

00

(s)

²

∼ 2 √

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

²

1 s √

1 − s

²

(s ↑ 1).

ゆえに

E

₀

[T

₀

] = lim

s↑1

F

₀₀⁰

(s) = ∞ . d = 2 なら q

⁽²ⁿ⁾_0,0

∼ 1/(πn) (n → ∞ ) より, 同様に s ↑ 1 のとき

Q

00

(s) ∼ 1

π log 1 1 − s

²

, Q

⁰₀₀

(s) ∼ 2

πs(1 − s

²

) ∼ 2 π(1 − s

²

) から

E

₀

[T

₀

] = lim

s↑1

2

"

π(1 − s

²

) µ

log 1 1 − s

²

¶

2

#

₋1

= ∞ .