修士論文 要旨

半正定値計画法による有限マルコフ連鎖の解析と最適化
数理情報学専攻 48-146201
指導教員

赤木 康紀
定兼 邦彦 教授

分かりやすい．漸近分散が小さければ推定はより正確

1 はじめにに，大きければより不正確になる．そのため，漸近分散

マルコフ連鎖モンテカルロ法 (MCMC 法) は，マルは推定の良さの指標としてしばしば用いられる．

コフ連鎖を利用して与えられた確率分布からのサンプ

漸近分散は V 上の関数値 f に依存する値であることリングを行う手法であり，統計学における期待値計算やから，推移確率行列 P そのものの良し悪しを議論する

数値積分，シミュレーションなどで広く利用されてい上では扱いにくい．そのため，P の良し悪しの指標とる．MCMC 法は所望の分布について可逆なマルコフ連して vA (P ) := EB [v(f, P )] を使うことが提案されてい鎖を設計し，遷移を行うことでサンプリングを実行するる．ただし，B はが，推移確率行列の選び方には自由度がある．MCMC法による期待値計算の精度は漸近分散と呼ばれる量にB = {f ∈ Rn | Eπ (f ) = 0, Varπ (f ) = 1}

よって特徴づけられ，どのような推移確率行列を使うなる領域であり，EB [·] は f が B から一様乱択されたかに大きく依存することが知られている．そのため，ど場合の期待値を表す．P の固有値を 1 = λ1 > λ2 ≥のような推移確率行列が漸近分散を小さくするかとい· · · ≥ λn とすると，π が一様分布である場合う問題は重要な問題である．本研究では，グラフ上でのvA (P ) =MCMC 法を考え，漸近分散を小さくするような推移確率行列は何かという問題に関する２つの話題を扱う．

2 MCMC 法と漸近分散n∑2−11−λii=2と書けることが Chen らによって示されている [2]．こ∑nこで，1i=2 1−λi は Kemeny 定数と呼ばれ，マルコフ連鎖の理論において重要な量である．

MCMC 法を用いて，連結なグラフ G = (V, E)，V上の確率分布 π : V → (0, 1)，V 上の関数値 f に対して Eπ (f ) :=∑v∈V π(v)f (v) を計算する方法を以下に3 関数が固定されている場合の漸近分散の最小化問題示す．

 まずは，グラフ G = (V, E)，確率分布 π : V →(0, 1)，V 上の関数値 f が与えらている場合に，漸近分1. 既約かつ π を定常分布にもつ，グラフ G 上のマ散 v(f, P ) を最小化する π について可逆な推移確率行ルコフ連鎖の推移確率行列 P を作る．

2. ある状態 v0 ∈ V から，P をもとに確率的な遷列は何かという問題を考える．この問題には，漸近分散移を行う．こうして得られるマルコフ連鎖を {Xt }は既約なマルコフ連鎖にしか定義されないにもかかわとする．

らず，実行可能領域を既約な推移確率行列に制限すると最適解が存在しない場合があるという困難がある．本3. 十分大きいステップ数 T − 1 で遷移を終了させ，∑T −1
研究では関数の推定可能性という概念を新しく導入し，µT (f ) := T1 t=0 f (Xt ) を出力する．
その概念を用いて非既約な推移確率行列の一部にも漸推定の精度は漸近分散と呼ばれる指標によって評価

近分散の定義を拡張した．そして，拡張された漸近分散される．漸近分散の存在は以下の定理が保証している．の最小化問題が半正定値計画問題として定式化できる

定理 1 ([3]). P を既約なマルコフ連鎖の推移確率行列とすると，初期状態の分布に関係なく

lim T · Var(µT (f ))T →∞が存在する．

ことを示した．この最適化問題によって得られる最適解の例が図 1 である．これらの結果は，漸近分散を最小化する推移確率行列の構造に関して興味深い洞察を与えている．

4 Kemeny 定数の最小化問題

この収束先を漸近分散と呼び，v(f, P ) で表す．漸近さらに本研究では，グラフ G 上の，一様分布につい分散の意味は，Var(µT (f )) ≈ T1 · v(f, P ) と書き直すとて可逆なマルコフ連鎖の Kemeny 定数の最小化問題に

半正定値計画法による有限マルコフ連鎖の解析と最適化 (赤木 康紀)

定理 2. 任意のグラフにおいてK(P opt ) ≤ K(P MH ) ≤ dmax · K(P opt )が成立する．ただし dmax はグラフの最大次数である．
定理 2 より，最大次数が小さいグラフにおいてはPMHは最適に近いことがわかる．

さらに，Kemeny 定数の上界について以下の定理が成り立つことを示した．
図 1. 最適解の例．π = 14 [1, 1, 1, 1]⊤ である．

定理 3. 任意の連結なグラフにおいて，K(P MH ) ≤ 3(n2 − n)ついての研究を行った．この問題は，半正定値計画法を利用して数値的には正確に解けることが Agharkar らによって示されている [1] が，具体的なグラフにおける最小値や下界は知られていなかった．本研究では，具体的な幾つかのグラフにおいて Kemeny 定数の最小値が成り立つ．
この上界は緩い評価であるが，G が木である場合は次のように改善することができる．
定理 4. 任意の木において，や下界を解析的に求め，MH 法による推移確率行列のK(P MH ) ≤ (n − 1)2Kemeny 定数との比較を行った．得られた結果は表 1にまとめてある．ただし，主要な項のみを記しており，n は頂点数である．

が成立する．
この上界はほとんどタイトである．これは，スターグ

表 1. 具体的なグラフに対する Kemeny 定数

ラフにおいて K(P MH ) = (n − 1)2 − O(n) であることからわかる．つまり，K(P MH ) はスターグラフにおいてほぼ最悪になる．

グラフ

K(P MH )K(P opt )

完全グラフ

nn

サイクルグラフ

1 26n

1 26n

等式もほとんどタイトである．

スターグラフ

n2n2

参考文献

超立方体

n〜2nn〜2nバーベルグラフ

1 28n

√
7+2 2n4

ダブルスターグラフ

5 28n

1 22nパスグラフ

1 23n

1 23n

完全 r 分木rn logr−1 n

rn logr−1 nさらに，定理 4 より，任意の連結なグラフにおいてさらに，K(P MH ) と K(P opt ) の間に以下の関係があることを示した．

K(P opt ) ≤ (n − 1)2 が成り立つこともわかる．この不[1] P. Agharkar, R. Patel, and F. Bullo. Robotic surveillance and Markov chains with minimal first passage
time. In Proceedings of the 53rd Annual Conferenceon Decision and Control, pp. 6603–6608. IEEE, 2014.
[2] T.-L. Chen, W.-K. Chen, C.-R. Hwang, and H.-M.
Pai. On the optimal transition matrix for Markovchain Monte Carlo sampling. SIAM Journal on Control and Optimization, Vol. 50, No. 5, pp. 2743–2762,2012.
[3] J. G. Kemeny and J. L. Snell. Finite Markov Chains.
Van Nostrand, 1960.