確率過程論基礎
笠原
初到達時間
定義
状態空間 S = {0, 1, 2, . . .} を持つ離散時間マルコフ連鎖 {Xn : n ≥ 0} を考える．
このマルコフ連鎖の遷移確率行列を P = (pij )，初期確率分布ベクトルを
a = (a0 , a1 , . . .) とする．X0 = i (i = 1, 2, . . .) のとき，このマルコフ連鎖が初め
て状態 0 を訪れるまでの時間
T = min{n ≥ 0 : Xn = 0}
を初到達時間 (first passage time) と呼ぶ．
63
確率過程論基礎
笠原
ここで行列 B を
B = (pij ),
i, j ≥ 1
で定義する．B は P の部分行列となっていることに注意する．


p01 p02 · · ·
p

 00



 p10


P =

B

 p20

 .
..
以降では，初到達時間 T に関する以下の諸量について考察する．
1. T の補分布：Pr{T > n}, n ≥ 0
2. 最終的に状態 0 を訪れる確率：Pr{T < ∞}
3. T の k 次モーメント：E[T k ]
4. T の母関数：ψ(z) = E[z T ]
64
確率過程論基礎
笠原
T の補分布
i ∈ S に対し，以下の記号を定義する．
vi (n)
=
Pr{T > n|X0 = i},
v(n)
=
Pr{T > n}.
このとき，v(n) は次式で与えられる．
v(n) =
∑
ai vi (n)
i∈S
定理 2.21 v(n) = (v1 (n), v2 (n), . . .)⊤ (⊤ は転置) とすると，v(n) は次式を満
足する．
v(n) = B n e,
n ≥ 0.
(19)
ここで e = (1, 1, . . .)⊤ である．
65
確率過程論基礎
笠原
証明
vi (n)
=
Pr{T > n|X0 = i}
∞
∑
=
Pr{T > n|X1 = j, X0 = i} · Pr{X1 = j|X0 = i}
j=0
=
∞
∑
pij · Pr{T > n|X1 = j, X0 = i}
j=0
= pi0 · Pr{T > n|X1 = 0, X0 = i} +
∞
∑
pij · Pr{T > n|X1 = j, X0 = i}
j=1
ここで事象 {X1 = 0} は事象 {T = 1} と等価であることから，n ≤ 1 に対して
Pr{T > n|X1 = 0, X0 = i} = 0.
66
確率過程論基礎
笠原
よって
vi (n) =
∞
∑
pij · Pr{T > n|X1 = j, X0 = i}
j=1
=
∞
∑
pij · Pr{T > n|X1 = j}
(マルコフ性)
j=1
=
∞
∑
pij · Pr{T > n − 1|X0 = j}
(斉時性)
j=1
=
∞
∑
pij vj (n − 1)
j=1
これより行列表現の次式を得る．
v(n) = B · v(n − 1),
n ≥ 1.
(20)
上式を繰り返し用いることにより
v(n) = B n · v(0),
n ≥ 1.
67
確率過程論基礎
笠原
i ≥ 1 に対し，事象 {X0 = i} は T ≥ 1 を意味し，vi (0) = 1 となることから
v(0) = e
また，B 0 = I (I は単位行列) より，n ≥ 0 に対して (19) 式が成立する．
(21)
68
確率過程論基礎
笠原
例 2.2 以下の遷移確率で表現される 2 状態 S = {1, 2} を持つ離散時間マルコフ
連鎖を考える．


α
1−α

,
P =
0 ≤ α, β ≤ 1.
1−β
β
1−α
α
1
2
β
1−β
初期状態が 2 のとき，T を状態 1 への初到達時間とする．このとき B = (β) と
なり，
v2 (n) = Pr{T > n|X0 = 2} = β n , n ≥ 0
を得る．これより
Pr{T = n|X0 = 2} = v2 (n − 1) − v2 (n) = β n−1 (1 − β),
n≥0
となり，T が幾何分布となることがわかる．
69
確率過程論基礎
笠原
吸収確率
vi (n) = Pr{T > n|X0 = i} は n について単調非減少かつ有界であるから，極限
vi = lim vi (n)
n→∞
が存在する．このとき ui = 1 − vi = Pr{T < ∞|X0 = i} は，マルコフ連鎖が状
態 i から始まって最終的に状態 0 を訪問する確率となる．特に，0 から 0 への遷
移確率が p00 = 1 のとき，ui を吸収確率 (absorption probability) と呼ぶ．
定理 2.22 v = limn→∞ v(n) とするとき，v は
v = Bv
(22)
かつ v ≤ e を満足する最大の解で与えられる．
70
確率過程論基礎
笠原
証明
(20) 式 v(n) = Bv(n − 1) の両辺に対して n → ∞ とすると，(22) を得る．
今，w ≤ e を (22) 式をみたす別の解とする．(21) より
v(0) = e ≥ w
を得る．ここで k = 0, 1, . . . , n に対して
v(k) ≥ w
を仮定する．w = Bw であり，かつ B は非負行列であることから
v(n + 1) = Bv(n) ≥ Bw = w
となり，帰納法によって v(n) ≥ w がすべての n ≥ 0 に対して成立する．結果
として
v = lim v(n) ≥ w
n→∞
が得られ，v が最大解であることが示された．
71
確率過程論基礎
笠原
初到達時間の平均
状態空間 S = {0, 1, 2, . . .} を持つ離散時間マルコフ連鎖 {Xn : n ≥ 0} において，
ui = Pr{T < ∞|X0 = i} = 1 を仮定する．
このとき，T の条件付き期待値を以下のように定義する．
mi = E[T |X0 = i]
また，ベクトル表現 m = (m1 , m2 , . . . , )⊤ を導入する．このとき，以下の定理
が成立する．
定理 2.23 i ≥ 1 に対して ui = 1 を仮定する．このとき，m は
m = e + Bm
(23)
を満足する最小の非負解として与えられる．
72
確率過程論基礎
笠原
証明
mi
= E[T |X0 = i]
∞
∑
=
E[T |X0 = i, X1 = j] · Pr{X1 = j|X0 = i}
j=0
=
∞
∑
pij · E[T |X0 = i, X1 = j]
j=0
ここで
E[T |X0 = i, X1 = 0] = 1
であり，かつ
E[T |X0 = i, X1 = j] = 1 + E[T |X0 = j] = 1 + mj ,
より次式を得る．
mi = 1 +
∞
∑
pij · mj ,
j≥1
i≥1
j=1
上式を行列形式にすると (23) を得る．
m が非負の最小解となるのは定理 2.22 と同様の議論より証明される．
73
確率過程論基礎
笠原
例 2.3 表の出る確率が p，裏の出る確率が q = 1 − p のコインを連続して投げ
る試行を考える．Xn をその時点までに連続して表が出た回数（連）を表す確率
変数とする．X0 = 0 として，初めて k 回連続して表が出るまでの試行回数の平
均を考える．
今，{Xn : n ≥ 0} をマルコフ連鎖として定式化する．例えば k = 3 のときの遷
移確率行列 P は次式で与えられる．

