齊藤 文則

有限状態空間上の対称マルコフ連鎖における スペクトルギャップの評価

東北大学大学院 理学研究科（数学専攻）

齊藤 文則

はじめに

 本論文では，有限状態空間上の連続時間マルコフ連鎖の推移確率が定常分布に収束すると き，その収束の速さをマルコフ連鎖により定まる解析的な量であるスペクトルギャップ用いて 評価する．連続時間マルコフ連鎖とは，ジャンプが起る時間がランダムで，ジャンプの行き先 が現在の状態のみに依存し，過去の履歴には依存しない推移が繰り返されるような確率過程 のことある．特別な連続時間マルコフ連鎖の例として，有限状態空間上の出生死亡連鎖を考え てみる．この連鎖は，状態空間{0,1,2,· · · , n}上を右か左へ一歩ジャンプする．２つの実数 列(a_i)_0≤i≤n，(b_i)_0≤i≤n（a_i, b_i >0, a_i+b_i≤1．但し，a₀ = 0, b_n= 0）に従い，この連鎖が状 態iにいるならば，パラメーターa_i+b_iをもつ指数分布に従ってiに滞在し，確率a_i/(a_i+b_i) でi−1にジャンプするか，確率b_i/(a_i+b_i)でi+ 1にジャンプする．a₀ = 0, b_n= 0と定め たことで，状態0と状態nに反射壁があると見なせるため，いつまでも推移し続ける．

状態空間χ={x₀, x₂,· · ·, xN}^，N ∈N上の一般のマルコフ連鎖の場合について考える．マ ルコフ連鎖は，成分が非負で各行成分の和が1のN + 1次正方行列である推移行列Kを持 つ．以降，マルコフ連鎖は可逆であると仮定する．すなわち，適当なχ上の分布関数πが存 在して，

π(x)K(x, y) =π(y)K(y, x) x, y∈χ

を満たすとする．さらに，状態xから出発し時刻tで状態yにいる確率がH_t(x, y) :=e^−t(I−K)(x, y) で与えられ，推移確率H_t(x, y)を持つマルコフ連鎖が構成できる．どこから出発してもどこ へでも有限回の推移で必ず到達できるという既約性の条件を満たすとき，定常分布πに収束 する．

次に，Kに対応する二次形式E^を，πに関して２乗可積分な関数空間²(π)に含まれるf, g に対して，

E(f, g) :=(I−K)f, gπ =

x∈χ

(I−K)f(x)g(x)π(x)

で定義する．ここで， ・,・πは²(π)内積を表す．このとき，スペクトルギャップλは λ:= min

f

E(f, f)

Varπ(f) : Varπ(f)= 0

で定義される．但し，

Var_π(f) :=

x

|f(x)−π(f)|²π(x)．

I−Kの最小固有値は0であり，定数関数はその固有関数である．よって，λは２番目に小さ い固有値に等しい．推移確率の定常分布への収束の速さを²(π)ノルムで計ると

H_tf −π(f)²₂≤e^−2λtVar_π(f)

を満たす．すなわち，収束の速さはλを求めることで評価できる．しかし実際には，スペク トルギャップの正確な値を求めることは困難な場合が多い．そこで，λに下から評価を与える ことで収束の速さを評価する．Saloff-Coste [SC]の中で，スペクトルギャップの下からの評価 を与える方法がいくつか書かれているが，本論文では次の3つの方法を用いる．

[方法I] ナッシュ不等式を用いた方法.

[方法II] マルコフ核Kに適合する辺集合を用いた方法. [方法III]等周定数及びチーガー不等式を用いた方法．

以下，本論文で得られた結果について述べる．各方法を，具体的な有限状態空間上の連続 時間マルコフ連鎖に応用する．空間上の状態数がn+ 1個の出生死亡連鎖に対しては，スペ クトルギャップλは

λ≥2 min

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

a₁· · ·a_iπ(0) (1≤i≤n)

mini {π(i)}

で評価できる．この評価はナッシュ不等式を導く[方法I]を用いて得られる．また，この出 生死亡連鎖に対して他の方法で評価を与え比較を行なった．

次に，出生死亡連鎖に対して得られた[方法I]の評価の応用として，自然連鎖を取り上げ る．この連鎖は{0,…, n}²上を隣接点にそれぞれ確率1/4で推移する．但し，隣接点が３点 である端や，２点である角では，留まる確率をそれぞれ1/4,1/2とする．自然連鎖の縦方向，

