出生死亡連鎖（ Birth and death chains ）

特別な連続時間マルコフ連鎖の例として，有限状態空間上の出生死亡連鎖を考える．この 連鎖は，χ={0,· · ·, n}^，n∈Nの上を右(+方向)か左（−方向）に一歩しか動けない．ここ で，(λ_i)_i≥1と(µ_i)_i≥0を２つの非負値実数列とする．この連鎖が状態 iに居るならば，パラ メータλ_i+µ_iをもつ指数分布に従ってiに滞在し，確率_λ^λi

i+µ_i でi+ 1にジャンプするか，確 率 _λ^µi

i+µ_i でi−1にジャンプする．また，状態0ならばパラメータλ₀をもつ指数分布に従っ て状態 １ にジャンプし，状態nならばパラメータµnをもつ指数分布に従って状態n−1に ジャンプするとする．パラメータλi, µiは，それぞれこのマルコフ連鎖の出生率，死亡率と 呼ばれる．この連鎖のQ-行列Qは

Q=

⎛

⎜⎜

⎜⎜

⎜⎜

⎝

−λ₀ λ₀

µ₁ −(µ₁+λ₁) λ₁

· · · · · ·

µn−1 −(µn−1+λn−1) λn−1

µn −µn

⎞

⎟⎟

⎟⎟

⎟⎟

⎠

で与えられる．この行列から各成分をmax_i{λ_i+µ_i}^{で割ることで},マルコフ核 Ｋ を作る．こ のマルコフ核から生成される連続時間マルコフ連鎖を解析し，そのスペクトルギャップを評 価する．そのKを

K=

⎛

⎜⎜

⎜⎜

⎜⎜

⎝

1−b₀ bo

a₁ 1−(a₁+b₁) b₁

· · · · · ·

a_n−1 1−(a_n−1+b_n−1) b_n−1 a_n 1−a_n

⎞

⎟⎟

⎟⎟

⎟⎟

⎠

とかく．ここで，

a_i = µ_i

max_i{λ_i+µ_i}, b_i= λ_i

max_i{λ_i+µ_i}, i= 0，· · · , n 但し，a₀ = 0, b_n= 0.

とする.

その定常分布πは, π=

π(j) = b₀· · ·bj−1

a₁· · ·a_j π(0), 1≤j≤n

(但し，π(0)は n

j=0π(j) = 1を満たすように決める ) で与えられる．特に，a_i，b_i = u，(i = 0,· · ·, n)，a₀ = 0，b_n= 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

b₀π(0), b₀· · ·bi

a₁· · ·ai

π(0) (1≤i≤n)

mini {π(i)} である.

証明 関数gに対して E(g, g) = 1

2

x,y

|g(x)−g(y)|²K(x, y)π(x)

= 1

2

n−1

i=0

|g(i+ 1)−g(i)|²a_i+1π(i+ 1) + 1 2

n−1

i=0

|g(i)−g(i+ 1)|²b_iπ(i)

=

n−1

i=0

|g(i)−g(i+ 1)|²b₀· · ·b_i a₁· · ·a_iπ(0)

≥ A

n−1

i=0

|g(i)−g(i+ 1)|².

但し，

A= min

b₀π(0),b₀· · ·bi

a₁· · ·a_iπ(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)|²

12 _n−1

i=0

(|g(i+ 1)|+|g(i)|)²

12

が成り立つ．従って，

g²_∞≤2¹² 1

A ¹

2 (min

i {π(i)})⁻¹²E(g, g)¹² g₂ が成り立つ．故に，

g⁴₂ ≤ g²_∞g²₁

≤ 2¹² 1

A ¹₂

(mini {π(i)})⁻¹²E(g, g)¹² g2g²₁ である．従って,

g⁶₂≤ 2 Amin

i {π(i)}E(g, g)g⁴₁

が成り立つ．新たにg =f −cとする．但しcは π(f > c)≤ ¹₂^，π(f < c)≤ ¹₂ ^{とする．この} とき，

f −c⁶₂≤ 2 Amin

i {π(i)}E(g, g)f−c⁴₁≤ 2 Amin

i {π(i)}E(g, g)f ⁴₁ である．故に，任意のf に対して

Var(f)³ ≤ 2 Amin

i {π(i)}E(f, f)f ⁴₁ が成り立つ．ナッシュ定数CはC= _Amin²

i{π(i)} である．定理2.1.3，補題1.5.2から，

λ≥2Amin

