第 3 章 応用例
3.1 出生死亡連鎖( Birth and death chains )
特別な連続時間マルコフ連鎖の例として,有限状態空間上の出生死亡連鎖を考える.この 連鎖は,χ={0,· · ·, n},n∈Nの上を右(+方向)か左(−方向)に一歩しか動けない.ここ で,(λi)i≥1と(µi)i≥0を2つの非負値実数列とする.この連鎖が状態 iに居るならば,パラ メータλi+µiをもつ指数分布に従ってiに滞在し,確率λλi
i+µi でi+ 1にジャンプするか,確 率 λµi
i+µi でi−1にジャンプする.また,状態0ならばパラメータλ0をもつ指数分布に従っ て状態 1 にジャンプし,状態nならばパラメータµnをもつ指数分布に従って状態n−1に ジャンプするとする.パラメータλi, µiは,それぞれこのマルコフ連鎖の出生率,死亡率と 呼ばれる.この連鎖のQ-行列Qは
Q=
⎛
⎜⎜
⎜⎜
⎜⎜
⎝
−λ0 λ0
µ1 −(µ1+λ1) λ1
· · · · · ·
µn−1 −(µn−1+λn−1) λn−1
µn −µn
⎞
⎟⎟
⎟⎟
⎟⎟
⎠
で与えられる.この行列から各成分をmaxi{λi+µi}で割ることで,マルコフ核 K を作る.こ のマルコフ核から生成される連続時間マルコフ連鎖を解析し,そのスペクトルギャップを評 価する.そのKを
K=
⎛
⎜⎜
⎜⎜
⎜⎜
⎝
1−b0 bo
a1 1−(a1+b1) b1
· · · · · ·
an−1 1−(an−1+bn−1) bn−1 an 1−an
⎞
⎟⎟
⎟⎟
⎟⎟
⎠
とかく.ここで,
ai = µi
maxi{λi+µi}, bi= λi
maxi{λi+µi}, i= 0,· · · , n 但し,a0 = 0, bn= 0.
とする.
その定常分布πは, π=
π(j) = b0· · ·bj−1
a1· · ·aj π(0), 1≤j≤n
(但し,π(0)は n
j=0π(j) = 1を満たすように決める ) で与えられる.特に,ai,bi = u,(i = 0,· · ·, n),a0 = 0,bn= 0である時,
π(j) = 1 n+ 1 である.
I−K =− 1
maxi{λi+µi}Q
であるから,マルコフ核Kから作られるマルコフ連鎖のスペクトルギャップをλとすると,
Qによって作られるマルコフ連鎖のスペクトルギャップは,maxi{λi+µi}λである. 以下,三つの方法でスペクトルギャップを評価する.
3.1.1 方法I(ナッシュの不等式を利用した方法)
命題 3.1.1. χ={0,· · ·, n}上の上記で定めたマルコフ核Kから作られるマルコフ連鎖に対 するスペクトルギャップλは,
λ≥2 min
b0π(0), b0· · ·bi
a1· · ·ai
π(0) (1≤i≤n)
mini {π(i)} である.
証明 関数gに対して E(g, g) = 1
2
x,y
|g(x)−g(y)|2K(x, y)π(x)
= 1
2
n−1
i=0
|g(i+ 1)−g(i)|2ai+1π(i+ 1) + 1 2
n−1
i=0
|g(i)−g(i+ 1)|2biπ(i)
=
n−1
i=0
|g(i)−g(i+ 1)|2b0· · ·bi a1· · ·aiπ(0)
≥ A
n−1
i=0
|g(i)−g(i+ 1)|2.
但し,
A= min
b0π(0),b0· · ·bi
a1· · ·aiπ(0) (1≤i≤n)
.
また,値域が同一符号にならない関数fに対して, f ∞= sup
x∈χ|f(x)| ≤
n−1 i=0
|f(i+ 1)−f(i)|
が成り立つ.ここで,f = sgn(g)|g|2とおく.このときgの値域も同一符号になる条件が必要 である.
|f(i+ 1)−f(i)| ≤ |g(i+ 1)−g(i)|(|g(i+ 1)|+|g(i)|) であるから,
n−1
i=0
|f(i+ 1)−f(i)| ≤
n−1
i=0
|g(i+ 1)−g(i)|(|g(i+ 1)|+|g(i)|)
≤
n−1
i=0
|g(i+ 1)−g(i)|2
12 n−1
i=0
(|g(i+ 1)|+|g(i)|)2
12
が成り立つ.従って,
g2∞≤212 1
A 1
2 (min
i {π(i)})−12E(g, g)12 g2 が成り立つ.故に,
g42 ≤ g2∞g21
≤ 212 1
A 12
(mini {π(i)})−12E(g, g)12 g2g21 である.従って,
g62≤ 2 Amin
i {π(i)}E(g, g)g41
が成り立つ.新たにg =f −cとする.但しcは π(f > c)≤ 12,π(f < c)≤ 12 とする.この とき,
f −c62≤ 2 Amin
i {π(i)}E(g, g)f−c41≤ 2 Amin
i {π(i)}E(g, g)f 41 である.故に,任意のf に対して
Var(f)3 ≤ 2 Amin
i {π(i)}E(f, f)f 41 が成り立つ.ナッシュ定数CはC= Amin2
i{π(i)} である.定理2.1.3,補題1.5.2から,
λ≥2Amin
i {π(i)} が成り立つ.
特にai=bi=u,a0 = 0, bn= 0 の時,
A= u n+ 1 である.
例題 3.1.2. 例えば,状態空間が5個の場合については, A = b0
Dmin{a1a2a3a4, b1a2a3a4, b1b2a3a4, b1b2b3a4, b1b2b3b4} である,また
mini {π(i)}= 1
Dmin{a1a2a3a4, b0a2a3a4, b0b1a3a4, b0b1b2a4, b0b1b2a4} である.但し,D=a1a2a3a4+b0a2a3a4+b0b1a3a4+b0b1b2a4+b0b1b2b3.
3.1.2 方法II(Kに適合した辺集合を用いる方法)
各(x, y) ∈ Aに対してγ(x, y) ∈Γが唯一存在することに着目し,定理2.2.3を用いる. す なわち,
A= max
e∈A
⎧⎨
⎩ 1 Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|π(x)π(y)
⎫⎬
⎭
とおくと,
λ≥ 1 A が成り立つ.
Aを求めるためには,各辺eに対する 1
Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|π(x)π(y)
の値を計算して最大値をとればよい.しかし,状態空間χ={0,· · · , n}では辺の数が2n個 存在するためnが大きいときは困難である.そこで状態数が5個のときを調べた.
命題 3.1.3. 状態空間χ={0,· · · ,4}上の上記で定めたマルコフ核Kから作られるマルコフ 連鎖に対応するスペクトルギャップλは
λ≥ 1 A
を満たす.但し,
A= 1
Dmax{a2a3a4+ 2b1a3a4+ 3b1b2a4+ 4b1b2b3,
b0a3a4+ 2a1a3a4+ 2b0b2a4+ 3a1b2a3+ 3b0b2a4+ 4a1b2b3, b0b1a4+ 2b0a2a4+ 2b0b1b3+ 3a1a2a4+ 3b0a2b3+ 4a1a2b3, b0b1b2+ 2b0b1a3+ 3b0a2a3+ 4a1a2a3} ,
D=a1a2a3a4+b0a2a3a4+b0b1a3a4+b0b1b2a4+b0b1b2a3. 証明 8 つの辺があり,各々の値を求める.
(i) e= (0,1)のとき Q(e) = 1
2(K(0,1)π(0) +K(1,0)π(1)) = b0a1a2a3a4
D (=b0π(0)),
(0,1)∈γ(x, y)となるパスγ(x, y)は4つあり,γ(0,1), γ(0,2), γ(0,3), γ(0,4)であるから,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y)
= 1
b0π0 {1π(0)π(1) + 2π(0)π(2) + 3π(0)π(3) + 4π(0)π(4)}
=π(0) 1
a1 + 2b1
a1a2 + 3b1b2
a1a2a3 + 4b1b2b3 a1a2a3a4
= 1
D(a2a3a4+ 2b1a3a4+ 3b1b2a4+ 4b1b2b3) である.以下,7つもこれと同様にして求める.
(ii) e= (1,0)のとき Q(e) = 1
2(K(1,0)π(1) +K(0,1)π(0)) = b0a1a2a3a4
D (=b0π(0)),
(1,0)∈γ(x, y)となるパスγ(x, y)は4つあり,γ(1,0), γ(2,0), γ(3,0), γ(4,0)であるから,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y) = 1
b0π0 {1π(0)π(1) + 2π(0)π(2) + 3π(0)π(3) + 4π(0)π(4)}
= 1
D(a2a3a4+ 2b1a3a4+ 3b1b2a4+ 4b1b2b3) である.
(iii) e= (1,2)のとき
Q(e) = 1
2(K(1,2)π(1) +K(2,1)π(2)) = b0b1 a1 π(0),
(1,2)∈γ(x, y)となるパスγ(x, y)は6つあり,γ(0,2), γ(0,3), γ(0,4), γ(1,2), γ(1,3), γ(1,4) である.同様に計算して,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y)
= 1
D(b0a3a4+ 2a1a3a4+ 2b0b2a4+ 3a1b2a4+ 3b0b2a4+ 4a1b2b3) である.
(iv) e= (2,1)のとき
Q(e) = 1
2(K(2,1)π(2) +K(1,2)π(1)) = b0b1 a1 π(0).
(2,1)∈γ(x, y)となるパスγ(x, y)は6つあり,γ(2,0), γ(3,0), γ(4,0), γ(2,1), γ(3,1), γ(4,1) である.同様に計算して,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y)
= 1
D(b0a3a4+ 2a1a3a4+ 2b0b2a4+ 3a1b2a4+ 3b0b2a4+ 4a1b2b3) である.
(v) e= (2,3)のとき
Q(e) = 1
2(K(2,3)π(2) +K(3,2)π(3)) = b0b1b2 a1a2 π(0).
(2,3)∈γ(x, y)となるパスγ(x, y)は6つあり,γ(0,3), γ(0,4), γ(1,3), γ(1,4), γ(2,3), γ(2,4) である.同様に計算して,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y)
= 1
D(b0b1a4+ 2b0a2a4+ 2b0b1b3+ 3a1a2a4+ 3b0a2b3+ 4a1a2b3) である.
(vi) e= (3,2)に対して Q(e) = 1
2(K(3,2)π(3) +K(2,3)π(2)) = b0b1b2 a1a2 π(0).
(3,2)∈γ(x, y)となるパスγ(x, y)は6つあり,γ(3,0), γ(4,0), γ(3,1), γ(4,1), γ(3,2), γ(4,2) である.同様に計算して,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y)
= 1
D(b0b1a4+ 2b0a2a4+ 2b0b1b3+ 3a1a2a4+ 3b0a2b3+ 4a1a2b3)
である.
(vii) e= (3,4)に対して Q(e) = 1
2(K(3,4)π(3) +K(4,3)π(4)) = b0b1b2b3 a1a2a3 π(0).
(3,4)∈γ(x, y)となるパスγ(x, y)は4つで,γ(0,4), γ(1,4), γ(2,4), γ(3,4)である.同様に計 算して
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y) = 1
D(b0b1b2+ 2b0b1a3+ 3b0a2a3+ 4a1a2a3).
(viii) e= (3,4)に対して Q(e) = 1
2(K(4,3)π(4) +K(3,4)π(3)) = b0b1b2b3 a1a2a3 π(0).
(3,4)∈γ(x, y)となるパスγ(x, y)は4つで,γ(0,4), γ(1,4), γ(2,4), γ(3,4)である.同様に計 算して,
ω(e) Q(e)
x,y∈χ:γ(x,y)e
|γ(x, y)|ωπ(x)π(y) = 1
D(b0b1b2+ 2b0b1a3+ 3b0a2a3+ 4a1a2a3).
である.
従って,(i)〜(viii)より A= 1
Dmax{a2a3a4+ 2b1a3a4+ 3b1b2a4+ 4b1b2b3,
b0a3a4+ 2a1a3a4+ 2b0b2a4+ 3a1b2a4+ 3b0b2a4+ 4a1b2b3, b0b1a4+ 2b0a2a4+ 2b0b1b3+ 3a1a2a4+ 3b0a2b3+ 4a1a2b3, b0b1b2+ 2b0b1a3+ 3b0a2a3+ 4a1a2a3} .
となる.
特に,ai, bi =u, a0 = 0, b4= 0のとき,
λ≥ 4 15u である.
3.1.3 方法III(等周定数を用いた方法)
定理2.3.6から,等周定数Iを求めることでスペクトルギャップを評価できる.従って,等
周定数I を定義に従って求める.ここでは,ai, bi =u (0< u≤ 12),a0 = 0, bn= 0である出 生死亡連鎖に対する等周定数Iの値を求める.以下,(A)は集合Aの要素の個数とする.
定理 3.1.4. χ= 0,· · · , n上のマルコフ核
K =
⎛
⎜⎜
⎜⎜
⎜⎜
⎝
1−u u u 1−2u u
· · · · · ·
u 1−2u u u 1−u
⎞
⎟⎟
⎟⎟
⎟⎟
⎠
から作られる連続時間マルコフ連鎖の等周定数Iは,
I = 2u
(n+1) nが奇数のとき
2u
n nが偶数のとき である.
証明 ∂∗A={(x, y)∈ A:x∈A, y ∈Ac}とすると,
Q(∂A) π(A) = 1
2
x∈A,y∈Ac
(K(x, y)π(x) +K(y, x)π(y)) 1
π(A) = (∂∗A) u (n+ 1)
(n+ 1) (A) .
をみたす.π(A)≤ 12を満たすAのうち,この値を最小にするものを考える.まず,Aに含ま れる格子点の数,すなわち(A)を固定したときに,(∂∗A)の値がを最小になるAの形を考 えるが,どんな(A)に対しても(∂∗A) = 1となるAがあるのは明らか.従って,(A)を固 定したもとでは
min
Q(∂A) π(A)
= u
(A)
である.次に(A)を動かし,Iを決定する(A)を調べる.π(A)≤ 12 において,
(A)≤ n+1
2 n:奇数
n2 n:偶数
である.故に,
I = 2u
n+1 n:奇数
2u
n n:偶数
である.
従って,定理2.3.6(チーガー不等式)より, λ≥ I2
8 =
u2
2(n+1)2 n:奇数
u2
2n2 n:偶数
である.
以上で述べた有限状態空間上の連続時間出生死亡連鎖の結果を次の表にまとめた.
条件 方法 方法 方法
状態空間がn+1個 命題3.1.1 —– —–
状態空間がn+ 1個,ai=bi=u 定理3.1.4 (0≤u≤ 12) λ≥ (n2+1)u 2 —– λ≥
u2
2(n+1)2 n:奇数
u2
2n2 n:偶数
状態空間が5個 例題3.1.2 命題3.1.3 —–
状態空間が5個,ai, bi =u (0< u≤ 12) λ≥ 252u λ≥ 415u λ≥ u502 また,状態空間が5個,ai =bi =uのときのスペクトルギャップは,12(3−√
5)uであること が知られている.