または横方向の動きに着目すると，状態数がn+ 1個でai, bi = 1/2である推移行列Kを持 つ出生死亡連鎖に従っている．だから，自然連鎖は出生死亡連鎖の直積として記述されるの で，自然連鎖のスペクトルギャップは，出生死亡連鎖におけるスペクトルギャップの値から得 られる．故に，出生死亡連鎖のスペクトルギャップの評価を応用して，自然連鎖のスペクト ルギャップλは

λ≥ 1

2(n+ 1)² で評価できる．W. Feller [WF]により，

λ= 1 2

1−cos π n+ 1

と求めることができ，自然連鎖のスペクトルギャップの評価の精度が確かめられる.  

最後に本論文の構成について述べる．本論文の第１章で，有限状態空間上のマルコフ連鎖 構成し，基本的な定義を述べる．また，それに対する性質を取り上げ，収束の評価とスペク

トルギャップの関連付けを行う．第２章では，[SC]のスペクトルギャップを評価する３つの方 法について述べる．第３章では，第２章の３つの方法を用いて，出生死亡連鎖に対するスペ クトルギャップを評価し，得られた評価の比較を行う．そして，評価の精度を確かめる例と して，自然連鎖を取り上げる．

謝辞

本論文を書き上げるにあたり，指導教官の竹田 雅好先生に，研究課題やその進め方等，多 大なご指導を頂きました．また，東北確率論セミナーを通じ服部 哲弥先生に，貴重な御意見 を頂きました．この場を借りて厚く御礼申し上げます．そして，先輩の塩沢 裕一さん，土田 兼治さん，田原 喜宏さんにも有益な助言を多数頂きました．どうも有り難う御座いました．

同輩の三浦 充晴君，渡部 金一郎君には公私にわたり多大なお世話を頂き，心からお礼を申 し上げます．

最後に，本人のわがままを受け入れ，進学に際して多くのご支援を甘受した，父，母に心 からの感謝を捧げます．

目 次

第1章 準備 5

1.1 連続時間マルコフ連鎖の構成. . . . 5

1.2 定常分布 . . . . 7

1.3 ディリクレ形式 . . . . 8

1.4 スペクトルギャップ . . . . 9

1.5 対数ソボレフ定数 . . . . 11

1.6 直積空間上のマルコフ連鎖の評価への応用 . . . . 14

第2章 スペクトルギャップを評価する方法 17 2.1 ナッシュ不等式とスペクトルギャップ . . . . 17

2.2 適合集合とスペクトルギャップ . . . . 19

2.3 等周定数とスペクトルギャップ. . . . 23

第3章 応用例 29 3.1 出生死亡連鎖（Birth and death chains） . . . . 29

3.1.1 方法I(ナッシュの不等式を利用した方法) . . . . 30

3.1.2 方法II(Kに適合した辺集合を用いる方法) . . . . 32

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

3.2 自然連鎖(Natural chains) . . . . 37

3.2.1 等周係数を用いた解析手法 . . . . 37

3.2.2 出生死亡連鎖の拡張による解析方法 . . . . 40

第 1 ^{章 準備}

これから本稿を読む上で必要な概念を述べる．

1.1 連続時間マルコフ連鎖の構成

有限状態空間χ={0,· · · , n}上の，連続時間マルコフ連鎖{Xt}₍t>0)の推移確率は定常で あると仮定する. すなわち,

P_xy(t) =P(X_t+s=y|X_s=x)

とする．X_t のマルコフ性からP_xy(t)は次の性質を満たす. x, y, z∈χに対して，

(a) P_xy(t)≥0.

(b) n

y=0P_xy(t) = 1.

(c) P_xz(s+t) = n

y=0P_xy(s)P_yz(t), t, s≥0.

更に, (d) lim

t→0+P_xy(t) =

1 ifx=y 0 ifx=y が成り立つことを要請する.

P(t)でP_xy(t)を成分に持つ行列を表すとすると, (c)は

P(t+s) =P(t)P(s), t, s≥0 (1.1)

とかけるので，P(0) =Iが導かれる．よって，(d)はP(t)がt= 0で連続であることを示し，

P(t)がすべてのt≥0に対して連続である.

