ランダムウォークの再帰性に関する研究

ランダムウォークの再帰性に関する研究

三重大学大学院教育学研究科教育科学専攻 理数生活系教育領域

217M014

2019

2

8

はじめに

本研究の目的は，ランダムウォークの再帰性を判定することにある．

第1章ではまず，ランダムウォークとマルコフ連鎖に関する基本事項を説明する．ランダムウォークとは，格 子空間上を1歩ごとにランダムに方向を定めて動く確率モデルであり最も基本的な確率過程の1つである．マ ルコフ連鎖とは，マルコフ性と時間的一様性の2つの性質を持った確率過程である．このとき，ランダムウォー クはマルコフ連鎖になっている．ランダムウォークが確率1で出発点に戻るかどうか判定する条件を与え，再 帰性と過渡性をはじめとした言葉を準備し，ランダムウォークが再帰的であるための必要十分条件に関する定理 の証明をする．

第2章では，第1章で証明した定理を用いてランダムウォークの再帰性を判定する．そのために必要となる 推移確率の無限和の値を直接求めることは困難であるため，スターリングの公式を用いて推移確率の漸近オー ダーを求めることでランダムウォークの再帰性を判定する．初めにZ^d上の単純ランダムウォークの再帰性を判 定する．その結果をもとに1次元・2次元非対称単純ランダムウォークの再帰性を判定する．次に「その点に留 まる」場合を加えた1次元ランダムウォークの再帰性を考える．右に1歩進む確率をp，左に1歩進む確率を q，その点に留まる確率をrとすると，この1次元ランダムウォークの再帰性はp, q, rの値の取り方によって決 まる．

目次

1 マルコフ連鎖とランダムウォーク 3

1.1 d次元ランダムウォーク . . . 3

1.2 マルコフ連鎖. . . 4

2 ランダムウォークの再帰性 14 2.1 d次元単純ランダムウォークの再帰性の判定 . . . 14

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

2.3 2次元非対称単純ランダムウォーク . . . 17

2.4 特殊な１次元ランダムウォーク . . . 19

1

1.1 d

d≥1を次元をあらわす自然数，Z^dをd次元立方格子の空間とする．すなわち，

Z^d=Z× · · · ×Z={j= (j1,· · ·, jd) :jp (1≤p≤d)は整数}

Z^dの各点は2d個の隣接点をもつが，Z^dの点jから出発し，毎回2d個の隣接点の中から1点をランダムに選 んで1歩ずつ進む運動をjから出発したd次元単純ランダムウォークという．

j ∈ Z^d から出発した単純ランダムウォークのn歩目の位置を X(n)として，n 歩目の変位をY(n) = X(n)−X(n−1) (n≥1)であらわすと，(Y(n))n=1,2,···は独立かつ同分布をもつ確率ベクトルの列で，その分 布は