i {π(i)} が成り立つ．

特にa_i=b_i=u，a₀ = 0, b_n= 0 の時,

A= u n+ 1 である．

例題 3.1.2. 例えば，状態空間が5個の場合については, A = b₀

Dmin{a₁a₂a₃a₄, b₁a₂a₃a₄, b₁b₂a₃a₄, b₁b₂b₃a₄, b₁b₂b₃b₄} である，また

mini {π(i)}= 1

Dmin{a₁a₂a₃a₄, b₀a₂a₃a₄, b₀b₁a₃a₄, b₀b₁b₂a₄, b₀b₁b₂a₄} である．但し，D=a₁a₂a₃a₄+b₀a₂a₃a₄+b₀b₁a₃a₄+b₀b₁b₂a₄+b₀b₁b₂b₃.

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個 存在するためｎが大きいときは困難である．そこで状態数が5個のときを調べた．

命題 3.1.3. 状態空間χ={0,· · · ,4}上の上記で定めたマルコフ核Kから作られるマルコフ 連鎖に対応するスペクトルギャップλは

λ≥ 1 A

を満たす．但し，

A= 1

Dmax{a₂a₃a₄+ 2b₁a₃a₄+ 3b₁b₂a₄+ 4b₁b₂b₃,

b₀a₃a₄+ 2a₁a₃a₄+ 2b₀b₂a₄+ 3a₁b₂a₃+ 3b₀b₂a₄+ 4a₁b₂b₃, b₀b₁a₄+ 2b₀a₂a₄+ 2b₀b₁b₃+ 3a₁a₂a₄+ 3b₀a₂b₃+ 4a₁a₂b₃, b₀b₁b₂+ 2b₀b₁a₃+ 3b₀a₂a₃+ 4a₁a₂a₃}^，

D=a₁a₂a₃a₄+b₀a₂a₃a₄+b₀b₁a₃a₄+b₀b₁b₂a₄+b₀b₁b₂a₃. 証明 ８ つの辺があり，各々の値を求める．

(i) e= (0,1)のとき Q(e) = 1

2(K(0,1)π(0) +K(1,0)π(1)) = b₀a₁a₂a₃a₄

D (=b₀π(0))，

(0,1)∈γ(x, y)となるパスγ(x, y)は４つあり，γ(0,1), γ(0,2), γ(0,3), γ(0,4)であるから，

ω(e) Q(e)

x,y∈χ:γ(x,y)e

|γ(x, y)|ωπ(x)π(y)

= 1

b₀π₀ {1π(0)π(1) + 2π(0)π(2) + 3π(0)π(3) + 4π(0)π(4)}

=π(0) 1

a₁ + 2b₁

a₁a₂ + 3b₁b₂

a₁a₂a₃ + 4b₁b₂b₃ a₁a₂a₃a₄

= 1

D(a₂a₃a₄+ 2b₁a₃a₄+ 3b₁b₂a₄+ 4b₁b₂b₃) である．以下，７つもこれと同様にして求める．

(ii) e= (1,0)のとき Q(e) = 1

2(K(1,0)π(1) +K(0,1)π(0)) = b₀a₁a₂a₃a₄

D (=b₀π(0))，

(1,0)∈γ(x, y)となるパスγ(x, y)は４つあり，γ(1,0), γ(2,0), γ(3,0), γ(4,0)であるから，

ω(e) Q(e)

x,y∈χ:γ(x,y)e

|γ(x, y)|ωπ(x)π(y) = 1

b₀π₀ {1π(0)π(1) + 2π(0)π(2) + 3π(0)π(3) + 4π(0)π(4)}

= 1

D(a₂a₃a₄+ 2b₁a₃a₄+ 3b₁b₂a₄+ 4b₁b₂b₃) である．

(iii) e= (1,2)のとき

Q(e) = 1