S.Karlin [SK]の8章定理1.1および定理1.2 によって次の定理が成り立つ.

定理 1.1.1. 一般の連続時間マルコフ連鎖に対して

hlim→0+

1−P_xx(h) h =q_x,

hlim→0+

Pxy(h)

h =qxy (x=y) が存在して，0≤qxy <∞(x=y)，0≤qx≤ ∞^である.

すなわちq_xy(t) (x=y)は常に有限であり，q_yは定まるが無限になりうる．有限状態上の 連続時間マルコフ連鎖の場合にはq_x <∞^{となる．実際，}

1 =P_xx(h) + n y=0,y=x

P_xy(h) をhで割ってhを上から0へ近づけると，

q_x= n y=0,y=x

q_xy (1.2)

となる. これは，q_i が有限であることを示している.

定義 1.1.2. χを可算集合とする. 行列Q= (q_xy, x, y ∈χ)が次を満たすとき，χ上のQ-行 列(Q-matrix)という.

(i) 0≤ −q_xx <∞ x∈χ.

(ii) qxy ≥0 x, y∈χ, x=y.

(iii)

y∈I

q_xy = 0 x∈χ.

定理1.1.1で定まるqxy, x=y, qxx =−qxをマルコフ連鎖から定まるQ-行列という. 定理

1.1.1を行列の形でかくと

hlim→0+

P(h)−I

h =Q (1.3)

と表される．式(1.1)から P(t+h)−P(t)

h = P(t) ( P(h)−I )

h = P(h)−I

h P(t) (1.4)

であるから，式(1.3)によって右辺の極限は存在して,行列の微分方程式

P(t) =P(t)Q=QP(t) (1.5)

が導かれる．但し，P(t)はその成分がP_xy (t)であるような行列を表す. 式(1.3)，(1.4)より P_xy (t)の存在は明らか．式(1.5)は初期条件P(t) =I の下で連立常微分方程式の通常の解法 で解く事ができて

P(t) =e^Qt=I+ ∞ n=1

Qⁿtⁿ n!

である．従って有限状態上の連続時間マルコフ連鎖は，Q-行列によって一意的に定まる.

定義 1.1.3. χ×χ上の関数Kが，任意のx, y∈χに対して，

K(x, y)≥0，

y∈χ

K(x, y) = 1

を満たすとき，マルコフ核(Markov kernel)という.

マルコフ核Kから作られる確率過程を考える場合，Q-行列をQ=−(I−K) として定め ればよい．従って，次のように定義する．

定義 1.1.4. Kから作られるマルコフ半群を下記のように構成する:

H_t:=e^−t(I−K). その核は,

H_t(x, y) =e^−t ∞

i=0

tⁱKⁱ(x, y)

i! , Kⁱ= (Kⁱ(x, y))

であり，H_t^x(y) =Ht(x, y) とおくと，H_t^x(・)はQ (=−(I−K))から生成される連続時間マ ルコフ連鎖{Xt}t≥0がxから出発したときの時刻tでの分布を表す.

1.2 ^定常分布

定義 1.2.1. 状態空間χ上の確率測度πが，推移確率Pt(x, y)をもつ連続時間マルコフ連鎖 で，任意のy∈χと任意のt >0 に対して，

x∈χ

π(x)Pt(x, y) =π(y) を満たすとき定常分布という．

定義 1.2.2. 有限集合χ上のマルコフ核K が，任意のx, yに対してK^j(x, y) > 0を満たす j =j(x, y)が存在するとき，既約性(irreducible)という．

Norris [JN] の定理2.7.1，定理3.6.2より有限状態空間上の既約なマルコフ連鎖は，任意の x, yに対して

P_xy(t)→π_y (t→ ∞)

である．すなわち有限状態空間上の既約なマルコフ連鎖の推移確率は，定常分布に収束する．

次にその収束時間について量的な評価を行う．以下，そのための準備をする．πに関して２ 乗可積分な関数空間²(π)に含まれるf, gに対して，

π(f) =

x

f(x)π(x)，Var_π(f) =

x

|f(x)−π(f)|²π(x).

1≤p≤ ∞^{に対して，2}(π)内積^・,・π，^p-ノルム^・pを，

f, gπ =

x∈χ

f(x)g(x)π(x)， f p= (

x∈χ

|f(x)|^pπ(x))^1p, f _∞= max