P(Y(n) =k) = {1

2d (|k|= 1) 0 (|k| ̸= 1) である．ここでは|k|^はk= (k₁,· · ·, k_d)の長さ，すなわち|k|=√

k₁²+· · ·+k_d²をあらわす．

したがって(X(n))_{n=0,1,2,···}はZ^dに値をとる確率過程として

X(0) =j, X(n) =j+Y(1) +· · ·+Y(n) (1.1.1) をみたしている．

以下では，出発点jを明示するために，確率PをPj であらわす．

一般にZ^d上の確率分布{pj}j∈Z^dが与えられたとき，これを1歩の分布としてランダムに進む運動をd次 元ランダムウォークという．このときn歩目の位置X(n)は，独立で同じ分布{pj}をもつ確率ベクトルの列 (Y(n))n=1,2,···を用いて(1.1.1)により与えられる．したがって

P(Y(n) =k) =pk (n≥1, k∈Z^d) (1.1.2) をみたしている．

(1.1.1)，(1.1.2)により定まるd次元ランダムウォーク(X(n))n=0,1,2,···に対し

P_j(X(n) =k) =Q⁽ⁿ⁾(j,k) (n≥0, j,k∈Z^d) (1.1.3) とおき，Q⁽ⁿ⁾= (Q⁽ⁿ⁾(j,k))をn−ステップ推移確率行列という．とくにQ⁽¹⁾=Qを推移確率行列という．

このとき

(Q1) Q⁽⁰⁾=I (単位行列)

(Q2) Q⁽ⁿ⁾=Q⁽ⁿ⁻¹⁾Q=Q× · · · ×Q

(Q3) Q⁽ⁿ⁾(j,k) =Q⁽ⁿ⁾(O,k−j) (n≥0, j,k∈Z^d) が成り立つ．(Q2)の右辺は行列としての積をあらわす．

d次元ランダムウォーク(X(n))n=0,1,2,···に対し，点k∈Z^dへの到達時間Tkを次で定める．

Tk=min{n≥1 :X(n) =k} (1.1.4)

ただしX(n)̸=k(n≥1)のときはT_k=∞^とする．

とくにk=j(=X(0))の場合にはT_j は出発点jへ初めて戻ってくる時間を意味する．ここでT_kはランダ ムなので確率変数であることに注意する．

ランダムウォーク(X(n))n=0,1,2,···に対し

Pj(Tj <∞) = 1

が成り立つときj∈Z^dは再帰的であるという．また，j∈Z^dは再帰的でなければ，過渡的であるという．

1.2

本節では，ランダムウォークより一般的な確率過程であるマルコフ連鎖を導入し，それに対する再帰性を判定 する条件を考える．

Sは一般に有限または可算無限集合とし，その要素をj, k,· · · ^{であらわす．}Sに値をとる確率過程(X(n))が 次の条件をみたすとき，マルコフ連鎖という．

(M1) n≥0, j0, j1,· · ·, jn, k∈Sに対し

P(X(n+ 1) =k|X(0) =j0, X(1) =j1,· · ·, X(n) =jn) =P(X(n+ 1) =k|X(n) =jn) (M2) n≥0, j, k∈Sに対し

P(X(n+ 1) =k|X(n) =j) =P(X(1) =k|X(0) =j)

(M1)はn+ 1歩目の位置はn歩目の位置に依存する確率法則で定まり，n−1歩目までの歩き方にはよらない ことを意味する．この性質をマルコフ性という．また，(M2)は推移確率法則が時間的に一定であることを意味 し，時間的一様性という．

ここで注意として，条件付き確率P(A|B)はP(B)>0をみたす事象B∈ F ^に対し P(A|B) = P(A∩B)

P(B) (A∈ F)

として定めた(Ω,F)上の確率測度である．したがって(M1)はP(X(0) =j₀, X(1) =j₁,· · · , X(n) =j_n)>0 のときに意味を持つ関係式であり，(M2)も同様に理解する．

マルコフ連鎖(X(n))に対してX(0)の分布を初期分布という．それをu={u_j}^{であらわすと} uj =P(X(0) =j) (j∈S)

とくにP(X(0) =j) = 1のとき，(X(n))n=0,1,2,···はjを出発点とするマルコフ連鎖といい，そのとき確率 P の代わりにPjを用いる．

n≥, j, k∈Sに対し

P(X(n) =k|X(0) =j) =Q⁽ⁿ⁾(j, k) (1.2.5) とおき，Q⁽ⁿ⁾= (Q⁽ⁿ⁾(j, k))をnステップ推移確率行列，とくにQ⁽¹⁾ =Qを単に推移確率行列という．した がって(M1),(M2)から

n≥1, j₀, j₁,· · · , j_n, k∈Sに対して

P(X(n+ 1) =k|X(0) =j0, X(1) =j1,· · ·, X(n) =jn) =Q(jn, k) (1.2.6) 命題 1.1. マルコフ連鎖(X(n))の初期分布をµ，推移確率行列をQとするとき

(i) Q⁽⁰⁾=I (単位行列)，Q⁽ⁿ⁾=

z }|n {

Q× · · · ×Q (n≥1) (ii) n≥1, k₀, k₁, k₂· · · , k_n∈Sに対して

P(X(0) =k0, X(1) =k1X(2) =k2,· · ·, X(n) =kn) =µ(k0)Q(k0, k1)Q(k1, k2)· · ·Q(kn−1, kn) (iii) n≥1, m≥1, j0, j1, j2· · ·, jn∈S, k1, k2· · · , km∈Sに対して

P(X(n+l) =k_l (1≤l≤m)|X(h) =j_h (0≤h≤n))

=Pj_n(X(l) =kl (1≤l≤m))

=Q(jn, k1)Q(k1, k2)· · ·Q(km−1, km)

(iv) Q⁽ⁿ⁾(j, k)≥0 (j, k∈S)かつ

∑

k∈S

Q⁽ⁿ⁾(j, k) = 1 (j∈S) 証明. (i)の証明

Q⁽⁰⁾(j, k) =P(X(0) =k|X(0) =j) = {

1 (k=j) 0 (k̸=j) であるからQ⁽⁰⁾=I (単位行列)である．また，

Q⁽²⁾(j, k) =P(X(2) =k|X(0) =j)

= ∑

k₁∈S

P(X(2) =k|X(1) =k1)P(X(1) =k1|X(0) =j)

= ∑

k1∈S

P(X(1) =k|X(0) =k1)P(X(1) =k1|X(0) =j)

= ∑

k₁∈S

Q(k₁, k)Q(j, k₁)

右辺はQ×Qの(j, k)成分であるからQ⁽²⁾ =Q×Qである．n= 3以降も同様に確かめられる．

(ii)の証明 (1.2.6)を用いると

P(X(0) =k0, X(1) =k1, X(2) =k2,· · · , X(n) =kn)

=P(X(0) =k₀, X(1) =k₁, X(2) =k₂,· · · , X(n−1) =k_n−1)Q(k_n−1, k_n)

=P(X(0) =k0)Q(k0, k1)Q(k1, k2)· · ·Q(kn−1, kn)

=µ(k0)Q(k0, k1)Q(k1, k2)· · ·Q(kn−1, kn) (iii)の証明

P(X(n+l) =kl(1≤l≤m)|X(h) =jh(0≤h≤n))

=P(X(n+l) =k_l(1≤l≤m)|X(n) =j_n)

=P(X(l) =kl(1≤l≤m)|X(0) =jn)

=Pj_n(X(l) =kl(1≤l≤m))

=Q(j_n, k₁)Q(k₁, k₂)· · ·Q(k_m−1, k_m) (iv)は(ii)および(1.2.5)より明らか．

初期分布をµとするとき(1.2.5)からX(n)の分布は P(X(n) =k) =∑

j∈S

µjQ⁽ⁿ⁾(j, k) (1.2.7)

一般にS上の確率分布π={πj}は次の条件をみたすとき，マルコフ連鎖(X(n))または推移確率行列(Q(j, k)) の定常分布という．

πk =∑

j∈S

πjQ(j, k) (k∈S) (1.2.8)

また，S上の確率分布π={π_j}^は

πkQ(k, j) =πjQ(j, k) (j, k∈S) (1.2.9) をみたすとき，マルコフ連鎖(X(n))または推移確率行列(Q(j, k))の可逆分布という．

一般に可逆分布は定常分布である．なぜなら(1.2.9)の両辺でjについて和をとれば(1.2.8)をみたすからで ある．

命題 1.2. (i) π = {πj} ^は(Q(j, k))の定常分布とする．マルコフ連鎖(X(n))の初期分布がπならば，

n≥1に対してX(n)の分布もπに一致する．

(ii) π={πj}^は(Q(j, k))の可逆分布とする．マルコフ連鎖(X(n))の初期分布がπならば(Xn())の確率法 則は次の意味で時間反転対称性をもつ；

任意のn≥1, j₀, j₁, j₂,· · · , j_n∈Sに対し

P(X(0) =j₀, X(1) =j₁, X(2) =j₂,· · ·, X(n) =j_n)

=P(X(0) =jn, X(1) =jn−1, X(2) =jn−2,· · ·, X(n) =j0) 証明. (i)の証明 (1.2.7)および(1.2.8)より，k∈Sに対して

P(X(n) =k) =∑

j∈S

πjQ⁽ⁿ⁾(j, k)

=∑

j∈S

∑

k1,k2,···,k_n−1∈S

πjQ(j, k1)Q(k1, k2)· · ·Q(kn−1, k)

= ∑

k1,k2,···,k_n−1∈S

πk1Q(k1, k2)· · ·Q(kn−1, k)

= ∑

k₂,k₃,···,k_n−1∈S

π_k2Q(k₂, k₃)· · ·Q(k_n−1, k)

=πk

となり，X(n)の分布もπに一致する．

(ii)の証明 命題1.1(ii)と(1.2.9)を用いると，j0, j1,· · ·, jn∈Sに対し P(X(0) =j0, X(1) =j1,· · ·, X(n) =jn)

=πj₀Q(j0, j1)Q(j1, j2)· · ·Q(jn−1, jn)

=πj1Q(j1, j0)Q(j1, j2)· · ·Q(jn−1, jn)

=πj_nQ(jn, jn−1)Q(jn−1, jn−2)· · ·Q(j1, j0)

=P(X(0) =j_n, X(1) =j_n−1, X(2) =j_n−2,· · ·, X(n) =j₀)

再帰性と過渡性

ランダムウォークの場合と同様に，k∈Sへの到達時間Tkを(1.1.4)により定める．とくに，出発点がjな らば，Tjは出発点へ初めて戻る時間であり再帰時間という．点j∈Sが

Pj(Tj<∞) = 1 (1.2.10)

をみたすとき，jは再帰的といい，任意のj ∈S が再帰的ならば，マルコフ連鎖(X(n))または推移確率行列 Q= (Q(j, k))は再帰的という．また，j∈Sが(1.2.10)をみたさないとき，すなわち

Pj(Tj=∞)>0

をみたすときjは過渡的という．jが再帰状態ならば再帰時間T_jは有限正値確率変数であるが，さらに E(T_j)<∞

ならばjを正再帰的という．それとは反対に，jは再帰的で E(T_j) =∞

ならばjを零再帰的という．任意のj∈Sが過渡的（正再帰的，零再帰的）のとき，マルコフ連鎖(X(n))また は推移確率行列Q= (Q(j, k))はそれぞれ過渡的（正再帰的，零再帰的）という．

既約性

2つの状態j, k∈Sに対し，あるn≥0が存在して

Q⁽ⁿ⁾(j, k)>0

をみたすとき，j →kとあらわす．これはjから出発するマルコフ連鎖(X(n))が正の確率でkに到達できる ことを意味する．とくに，任意のj, k∈Sに対しj →kをみたすときマルコフ連鎖(X(n))または推移確率行 列(Q(j, k))は既約という．

j, k∈Sに対し

f_jk^(m)=Pj(Tk =m) (m≥1) とおくと

Pj(Tk<∞) =

∑∞ m=1

f_jk^(m) (1.2.11)

これより，jの再帰性は

∑∞ m=1

f_jk^(m)= 1 と同値である．

{Q⁽ⁿ⁾(j, k)}n≥0および{f_jk^(m)}m≥1の母関数を次式で定める．

Q_jk(s) =

∑∞ n=0

Q⁽ⁿ⁾(j, k)sⁿ (|s|<1)

Fjk(s) =

∑∞ n=1

f_jk⁽ⁿ⁾sⁿ (|s| ≤1) (1.2.12) Qjk(s)およびFjk(s)はそれぞれ|s|<1，|s| ≤1で収束する．さらに

F_jk(1) =P_j(T_k<∞) である．

命題 1.3. (i) j, k∈S, n≥1に対して

Q⁽ⁿ⁾(j, k) =

∑n m=1

f_jk^(m)Q^(n−m)(k, k) (ii) j, k∈Sに対して

Qjk(s) =δjk+Fjk(s)Qkk(s) (|s|<1) ここでδ_jk= 0(j̸=k), δ_jj = 1である．

証明. 2つの事象列{A_n},{B_n}^{を次で定める．}

An= [X(n) =k]

Bn = [X(n) =k, X(l)̸=k(1≤l≤n−1)]

B_nはマルコフ連鎖(X(n))においてn−^{ステップ目に初めて}kに到達するという事象である．

Pj(An) =Q⁽ⁿ⁾(j, k), Pj(Bn) =f_jk⁽ⁿ⁾

であることに注意して，命題1.1とマルコフ性を用いると

P_j(A_n∩B_m) =P_j(B_m)P_j(A_n|B_m)

=f_jk^(m)Q^(n−m)(k, k) (1≤m≤n) また，{B_m}m=1,2,···は排反事象列で

∪n m=1

(An∩Bm) =An

だから(i)が成り立つ．さらに(i)を用いると Q_jk(s) =δ_jk+

∑∞ n=1

Q⁽ⁿ⁾(j, k)sⁿ

=δjk+

∑∞ n=1

∑n m=1

f_jk^(m)Q^(n−m)(k, k)s^ms^n−m

=δjk+

∑∞ m=1

∑∞ n=m

f_jk^(m)Q^(n−m)(k, k)s^ms^n−m

=δjk+

∑∞ m=1

∑∞ i=0

f_jk^(m)Q⁽ⁱ⁾(k, k)s^msⁱ

=δjk+

∑∞ m=1

f_jk^(m)s^m

∑∞ i=0

Q⁽ⁱ⁾(k, k)sⁱ

=δ_jk+F_jk(s)Q_kk(s) となり(ii)が成り立つ．

定理 1.4. j∈Sが再帰状態であるための必要十分条件は

∑∞ n=0

Q⁽ⁿ⁾(j, j) =∞ (1.2.13)

証明. 単調収束定理および(1.2.11)により F_jj(1) =

∑∞ m=1

f_jj^(m)=P_j(T_j <∞),

slim→1Qjj(s) =

∑∞ n=0

Q⁽ⁿ⁾(j, j)≤ ∞ が成り立つ．また命題1.3(ii)により

Q_jj(s)(1−F_jj(s)) = 1 (|s|<1) だからs→1とすれば(1.2.13)は

Pj(Tj <∞) =Fjj(1) = 1 と同値になるので定理1.4は証明された．

定理 1.5. (i) j∈Sが再帰状態ならば

P_j((X(n))はjに無限回戻る) = 1 (ii) j∈Sが過渡状態ならば

Pj((X(n))はjに無限回戻る) = 0

証明. m≥1に対し，m回目にjに戻る時間をT_j^(m)とおく．すなわち

T_j⁽¹⁾=T_j, T_j^(m)=min{n > T_j^(m−1):X(n) =j}

ただし，T_j^(m−1) = ∞^またはT_j^(m−1) < ∞^{ではあるが，任意の} n > T_j^(m−1) に対してX(n) ̸= j ならば T_j^(m)=∞^{と定める．}

m≥1に対し

Pj(T_j^(m)<∞) =Pj(Tj<∞)^m (1.2.14) を示す．命題1.1(iii)を用いると

P_j(T_j^(m)=l+n|T_j^(m−1)=l)

=Pj(X(l+h)̸=j (1≤h < n), X(l+n) =j|T_j^(m−1)=l)

=P_j(X(h)̸=j (1≤h < n), X(n) =j)

=Pj(Tj =n) だから

P_j(T_j^(m−1)=l, T_j^(m)=l+n) =P_j(T_j^(m−1)=l)P_j(T_j =n) したがって

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

=

∑∞ l=m

∑∞ n=1

Pj(T_j^(m−1)=l, T_j^(m)=l+n)

=

∑∞ l=m

∑∞ n=1

Pj(T_j^(m−1)=l)Pj(Tj=n)

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

となり，これより(1.2.14)が成り立つ．さらに，事象列{[T_j^(m)<∞]}m=1,2,···は単調減少列であるから Pj((X(n))はjに無限回戻る) =Pj

( _∞

∩

m=1

[T_j^(m)<∞] )

= lim

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

= lim

m→∞P_j(T_j<∞)^m

この値はjが再帰的か過渡的かによって1または0である．ゆえに定理1.5が証明された．

命題 1.6. jは再帰状態でかつj→kならば，

P_k(T_j <∞) = 1 証明. 任意のi, j∈Sに対し

Pi(Tj<∞) =Q(i, j) + ∑

l∈S,l̸=j

Q(i, l)Pl(Tj<∞) (1.2.15) を示す．

[T_j=n] = [X(m)̸=j (1≤m < n), X(n) =j]

に注意して命題1.1を用いると，l̸=j, n≥2のとき Pi(X(1) =l, Tj=n)

=Pi(X(1) =l, X(m)̸=j (1< m < n), X(n) =j)

=Q(i, l)P_l(X(m)̸=j (0< m < n−1), X(n−1) =j)

=Q(i, l)Pl(Tj =n−1)

l∈S, n≥1について和をとると

P_i(T_j <∞) =

∑∞ n=1

∑

l∈S

P_i(X(1) =l, T_j =n)

=Q(i, j) +

∑∞ n=2

∑

l∈S,l̸=j

Q(i, l)P_l(T_j =n−1)

=Q(i, j) + ∑

l∈S,l̸=j

Q(i, l)P_l(T_j <∞)

ゆえに(1.2.15)が成り立つ．いま(1.2.15)でi=jとするとjは再帰状態であるから(1.2.15)の右辺 = 1と なる．したがってQ(i, l)>0をみたす任意のlについてP_l(T_j <∞) = 1が成り立つ．次に(1.2.15)でi=l にとり同様に考えると，Q(l, r) > 0 をみたす任意のr についてもPr(Tj < ∞) = 1 が成り立つ．すな わちQ⁽²⁾(j, r) > 0をみたす任意の rについてもPr(Tj < ∞) = 1 が成り立つ．この議論を繰り返せば Q⁽ⁿ⁾(j, k)>0をみたす任意のkについてもPk(Tj<∞) = 1が成り立つ．よってj →kをみたす任意のkに 対してもPk(Tj<∞) = 1である．

命題 1.7. j, k∈Sがj→kかつk→jをみたすとする．そのときj ∈Sが過渡的，または正再帰的，零再帰 的ならばそれに対応してk∈Sもそれぞれ過渡的，または正再帰的，零再帰的である．したがって，既約なマル コフ連鎖は過渡的，正再帰的，零再帰的のいずれかになる．

証明. j→k, k→jをみたすのでl≥0, m≥0が存在し

Q^(l)(j, k)>0かつQ^(m)(k, j)>0

Q^(l+m+n)(j, j)≥Q^(l)(j, k)Q⁽ⁿ⁾(k, k)Q^(m)(k, j) (n≥0) より

Q_jj(s)≥s^l+mQ^(l)(j, k)Q^(m)(k, j)Q_kk(s) (1.2.16) さてjが過渡的ならば，定理1.4により

slim→1Qjj(s) =

∑∞ n=0

Q⁽ⁿ⁾(j, j)<∞ となるので(1.2.16)から

∑∞ n=0

Q⁽ⁿ⁾(k, k)<∞

となりkも過渡的である．またkとjを取り替えて考えればkが過渡的ならばjも過渡的になる．ゆえにjの 再帰性とkの再帰性も一致する．

次にjが正再帰的であると仮定してkも正再帰的であることを示す．jの再帰性から

E(T_j) =F_jj^′ (1−)<∞ (1.2.17)

命題1.3の関係式

Qjj(s)(Fjj(s)−1) + 1 = 0 (0< s <1) の微分をとると

F_jj^′ (s) = Q^′_jj(s) Qjj(s)² したがって

 lim

s→1

Q^′_jj(s)

Q_jj(s)²=F_jj^′ (1−) =E(T_j)<∞ (1.2.18)

また(1.2.16)と同様に

Qkk(s)≥s^l+mQ^(m)(k, j)Q^(l)(j, k)Qjj(s)

Q^′_jj(s)≥

∑∞ n=0

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

≥s^m+l−1Q^(l)(j, k)Q^(m)(k, j)Q^′_kk(s) をみたすので

Q^′_kk(s)

Qkk(s)²≤ 1

s^3(m+l)−1Q^(m)(k, j)³Q^(l)(j, k)³ Q^′_jj(s) Qjj(s)² ゆえに(1.2.18)によって

E(Tk) = lim

s→1

Q^′_kk(s) Q_kk(s)²<∞

となりkも正再帰的である．またkとjを取り替えて考えればkが正再帰的ならばjも正再帰的になる．この ようにjの正再帰性とkの正再帰性も一致する．

定理1.8. 既約なマルコフ連鎖が正再帰性をもつための必要十分条件は定常分布が存在することである．そのと き，定常分布πは一意に定まり

πj= 1

E(T_j) (j∈S) (1.2.19)

証明. 正再帰性を仮定すると，命題1.3により lim

s→1(1−s)Q_jj(s) = lim

s→1

1−s

1−Fjj(s) (1.2.20)

= 1

F_jj^′ (1−)

= 1

E(Tj)

1≤E(T_j)<∞だからこの値は正の有限値である．また，命題1.3により任意のi∈S, j∈Sは Qij(s) =δij+Fij(s)Qjj(s)

をみたす．さらに命題1.6によりFij(1) = 1だから，(1.2.20)によって

slim→1(1−s)Qij(s) = 1

E(T_j) (1.2.21)

ここで(1.2.21)の右辺をπjとおく． ∑

j∈S

(1−s)Qij(s) = 1 (1.2.22)

に注意して(1.2.21)およびファトウの補題を用いると

∑

j∈S

πj ≤1 さらにファトウの補題を用いて

∑

j∈S

πjQ(j, k)≤lim inf

s→1

∑

j∈S

(1−s)Qij(s)Q(j, k)

= lim

s→1(1−s)

∑∞ n=0

sⁿQ⁽ⁿ⁺¹⁾(i, k)

= lim

s→1(1−s)s⁻¹(Qik(s)−δik)

=πk

となるので ∑

j∈S

πjQ(j, k)≤πk (1.2.23)

(1.2.23)の両辺のkについての和は一致するので

∑

j∈S

πjQ(j, k) =πk (k∈S)

次に{πj}が確率分布になることを示す．両辺にQ⁽ⁿ⁻¹⁾を右からかけると，任意のn≥1に対し

∑

j∈S

π_jQ⁽ⁿ⁾(j, k) =π_k (k∈S) (1.2.24)

よって

∑

j∈S

πj(1−s)Qjk(s) = (1−s)

∑∞ n=0

∑

j∈S

sⁿπjQ⁽ⁿ⁾(j, k) (1.2.25)

=πk (k∈S)

(1.2.26) (1.2.22)より(1−s)Qjk(s)≤1 (j, k∈S)に注意して，(1.2.21)とあわせるとs→1のときルベーグの収束定

理が適用できる．ゆえに ∑

j∈S

πjπk=πk

が成り立つ．したがって ∑

j∈S

πj = 1 となり，(1.2.24)とあわせるとπ={π_j}^{は定常分布となる．}

次にπ={πj}を任意の定常分布と仮定すると(1.2.24)をみたすので，既約性の仮定から任意のj∈Sに対 しπj >0がわかる．そのとき(1.2.25)は容易に確かめられる．そこでs→1として(1.2.21)を用いると

πk =∑

j∈S

πj

1

E(T_k)= 1 E(T_k) となるのでπ={π_j}^{は一意に定まる．}

命題 1.9. ランダムウォーク(X(n))はマルコフ連鎖である．

証明. マルコフ性(M1)と時間的一様性(M2)を調べる．Y(n+ 1) =kとする．(Y(n))の独立性に注意すると

，n≥0,j0,j1,· · ·,jn∈Z^dに対して

Pj0(X(n+ 1) =jn+k|X(1) =j1,· · · , X(n) =jn)

= P_j0(X(n+ 1) =j_n+k, X(1) =j₁,· · ·, X(n) =j_n) Pj₀(X(1) =j1,· · ·, X(n) =jn)

= Pj₀(Y(n+ 1) =k, Y(1) =j1−j0,· · · , Y(n) =jn−jn−1) Pj₀(Y(1) =j1−j0,· · ·, Y(n) =jn−jn−1)

= Pj₀(Y(n+ 1) =k)Pj₀(Y(1) =j1−j0,· · ·, Y(n) =jn−jn−1) P_j0(Y(1) =j₁−j₀,· · · , Y(n) =j_n−j_n−1)

=Pj₀(Y(n+ 1) =k)

=P_j0(X(n+ 1) =j+k|X(n) =j_n)

となり，マルコフ性が確かめられた．次に，n≥0, j, k∈Z^dに対して P_j(X(n+ 1) =j+k|X(n) =j)

=Pj(Y(n+ 1) =k|X(0) +Y(1) +· · ·+Y(n) =j)

=P_j(Y(n+ 1) =k, X(0) +Y(1) +· · ·+Y(n) =j) Pj(X(0) +Y(1) +· · ·+Y(n) =j)

=Pj(Y(n+ 1) =k)Pj(X(0) +Y(1) +· · ·+Y(n) =j) P_j(X(0) +Y(1) +· · ·+Y(n) =j)

=Pj(Y(n+ 1) =k)

=Pj(Y(1) =k)

=P_j(X(1) =j+k|X(0) =j)

となり，時間的一様性が確かめられた．よってランダムウォークはマルコフ連鎖である．

2

2.1 d

d次元単純ランダムウォークはd= 1,2のとき零再帰的，d≥3のとき過渡的であることはよく知られている

（志賀徳造『ルベーグ積分から確率論』参照)．本節では，定理1.4を用いて，Z^d上のd次元単純ランダムウォー ク(X(n))の再帰性を判定する．d次元単純ランダムウォーク(X(n))のnステップ 推移確率Q⁽ⁿ⁾(j,j)はj に依存しないので，原点Oの再帰性を判定すれば十分である．

定理 2.1. d次元単純ランダムウォークは (i) d= 1のとき，再帰的である．

(ii) d= 2のとき，再帰的である．

(iii) d≥3のとき，過渡的である．

証明. (i)の証明 ∑_∞

n=1Q⁽ⁿ⁾(0,0) =∞^{となることを示す．}X(0) = 0とする．奇数歩では出発点0に戻れな いことに注意する．X(2n) = 0となるためには，2n歩のうちn歩は右へ，残りのn歩は左へ進むことになる．

このような歩みの個数は ^(2n)!_(n!)2 個だから

Q⁽²ⁿ⁾(0,0) = (2n)!

(n!)²2⁻²ⁿ Q⁽²ⁿ⁺¹⁾(0,0) = 0

よって，∑_∞

n=1Q⁽²ⁿ⁾(0,0) =∞となることを示せばよい．スターリングの公式 n!∼√

2πnⁿ⁺¹²e⁻ⁿ (n→ ∞) を適用すると

Q⁽²ⁿ⁾(0,0) = (2n)!

(n!)²2⁻²ⁿ

∼

√2π(2n)²ⁿ⁺¹²e⁻²ⁿ (√

2πnⁿ⁺¹²e⁻ⁿ)² 2⁻²ⁿ (n→ ∞)

=2²ⁿ⁺¹²n²ⁿ⁺¹²

√2πn²ⁿ⁺¹ 2⁻²ⁿ

= 1

√πn が成り立つ．これより∑_∞

n=1Q⁽²ⁿ⁾(0,0) =∞^{となるので，}1次元単純ランダムウォークは再帰的である．

(ii)の証明 このとき進む方向は上下左右の4方向である．Oから出発してX(2n) =Oとなるためには，左 右が同じ歩数，上下が同じ歩数となることが必要かつ十分である．そこで左右をそれぞれk歩，上下をそれぞ れl歩としてk+l =nをみたす2n歩の歩き方の個数を数えればよい．そのような歩みはそれぞれ4⁻²ⁿの確 率で出現するので，したがって

Q⁽²ⁿ⁾(O,O) = ∑

k,l≥0,k+l=n

(2n)!

(k!l!)²4⁻²ⁿ

= (2n

n )∑n

k=0

(n k

)2

4⁻²ⁿ

ここで

∑n k=0

(n k

)2

= (2n

n )

であるから

Q⁽²ⁿ⁾(O,O) = (2n

n )2

4⁻²ⁿ

∼π⁻¹n⁻¹ (n→ ∞) となり，∑_∞

n=1π⁻¹n⁻¹=∞^{であるから}∑_∞

n=1Q⁽²ⁿ⁾(O,O) =∞^{をみたすので}2次元単純ランダムウォーク は再帰的である．

(iii)の証明 1歩で2d方向のうち1つを選ぶのでd= 1,2のときと同様に考えると

Q⁽²ⁿ⁾(O,O) = ∑

ki≥0 (i=1,2,···,d),k1+k2+···+kd=n

(2n)!

(k₁!k₂!· · ·k_d!)²(2d)⁻²ⁿ

となる．n=dNのとき，次式の左辺は, k1+k2+· · ·+kd=dNの下では，k1=k2=· · ·=kd=N のとき 最大になり 

1

k1!k2!· · ·kd!≤ 1

(N!)^d (2.1.27)

である．実際，N! =∫_∞

0 t^Ne^−tdtにおいて，t^N =t^kd1t^kd2 · · ·t^kdd と分けて，ヘルダーの不等式を用いれば N!≤(k₁!k₂!· · ·k_d!)^d1

となる．したがって(2.1.27)が成り立つ．(2.1.27)とd項展開公式 dⁿ= (1 + 1 +· · ·+ 1)^d = ∑

ki≥0 (i=1,2,···,d),k1+k2+···+kd=n

n!

k₁!k₂!· · ·k_d! を用いると，

Q⁽²ⁿ⁾(O,O) = ∑

k_i≥0 (i=1,2,···,d),k₁+k₂+···+k_d=n

(2n)!

n! · 1

k1!k2!· · ·kd!· n!

k1!k2!· · ·kd!·(2d)⁻²ⁿ

≤ (2n)!

n! · 1

(N!)^d·dⁿ·(2d)⁻²ⁿ

= (2n)!

n! · 1

{(ⁿ_d)!}^d·dⁿ·(2d)⁻²ⁿ

∼

√2π(2n)²ⁿ⁺¹²e⁻²ⁿ

√2πnⁿ⁺¹²e⁻ⁿ · 1 {√

2π(ⁿ_d)^nd+12e^−nd}^d·dⁿ·(2d)⁻²ⁿ (n→ ∞)

=√ 2

( d 2πn

)^d₂

(2.1.28) となる．また，n=dN−M (M = 1,2,· · ·, d−1)のとき

Q^(2dN)(O,O) = ∑

j∈Z^d

Q^(2dN−2M)(O,j)Q^(2M)(j,O)

≥Q^(2dN−2M)(O,O)Q^(2M)(O,O)

≥Q^(2dN−2M)(O,O)·(2d)^−2M (2.1.29) であるから，(2.1.28)，(2.1.29)より

Q^(2dN−2M)(O,O)≤(2d)^2MQ^(2dN)(O,O)

≤(2d)^2dQ^(2dN)(O,O)

≤(2d)^2d√ 2

( d 2πn

)^d₂