2(K(1,2)π(1) +K(2,1)π(2)) = b₀b₁ a₁ π(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(b₀a₃a₄+ 2a₁a₃a₄+ 2b₀b₂a₄+ 3a₁b₂a₄+ 3b₀b₂a₄+ 4a₁b₂b₃) である．

(iv) e= (2,1)のとき

Q(e) = 1

2(K(2,1)π(2) +K(1,2)π(1)) = b₀b₁ a₁ π(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(b₀a₃a₄+ 2a₁a₃a₄+ 2b₀b₂a₄+ 3a₁b₂a₄+ 3b₀b₂a₄+ 4a₁b₂b₃) である．

(v) e= (2,3)のとき

Q(e) = 1

2(K(2,3)π(2) +K(3,2)π(3)) = b₀b₁b₂ a₁a₂ π(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(b₀b₁a₄+ 2b₀a₂a₄+ 2b₀b₁b₃+ 3a₁a₂a₄+ 3b₀a₂b₃+ 4a₁a₂b₃) である．

(vi) e= (3,2)に対して Q(e) = 1

2(K(3,2)π(3) +K(2,3)π(2)) = b₀b₁b₂ a₁a₂ π(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(b₀b₁a₄+ 2b₀a₂a₄+ 2b₀b₁b₃+ 3a₁a₂a₄+ 3b₀a₂b₃+ 4a₁a₂b₃)

である.  

(vii) e= (3,4)に対して Q(e) = 1

2(K(3,4)π(3) +K(4,3)π(4)) = b₀b₁b₂b₃ a₁a₂a₃ π(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(b₀b₁b₂+ 2b₀b₁a₃+ 3b₀a₂a₃+ 4a₁a₂a₃).

(viii) e= (3,4)に対して Q(e) = 1

2(K(4,3)π(4) +K(3,4)π(3)) = b₀b₁b₂b₃ a₁a₂a₃ π(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(b₀b₁b₂+ 2b₀b₁a₃+ 3b₀a₂a₃+ 4a₁a₂a₃).

である．

従って，(i)〜(viii)より A= 1

Dmax{a₂a₃a₄+ 2b₁a₃a₄+ 3b₁b₂a₄+ 4b₁b₂b₃,

b₀a₃a₄+ 2a₁a₃a₄+ 2b₀b₂a₄+ 3a₁b₂a₄+ 3b₀b₂a₄+ 4a₁b₂b₃, b₀b₁a₄+ 2b₀a₂a₄+ 2b₀b₁b₃+ 3a₁a₂a₄+ 3b₀a₂b₃+ 4a₁a₂b₃, b₀b₁b₂+ 2b₀b₁a₃+ 3b₀a₂a₃+ 4a₁a₂a₃}.

となる．

特に，a_i, b_i =u, a₀ = 0, b₄= 0のとき，

λ≥ 4 15u である.

3.1.3 方法III(等周定数を用いた方法)

定理2.3.6から，等周定数Iを求めることでスペクトルギャップを評価できる．従って，等

周定数I を定義に従って求める．ここでは，ai, bi =u (0< u≤ ¹₂)，a₀ = 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 ∈A^c}^{とすると，}

Q(∂A) π(A) = 1

2

x∈A,y∈A^c

(K(x, y)π(x) +K(y, x)π(y)) 1

π(A) = (∂_∗A) u (n+ 1)

(n+ 1) (A) .

をみたす．π(A)≤ ¹₂^を満たすAのうち，この値を最小にするものを考える．まず，Aに含ま れる格子点の数，すなわち(A)を固定したときに，(∂_∗A)の値がを最小になるAの形を考 えるが，どんな(A)に対しても(∂_∗A) = 1となるAがあるのは明らか．従って，(A)を固 定したもとでは

min

Q(∂A) π(A)

= u

(A)

である．次に(A)を動かし，Iを決定する(A)を調べる．π(A)≤ ¹₂ ^{において，}

(A)≤ n+1

2 n：奇数

n2 n：偶数

である．故に,

I = 2u

n+1 n：奇数

2u

n n：偶数

である.

従って，定理2.3.6(チーガー不等式)より, λ≥ I²

8 =

_u2

2(n+1)² n：奇数

u²

2n² n：偶数

である.

以上で述べた有限状態空間上の連続時間出生死亡連鎖の結果を次の表にまとめた.

条件 方法 方法  方法   

状態空間がn+1個 命題3.1.1 —– —–

状態空間がn+ 1個，a_i=b_i=u 定理3.1.4 (0≤u≤ ¹₂) λ≥ _(n²₊₁₎^u 2 —– λ≥

_u2

2(n+1)² n：奇数

u²

2n² n：偶数

状態空間が５個 例題3.1.2 命題3.1.3 —–

状態空間が５個,a_i, b_i =u (0< u≤ ¹₂) λ≥ ₂₅²u λ≥ ⁴₁₅^u λ≥ ^u₅₀² また，状態空間が５個，a_i =b_i =uのときのスペクトルギャップは，¹₂(3−√

5)uであること が知られている．

ドキュメント内 齊藤 文則 (ページ 30-38)