x∈χ{|f(x)|}

とおく．K^l，H_tの分布πに関する密度をk^l，h_tとする．すなわち，

k^l_x(y) =k^l(x, y) = K^l(x, y)

π(y) , h^x_t(y) =h_t(x, y) = H_t^x(y) π(y) とおく.

定義 1.2.3. マルコフ核K，χ上の確率測度πが存在し，任意のx, y∈χに対して, π(x)K(x, y) =π(y)K(y, x)

が成り立つとき，可逆(reversible)であるという．

1.3 ^{ディリクレ形式}

解析的な不等式を用いて，連続時間マルコフ連鎖の収束を量的に調べる．以下，マルコフ 核K，定常分布πをもつマルコフ連鎖を考える.

定義 1.3.1. f, g∈²(π)に対して，形式

E(f, g) =((I−K)f, gπ) (^は実部) をH_t=e^−t(I−K)に関するディリクレ形式(Dirichlet form)という. 補題 1.3.2. ディリクレ形式E^{は次を満たす}:

(i) E(f, f) =(I− ¹₂(K+K^∗))f, fπ. (ii) E(f, f) =¹₂

x,y|f(x)−f(y)|²K(x, y)π(x).

(iii) _∂t^∂ Htf ²₂=−2E(Htf, Htf).

証明 (i)

E(f, f) = ((I−K)f, fπ) =f, fπ− (Kf, fπ)

= f, fπ−1

2(Kf, fπ+Kf, fπ) =f, fπ−1

2(Kf, fπ+K^∗f, fπ).

(ii)

E(f, f) = ((I−K)f, fπ) =

x

(I−K)f(x)f(x)π(x)

=

x

|f(x)|²π(x)−

x

Kf(x)f(x)π(x)

= (f ²₂ −Kf, fπ) =f ²₂−(Kf, fπ).

一方,

x,y

|f(x)|²K(x, y)π(x) =

x

|f(x)|²

y

K(x, y)π(x)

=

x

|f(x)|²π(x) =f ²₂ .

πがKに関して定常で，πK=πであるから,

x,y

|f(y)|²K(x, y)π(x) =

y

|f(y)|²

x

K(x, y)π(x) =

y

|f(y)|²π(y) =f ²₂ .

また,

x,y

(f(x)f(y))K(x, y)π(x) = (

x

y

K(x, y)f(y)f(x)π(x))

= (

x

Kf(x)f(x)π(x)) =(Kf, fπ) である．従って,

1 2

x,y

|f(x)−f(y)|²K(x, y)π(x) = 1 2

x,y

(|f(x)|²+|f(y)|²−2(f(x)f(x)))K(x, y)π(x)

= f ²₂−(Kf, fπ) である．よって，(ii)を示せた.

(iii)

∂

∂t Htf ²₂ = ∂

∂tHtf, Htfπ

= −(I−K)Htf，Htfπ+Htf，−(I−K)Htfπ

= −H_tf，(I−K^∗)H_tfπ− H_tf，(I−K)H_tfπ

= −2Htf，Htfπ+ (K+K^∗)Htf，Htfπ

= −2(H_tf，H_tfπ−1

2(K+K^∗)H_tf，H_tfπ).

この値は，この補題の(i)より−2E(H_tf, H_tf)である.

補題1.3.2(i)より，H_tとその共役H_t^∗のディリクレ形式は等しいことがわかる.

1.4 ^{スペクトルギャップ}

この節ではスペクトルギャップの評価について調べる．

定義 1.4.1. E ^{をマルコフ核}K に対応するディリクレ形式とする．このとき，スペクトル ギャップ(Spectral gap) λ=λ(K)を

λ= min

E(f, f)

Var_π(f)^；Varπ(f)= 0

で定義する.

λを定義するf は実関数と仮定してよい．なぜなら，f が実関数である条件のもとで定義 される値をλ とする．λ ≥λ をみたすことは明らかであり，逆の不等号を示す． 実関数 u, vによってある複素関数をf^∗=u+iv としたとき,

λ Var(f^∗) =λ (Var(u) + Var(v))≤ E(u, u) +E(v, v) =E(f^∗, f^∗).

従って,

λ ≤ E(f^∗, f^∗) Var(f^∗) であり，λ ≤λが成り立つ．