0
1
2
0 q p
1
q 0
P = 
2q 0
3 0 0
3

0 0
p 0


0 p
0 1
状態 3 は吸収状態であることに注意すると，B は次式で与えられる．
0
1
2
0 q

B = 1q
2 q
p
0
0
0

p
0


74
確率過程論基礎
笠原
初到達時間 T を
T = min{n ≥ 0 : Xn = k}
で定義すると，(23) 式より
mi
=
1 + q · m0 + p · mi+1 ,
mk
=
0
上式を再帰的に解くことにより，
(
)
1
+ m0 (1 − pk−i ),
mi =
q
0≤i≤k−1
0≤i≤k−1
上式で i = 0 とおいて，m0 を解くと次式を得る．
(
)
1 1
m0 =
−1
k
q p
75
確率過程論基礎
笠原
初到達時間の平均：有限状態空間の場合
状態空間 S が有限な集合 {0, 1, 2, . . . , N } からなり，状態 0 が吸収状態となって
いるマルコフ連鎖 {Xn : n ≥ 0} を考える．このとき，遷移確率行列 P は次式の
ような構造をもっている．


1
0
···
0




p
p
·
·
·
p
 10
11
1N 


P = .
.
.
.
..
..
.. 
 ..



pN 0
pN 1
···
pN N
ここで過渡的な状態の遷移を支配する遷移確率行列 B は


p
· · · p1N
 11

.
 ..
.
..
.. 
B= .



pN 1 · · · pN N
で与えられることに注意する．
76
確率過程論基礎
笠原
n ステップ遷移確率行列 P (n) は帰納法により


1
0
(n)
n


P
=P =
n
r⊤
B
n
の形になることが証明できる．ここで 0 は要素がすべて 0 の行ベクトル，r ⊤
n は
対応する列ベクトルである．
過渡的な状態 i, j ∈ S \ {0} に対する n ステップ遷移確率の極限は 0 だから，
B n は n → ∞ で零行列に収束する．これより
(I − B)−1 = I + B + B 2 + · · ·
の存在が言える．平均初到達時間ベクトル m は (23) 式より m = e + Bm で与
えられることに注意すると，m は最終的に
m = (I − B)−1 e
で計算できることがわかる．
77
確率過程論基礎
笠原
初到達時間の母関数と高次モーメント
初到達時間 T の確率母関数として次のものを定義する．
ϕi (x) = E[z T |X0 = i] =
∞
∑
z n Pr{T = n|X0 = i},
i≥1
n=0
また，以下のものを定義する．
b
= (p10 , p20 , . . .)⊤
ϕ(z) =
(ϕ1 (z), ϕ2 (z), . . .)⊤
定理 2.24 ベクトル ϕ(z) は次式を満たす最小の解である．z ∈ [0, 1]
ϕ(z) = zb + zBϕ(z)
(24)
78
確率過程論基礎
笠原
証明
ϕi (z) =
=
E[z T |X0 = i]
∞
∑
E[z T |X0 = i, X1 = j] · Pr{X1 = j|X0 = i}
j=0
=
∞
∑
pij · E[z T |X0 = i, X1 = j]
j=0
ここで事象 {X0 = i, X1 = 0} は T = 1 を意味することから
E[z T |X0 = i, X1 = 0] = z
また j ≥ 1 に対し，事象 {X0 = i, X1 = j} が起こった条件の下での T の分布
は，X0 = j から開始したという条件の下での 1 + T の分布と同一になることに
注意すると
E[z T |X0 = i, X1 = j] = E[z 1+T |X0 = j] = zϕj (z)
79
確率過程論基礎
笠原
これら二つの結果から次式を得る．
ϕi (z) = zpi0 + z
∞
∑
pij · ϕj (z)
j=1
上式を行列表現することで最終的に (24) 式を得る．
最小解であることは，定理 2.22 と同様の議論より証明される．
80