補題 1.4.2. K をスペクトルギャップλ = λ(K) を持つマルコフ核とする．このとき半群

H_t=e^−t(I−K)は任意のfに対して,

H_tf−π(f)²₂≤e^−2λtVar_π(f).

である. 証明

u(t) := Varπ(Htf) =

x

|Htf(x)−π(Htf)|²π(x) =Htf−π(Htf)²₂=Htf −π(f)²₂ . この書き換えと, 補題1.3.2の(iii)より,

u(t) =−2E(Ht(f−π(f)), Ht(f−π(f)))≤ −2λu(t).

従って，u(t) =e^−2λtu(0)，u(0) = Var_π(f)であり，

H_tf −π(f)²₂≤e^−2λtVar_π(f) が成り立つ．

系 1.4.3. Kをスペクトルギャップλ=λ(K)を持つマルコフ核とする．このとき，密度h^x_t(

・) = ^H_π^xt_(・^(・₎⁾は

h^x_t −1₂≤

1 π(x)e^−λt

を満たす．さらに,

|Ht(x, y)−π(y)| ≤

π(y) π(x)e^−λt

である．

証明 EK(f, f) = EK^∗(f, f)より λ(K^∗) = λ(K) であるから, H_t^∗ はスペクトルギャップ λ(K^∗) =λ(K)を持つマルコフ半群である. 次に,

δ_x(y) = 1

π(x) ifx=y 0 otherwise とする. このとき,

π(δ_x) = 1, h^x_t(y) =H_t^x(y)

π(y) =H_t^∗δ_x(y) であり，K^∗に補題1.4.2を用いると,

H_t^∗δ_x−1²₂≤e^−2λtVar_π(δ_x) である．Var_π(δ_x) = ¹⁻_π^π_(x⁽₎^x)であり，

h^x_t −1₂≤

1−π(x) π(x) e^−λt≤

1 π(x)e^−λt

が成り立つ．また,ヘルダー不等式を用いて

|h^x_t(y)−1| ≤h^xt

2 −1₂h^∗_t^y

2 −1₂≤ 1

π(x)

π(y)e^−λt

を満たす．両辺にπ(y)をかければよい.

従って，半群のスペクトルギャップを評価することが，その定常分布への収束の速さを評 価することになっている．以下で，スペクトルギャップを評価する方法を述べる.

1.5 ^{対数ソボレフ定数}

スペクトルギャップを下から評価する方法として，対数ソボレフ定数及びナッシュ定数が ある．まず,任意のf ∈²(π)に対して，

L(f) =

x

|f(x)|²log

|f(x)|² f ²₂

π(x)

とおく.

定義 1.5.1. Kを定常分布πをもつ既約なマルコフ核とし，E ^をKが対応するディリクレ形 式とする．対数ソボレフ定数α=α(K) を

α= min

f

E(f, f)

L(f)^；L(f)= 0

.

で定義する.

すなわち，対数ソボレフ定数とは任意の関数fに対して対数ソボレフ不等式 CL(f)≤ E(f, f)

をみたす定数Cの最大値である.

補題 1.5.2. 対数ソボレフ定数αとスペクトルギャップλは，

2α≤λ を満たす.

証明 任意の関数gとε >0に対して，f = 1 +εg とおく．このとき，

|f|²log|f|² = (1 +εg)²log(1 +εg)²

= 2(1 + 2εg+ε²|g|²)(εg−ε²|g|²

2 +O(ε³))

= 2εg+ 3ε²|g|²+O(ε³).

さらに，

f ²₂ = 1 +εg ²₂=

x

|1 +εg(x)|²π(x)

=

x

(1 + 2εg(x) +ε²|g(x)|²)π(x)

= 1 + 2επ(g) +ε² g²₂. であるから，

logf ²₂ = log(1 + 2επ(g) +ε² g²₂)

= 2επ(g) +ε²g²₂ −2ε²(π(g))²+O(ε³).

従って,

|f|²logf ²₂ = (1 + 2εg+ε²|g|²)(2επ(g) +ε²g²₂ −2ε²(π(g))²+O(ε³))

= 2επ(g) + 4ε²gπ(g) +ε² g²₂−2ε²(π(g))²+O(ε³).

故に,

|f|²log |f|²

f ²₂ = |f|²(log|f|²−logf ²₂)

= 2ε(g−π(g)) +ε²(3|g|²− g²₂ −4gπ(g) + 2(π(g))²) +O(ε³).

よって,

L(f) =

x

|f|²log |f|²

f ²₂

π(x)

=

x

2ε(g−π(g)) +ε²(3g²− g²₂ −4gπ(g) + 2(π(g))²) +O(ε³) π(x)

= 2ε²

g²₂−(π(g))²

+O(ε³)

= 2ε²Var(g) +O(ε³). (1.6)

また，

E(f, f) = E(1 +εg,1 +εg)

= ε²E(g, g). (1.7)

(1.6)より,

2ε²

L(f) = 1

Var(g) +₂¹_ε2O(ε³) = 1 Var(g) +O(ε) であるから, (1.7)及びαの定義より,

E(g, g)

Var(g) +O(ε) =E(g, g) 2ε²

L(f) = 2E(f, f) L(f) ≥2α.

よって，ε↓0 のとき,

2α≤ E(g, g) Var(g) であり

2α≤λ が成り立つ．

Diaconis P.とSaloff-Coste[DS]により，次が成り立つ．以下，^・p→qは^pから^qへの 作用素ノルムを表す．

定理 1.5.3. マルコフ連鎖(K, π)が可逆であると仮定する．2< q≤ ∞^{を固定し，}tq，Mqが H_tq −π _2→q≤M_q 満たすとする．このとき，

α≥ (1−²_q)λ 2(λt_q+ logM_q+^q−2_q ) である．特に，q =∞ ^かつmax

x h^x_t −1₂≤Mをなすtに対して，

α≥ λ

2(λt+ logM) が成り立つ.

1.6 直積空間上のマルコフ連鎖の評価への応用

直積空間上のマルコフ連鎖におけるスペクトルギャップ，対数ソボレフ定数を評価する方法 として下記の補題がある．直積空間上のマルコフ連鎖を，より扱いやすいマルコフ連鎖の積 で表す．その各々のマルコフ連鎖から得られる評価を通じて，求めたい直積空間上のマルコ フ連鎖の評価を得ることができる．  

補題 1.6.1. (Ki, πi)，i= 1,…, dを有限状態空間χi上のスペクトルギャップλi，対数ソボレ フ定数αiを持つマルコフ連鎖とする．また，

µ= (µi)^d₁；µi>0,

i

µi= 1.

このとき，χ= Π^d_i=1χ_i上のカーネルK;

K(x, y) =K_µ(x, y) = d i=1

µ_iδ(x₁, y₁)· · ·δ(x_i−1, y_i−1)K_i(x_i, y_i)δ(x_i+1, y_i+1)· · ·δ(x_d, y_d) 及び，定常分布π = Π_iπ_iを持つ積連鎖(K, π)のスペクトルギャップλ，対数ソボレフ定数α は

λ= min

i {µ_iλ_i}, α= min

i {µ_iα_i} となる．

証明

K(x, y) = K_µ(x, y)

= d

i=1

µ_iδ(x₁, y₁)· · ·δ(x_i−1, y_i−1)K_i(x_i, y_i)δ(x_i+1, y_i+1)· · ·δ(x_d, y_d) に対応するディリクレ形式E^は，K_iに対応するディリクレ形式Eiを用いて次のようにかける.

E(f, f)

= d

i=1

µi

⎛

⎝

x_j:j=i

Ei(f(x₁,· · ·, xi−1,・, xi+1,· · · , x_d), f(x₁,· · · , xi−1,・, xi+1,· · ·, x_d)

⎞

⎠

π₁(x₁)· · ·πi−1(xi−1)πi+1(xi+1)· · ·πd(xd))

= d

i=1

µ_i

⎛

⎝

x_j:j=i

Ei(f, f)(xⁱ)πⁱ(xⁱ)

⎞

⎠.

但し，xⁱ = (x₁,· · ·, xi−1,・, xi+1,· · · , xd), πⁱ(xi) =π₁(x₁)· · ·πi−1(xi−1)πi+1(xi+1)· · ·πd(xd) と定義する.

ここではd= 2のときαについて示す．d≥3においても同じように示せる．また，λにつ いても同様に示せる.

f :χ×χ→ ^{を非負関数，}F(x₂) =

x₁

f(x₁, x₂)²π₁(x₁) ¹

2

とする. L(f) =

x₁,x₂

|f(x₁, x₂)|²logf(x₁, x₂)²

f ²_2,π π(x₁, x₂)

=

x₁,x₂

|f(x₁, x₂)|²log F(x₂)²

F ²_2,ππ(x₁, x₂) +

x₁,x₂

|f(x₁, x₂)|²logf(x₁, x₂)²

F(x₂)² π(x₁, x₂)

=

x₂

F(x₂)²log F(x₂)² F ²₂,π

π₂(x₂) +

x₁,x₂

|f(x₁, x₂)|²log f(x₁, x₂)²

f(・, x₂)²₂π(x₁, x₂). (1.8) ここで，

α₂ = min

E2(F, F)

L(F) ;L(F)= 0

≤ E₂(F, F) L(F)

= E₂(F, F)

x₂

F(x₂)²log^F_F^(x2₂⁾²

2,ππ₂(x₂) .

かつ, 

α₁ ≤ E1(f(・, x₂), f(・, x₂)) L(f(・, x₂))

= E1(f(・, x₂), f(・, x₂))

x₁ |f(x₁, x₂)|²log^|f_f⁽₍^x_・¹_,x^,x2)|2

2)²₂π₁(x₁). より,式(1.8)は

E2(F, F) α₂ +

x₂ E₁(f(・, x₂), f(・, x₂))π(x₂) α₁

で上から抑えることができる．次に, E₂(F, F) = 1

2

x₂,y₂

|F(x₂)−F(y₂)|²K(x₂, y₂)π₂(x₂)

≤ 1 2

x₂,y₂

f(・, x₂)−f(・, y₂)²_2,π1 K(x₂, y₂)π₂(x₂)

=

x₁

1 2

x₂

|f(x₁, x₂)−f(x₁, y₂)|²K(x₂, y₂)π₂(x₂) π₁(x₁)

=

x₁

E₂(f(x₁,・), f(x₁,・))π₁(x₁).

従って,

L(f) ≤ 1 µ₂α₂

x₁

µ₂E₂(f(x₁,・), f(x₁,・))π₁(x₁) + 1

µ₁α₁

x₂

µ₁E₁(f(・, x₂), f(・, x₂))π₂(x₂).

E(f, f) =

x₂

µ₁E₁(f(・, x₂), f(・, x₂))π₂(x₂)

+

x₁

µ₂E₂(f(x₁,・), f(x₁,・))π₁(x₁) であるから，

L(f)≤max

i { 1

µ_iα_i}E(f, f) を満たす．故に,

E(f, f)

L(f) ≥min

i {µiαi}. すなわち

α≥min

i {µ_iα_i}.

一方，逆向きの不等式は容易である．f の関数として二つの変数のうち片方に依存する関 数をとれば示せる．よって等号成立.

第 2 章 スペクトルギャップを評価する方法

2.1 ナッシュ不等式とスペクトルギャップ

定義 2.1.1. 任意のg∈²(π)に対して，不等式

Varπ(g)^(1+2d)≤CE(g, g)g₁^4d (2.1) をナッシュ (Nash) 不等式という．d，CはKから定まる定数である．特に，定数Cをナッ シュ定数という.

定理 2.1.2. 有限状態空間上のマルコフ連鎖(K, π)が式(2.1)を満たすとき，任意のtに対 して，

h^x_t −1₂≤ dC

4t ^d

4

, (2.2)

が成り立つ．さらに，

|h_t(x, y)−1| ≤ dC

2t ^d

2 (2.3)

が成り立つ.

証明 f ₁= 1を満たすf を固定する.

u(t) :=H_t(f−π(f))²₂= Var_π(H_tf) とする．補題1.3.2 (iii)より

u(t) =−2E(H_t(f−π(f)), H_t(f−π(f))) =−2E(H_tf, H_tf) である．また，

H_tf ₁=

x

|H_tf(x)|π(x)≤

x

H_t|f(x)|π(x) =

x

|f(x)|π(x) =f ₁= 1

であり，仮定した式(2.1)は

u¹⁺_t ^2d ≤ −C 2u(t)

となる.

v(t) := dC

4 u(t)^−2d 

とおくと，v(t)≥1．また，v(0)≥0であるから，v(t)≥t．従って，

t≤v(t) = dC 4 u(t)^−2d

である．すなわち，任意のt >0に対して，u(t)≤(^dC_4t)^d2 . 従って, H_t−π _1→2= sup

f=0

H_tf −π(f)₂ f ₁

≤ dC

4t ^d

4

共役なH_t^∗に対しても同様に,

H_t^∗−π1→2= sup

f=0

H_t^∗(f)−π(f)2

f ₁

≤ dC

4t ^d

4

が成り立つ．よって，

H_t^∗−π_1→2=H_t−π_2→∞= max

x h^x_t −1₂ であるから，

h^x_t −1₂≤ dC

4t ¹

4

が成り立つ．

次に，Htの半群性より，Ht−π = (Ht

2 −π)(Ht

2 −π)であるから，任意のtに対し，

H_t−π_1→∞≤Ht

2 −π_1→2Ht

2 −π _2→∞≤

dC 4₂^t

^d

2 =

dC 2t

^d

2

を満たす．Ht−π_1→∞= max

x,y {|ht(x, y)−1|} より，

|h_t(x, y)−1| ≤ dC

2t ^d

2

が成り立つ．

定理 2.1.3. (K, π)を有限状態空間上の可逆なマルコフ連鎖とする．(K, π)が(2.1)をみたす とき，この連鎖の対数ソボレフ定数αは

α≥ 2 dC で評価できる.

証明 定理2.1.2において，t= ^dC₄ とすると式(2.2)は h^x_t −12≤

dC 4t

^d

4 = 1

である．これは，

maxx h^x_t −12≤1 であり，定理1.5.3を用いて,

α≥ λ

2(λt+ log 1) = 1 2t = 2

dC

である．

2.2 適合集合とスペクトルギャップ

定義 2.2.1. K を有限集合χ 上の既約なマルコフ核とする. 

(1) 次の条件をみたすとき，辺集合A ⊂χ×χはKに適合しているという. (i) (x, y)∈ A=⇒(y, x)∈ A.

(ii) (χ,A)が連結.

(iii) (x, y)∈ A=⇒K(x, y) +K(y, x)>0.

(2) Kが定常分布πを持つχ上の既約なマルコフ核であるとき，e= (x, y)∈χ×χに対して, Q(e) = 1

2(K(x, y)π(x) +K(y, x)π(y)) とする．このとき，Qはχ×χ上の確率測度である．また

df(e) =f(y)−f(x) とする．

定義 2.2.2. Aを適合した辺集合とする．(χ,A) 上の道γが，γ = (x₀,…, xk)；(xi−1, xi)∈ A

，i= 1,…, k であるとき，γ = (e₁,…, e_k)；ei = (xi−1, xi)∈ A^，i= 1,…, k とかける．このと きの道γ の長さは|γ|=k と定義する．さらに，(χ,A)での(x, y) ∈χ×χを結ぶ重複しな いすべての道集合Γ(x, y)を

Γ(x, y) ={γ= (e₁,…, e_k);x₀ =x, x_k=y, ei = (xi−1, xi)∈ A, i= 1,…, k, ei =ej, i=j} とする.

これを用いると，マルコフ連鎖(K, π)のディリクレ形式E^は，

E(f, f) = 1 2

x,y

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

= 1

4

x,y

|f(x)−f(y)|²K(x, y)π(x) +1 4

y,x

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

= 1

2

x,y

|f(x)−f(y)|²1

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

= 1

2

e∈χ×χ

|df(e)|²Q(e)

とかける.

定理 2.2.3. K を有限集合χ 上の定常分布π を持つ既約なマルコフ核とし，A^をK に適合 した辺集合とする．さらに，各(x, y) ∈χ×χ に対して道γ(x, y) ∈Γ(x, y)が唯一存在する とする．このとき,

A= max

e∈A

⎧⎨

⎩ 1 Q(e)

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

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

⎫⎬

⎭

によって，

λ≥ 1 A が成立する.

証明 各(x, y)∈χ×χに対して，

f(x)−f(y) =

e∈γ(x,y)

df(e)

とかける．シュワルツ不等式より

|f(x)−f(y)|² ≤

⎛

⎝

e∈γ(x,y)

df(e)

⎞

⎠

2

≤

⎛

⎝

e∈γ(x,y)

1²

⎞

⎠

⎛

⎝

e∈γ(x,y)

|df(e)|²

⎞

⎠≤ |γ(x, y)|

e∈γ(x,y)

|df(e)|²