マルコフ連鎖とそのORへの応用
木島 正明
l………………ll州＝lll………‖……………………………ll……lt……l………ll州Il…ll………lll………………………‖‖＝‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖……………lllll……l…lll………ll川Il………‖‖‖……llll…l川m＝川l…

つマルコフ連鎖が定式化され（例えば［27】），しかも（これ1． はじめにらのモデルにより）患者の効用および費用に関して最適なマルコフ連鎖が何かということは後にして，まず次の治療法を選ぶことができるであろう．

例によりマルコフ連鎖の応用の可能性を見てみよう．
例1バブル絶頂期には日本のほとんどの金融機関が最高の格付けであったが，バブル崩壊後にそのほとんどで●

2．マルコフ性とはマルコフ性の概念は離散時点の方が理解し易いので，見直しが行われ，格付けが下げられてしまった．このこ

本稿では時間の集合をγ＝（0，1，2，‥・）とする．連続時とから行政や経営のあり方を議論することも重要である

点マルコフ連鎖については［2］を参照して頂きたい．以下

が，企業の格付け（信用度）も時間とともに変化するもの

では〟を離散的な状態空間とし，（ズ1，f∈γ）を〟であるということから，この推移のデータを依って信用上の確率過程とする．確率過程とは時間のインデックス王

力（信用リスク）の定量化を行なおうという考え方で出てを持つ確率変数の列のことで，一般の確率過程ではズ廿1

き．ている（詳しくは［9］を参照）・つまり，信用度を状態の従う（条件付き）確率分布は，時点青までにこの確率過とし，これが時間とともに変化し（吸収状態である）倒産

程がどのよう尉直をとってきたかという履歴

までの推移をマルコフ連鎖で定式化しようというのであ石＝（ズ0＝壱0，…，ズト1＝才ト1，ズf＝吏）

る・もちろんデータの吟味や，厳密な意味でのマルコフ
性の膵認も重要であるが，それ以上にここで注目したいに依存すると考えられる・これに対して（ズf）がマノしコことは，信用リスク管理のために唯一の観測可能なデーフ性を持つとは，ズ叶1の（条件付き）確率分布が弟のタである格付けの推移を使おうというところである．

値にしか依存しない，つまり，すべての状態ゴ，J∈〟とすべての時点ま∈丁に対して例2 人間の健康度もある意味で時間とともに変化しており，人間の場合には推移の変化を見守るだけでなく，

P［ズ号1＝Jlろ］＝P［ズ叶1＝Jlズt＝盲］

病気になれば医者に行くであろうし，医者は病状によりが成立することである・一方，独立性はズ叶1の確率分

適切な治療を施すであろう．ここで「適切な」という意

布が現在や過去に依存しない場合で（1）

味は，最近の医療コンセプトに立脚すれば，患者の効用と（患者および社会の）経済的な負担を勘案して，患者にP【ズ叶1＝Jlろ］＝P［ズ什1＝ノ］

とって最適な治療を選ぶということであろう．このためと表現できる・2つの式（1）と（2）を比べると，マルコには各治療法の効果のデータを収集し，治療による病状

フ性と独立性には一見たいした違いがなさそうであるの推移を正確に定量化するだけでなく，患者個人の持つが，実際には大きな違ムがある．英語のアルファベット

病状に対する（負の）効用を数量化することが必要となをマルコラ的に発生させた場合と独立に発生させたもの

る・もし，これらのことが可能であれば，適当に定義さとを比較してみると，驚くほどの差が現われる（川を参れた病状を状態とし，各治療法に依存した推移確率を持照）・また，現実問題への適用という観点から見る上，古典的確率論の重要な結果である中心極限定理などは独立
きじま まさあき 筑波大学大学院経営システム科学性の仮定があって成立するのであるが，現実の問題では〒112文京区大塚3−29−1

この独立性の仮定は少し強すぎる場合が多い．逆に，一150（32）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

（2）

●

．Ⅳ

放任を追求しすぎたのでは複雑すぎて目ぼしい結果は何∑拘＝1；拘≧0，盲，J∈〟も得られないであろう．そこで，独立性を弱めたマルコフ性を仮定するのである．こうすることで解析的に扱い

j＝0とならなければならない／この条件を行列形式で書けが易く，しかも広い応用範囲を持つ確率過程が得られる・

Pl＝1；P＞0

実際，「システムのモデル化に際して状態空間をうまくとれば，たいていのシステムがマルコフ性を持っていると考えられる」と言い切る人もいるほどである・マルコ（3）となる（1は要素がすべて1のベクトル）が，このような行列を確率行列と呼ぶ・フ性を持つ確率過程はマルコフ過程と呼ばれ Markov●

P21＝P（Pl）＝Pl＝1；P2≧0（1856−1922）により提案された・本稿ではマルコフ過程のうち状態を表わす集合〟が非負の整数またはその部分であるから，P2も確率行列である・p古バ2）をP2の要集合である場合，すなわちマルコフ連鎖とそのORにお素とすれば，行列の横の定義と斉時性より，ける応用の可能性について解説する（より詳しくは【17］pよj（2）＝P［ズ叶2＝Jlズt＝査］

を見よ）・なお参考文献はできるだけ最近のものを一つ挙・●げることとし，さらに深く研究してみようという読者は■が示される．したが って，拘（2）は状態iから状態ノへ

その文献からサーべ−の2ステップ推移確率である．同様にして，Pnの要素を始めて頂きたい・拘（m）はmステップ推移確率であることが示される・

3．有限マルコフ連鎖

訂 （m）＝P［ズn＝よ］を時点mでの状態確率，汀 （n）をマルコフ連鎖（ズt）の確率的挙動払（1）の右辺

拘（り＝P［ズ叶1＝Jlズt＝盲】，盲，J∈〟，ま∈γ

要素とするベタいレ汀（乃）＝（訂よ（乃））を状態確率ベクトルと呼ぷ．マルコフ性より

汀ブ（れ＋1）＝ ∑p【ズn＝i，ズ∴＋1＝J】

が与えられることにより決定される− この条件付き確率l

勒（t）を時点いでの状態ょから状態ブへの1ステップ推移＝ ∑汀 （m）P［弟困＝ブlズn＝f】

確率と呼ふ 特に，推移確率が時点に依存しない場合，

1

すなわち，すべてのf∈丁に対してであるから，これらを行列形式で書けば

p j＝P［ズけ1＝ブlズー＝札i，J∈〟となっているとき，マルコフ連鎖（ズt）は斉時的であるという．以下では斉時的な場合のみを考える・
斉時的マルコフ連鎖の1ステップ推移確率は，2つの状態の対（り）が決まれば，それに対して1つの確率値●鞘が対応する・このため，斉時的マルヲフ連鎖では推訂T（れ＋1）＝訂T（m）P（4）

が得られる．ただしTは転置を表わす・初期確率ベクト
ルをα＝訂（0）とすれば，（4）を繰り返し用いることにより∬T（m）＝αTpn，乃＝0，1，2，…

（5）

移確率をまとめて推移確率行列と呼ばれる行列で表現す
る．いま状態数を有限とし，状態を適当に番号付けすることで状態空間を〟＝（0，1，‥・，〃）とする・このとき推移確率行列は以上の準備の下で，有限マルコフ連鎖の何に興味が
〃
O

p▲

1

あるのかに話を移そう．まず，どの状態も互いに到達可能，すなわち既約な有限マルコフ連鎖を考える・この

．．．

・・・

1

p▲

p．

mr

P．

p〃O p〃1 ＝■

4．有限マルコフ連鎖における興味

Ⅳ

p．

1

O

0

・・・

l

l

ハリ

O

P＝

が示される．

セッティングでの最大の興味はp〃Ⅳ●十分に時間が経過した後にどうなるか？
で与えられる．

推移確率行列Pの構成要素である拘は確率であるか
ら非負の値をとる．また，マルコフ連鎖がある時点で状ということである．既約な有限マルコフ連鎖に周期的な構造がなければ

態盲にいれば，次の時点では取りうる状態のうちどれかには必ず移るので

1本稿ではベタIルはすぺて列ベクトルとする・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1997年3 月号（33）151拘（m）＝∑叩 ブ（m），J∈〟，忠P【ズn＝ブlズ0＝盲】＝り＞0lが成立する（この場合をエルゴード的と呼ぶ）・この初期状態確率べクレレを汀。（m）＝（p可（m））と書くことに状態に依存しない極限確率は（4）でする・いま（ズn）を，（ズn）と独立で，初期分布として（ズn）の定常分布訂，推移確率行列として同じPを持つ

汀＝（汀よ）＝1im∬（れ）n一一十∞

マルコフ連鎖とする．ここでとした定常分布として特徴付けられ，
r＝inf（m：ズn＝ズn）
7TT＝訂Tp，．汀Tl＝1（6）とおけば，rは2つのマルコフ連鎖が初めて一致する時が成立する・（6）を定常方程式と呼び，エルゴード的な点を表わす確率変数でcoupling timeと呼ばれている・

マルコフ連鎖の定常方程式はユニークな解を持つ．定常

さて，r以降は2つのマルコフ連鎖は（確率的に）同じ振分布を求めるとい舞いをするので（強マルコフ性より）解くことである／状態数が多い場合には自明というP［ズn＝ブ，m≧r］＝P［ズn＝J，乃≧r］

わけではない【28］・ところで，現実問題では推移確率行が成立する．よって

列Pをデータから推定する必要があり，その推定法に関する研究も重要である（例えば［11］を見よ）が，ORとしl拘（m）一勺lては，推定値の誤差の与える影響を押さえておくことも＝lP［ズm＝ゴトP【ズn＝州

重要であろう【26］・また，確率分布訂が与えられたとき＝lP［ズn＝ブ，乃＜r］一夕【ズn＝ブ，m＜r】iに，訂を定常分布に持つ推移確率行列Pの特徴付け（逆≦ P【ズn＝ブ，乃＜r】＋P【ズn＝ノ，m＜r】問題）に関する研究もある［10］・であるから，ブに関して和をとれぼ

ところで，厳密な意味では，有限時間では極限分布に到達することはできないわけで，このためマルコフ連鎖Il汀。（氾）一可ll≦2f）［r＞m】の極限分布（エルゴード的ならば定常分布と同じ）へ収束が得られる・したがってrの分布の裾P［r＞可を知るする速さ，または極限分布との距離を押さえておくことことで極限分布との距離を評価することができる（詳しくが重要となる．エルゴード的な有限マルコフ連鎖の推移

は［21］を参照）・また評価尺度としてseparation

確率行列は
p可（れ）

一

P＝1汀T＋AJ∈・＼ 勺
（7）

およぴvariationdistanceと分解できて，1汀T△＝Al汀T＝0が成立する．したがってdα（n）＝∑（拘（乃卜汀j） j∈A

Pn＝1∬丁＋Am，m＝1，2，‥（8）が使われることも多い・【4］によればdα（乃）≦β。（乃）がが成立するので，Aの絶対値最大の固有値をγ1とすれ成立し，応用上はseparationを押えておくことが重要でば，推移確率pり（乃）は7＝lrllの割合で極限確率に収束ある・Separationの評価に関しては【15】を見よ・する・ところで，状態数が多い場合には収束の速さを支次に吸収状態を持つ有限マルコフ連鎖を考えよう．最配する値7を求めることは容易ではない．そこで，この初に挙げた2つの例はいずれも吸収マルコフ連鎖でモデ7を上からおさえる試みがいくつかなされている・【25］ル化される2．吸収状態があれば，その吸収状態から他のによれば状態へ到達できないので，吸収マルコフ連鎖は既約ではありえない．したがってエルゴード的ではなくて，必ず1 T（P）＝盲i誓き卦∑lpほ一扉

吸収状態のどれかに吸収される（例1では倒産，例2ではたで定義されるcoe用・Ciqnt ofergodicityはT（P）≧7を死亡が吸収状態）・有限吸収マルコフ連鎖における興味は満足し，マルコフ連鎖の収束の研究において重要な役割を演じる（γの上限については他に［5，7，22］を見よ）・

極限分布との距離を評価するために，初期確率ベクト
ルをα＝（αi）とし，時点乃における状態確率を
152（34）

2例2では決定の要素を含んでいるのでマルコフ決定過程の範疇で考えるべきであろうが，決定の要因数が少ない場合には各政策に対応するマルコフ連鎖を定式化しておいて，各政策のパフォーマンスを比較すればよい．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

●吸収状態へ吸収されるまでの時間（初到達時間）の確行列のPF固有値は1であるから）PF固有値を計算する

率分布，またはその平均や分散などの特性値；

必要がなれ したがって準定常分布の数値計算法の開発［24］や上下限の導出【13，16】が重要となる3・●吸収状態が複数ある歩合には，どの吸収状態忙吸収

5．無限マルコフ連鎖

されるかという確率；などであろう．吸収までの時間を表わす確率変数をrと待ち室に制限のない待ち行列モデルにおいて系内数をすると，このrの従う分布は相型分布と呼ばれ【23】，r考える場合には，状態空間は可算無限個と考えるのが普の分布の性質に関する研究も多い（例えば［20】を参照）・

通であり，したがって状態数が無限のマルコフ連鎖も広ところで，有限吸収マルコフ連鎖では有限時間内に必い応用範囲を持つ．状態数が無限の場合でも無限次元のずどこか忙吸収されるのであるが，rが十分に長くて，推移確率行列を想定し，有限次元のときの類推を考えれ吸収される前に統計的な均衡に到達していることがあ

ばかなりの議論は平行して行えるが，ある部分では有限る．例えば，ある生命休の倍数をマルコフ連鎖でモデルのときには起こり得ない状況が発生し数学的には非常に化する場合忙は，状態数0は明らかな吸収状態である．

厄介になる場合がある．その代表例が無限次元の定常方

しかし現存している種の場合にはまだ吸収されていない

程式（6）の数値解法であろう・このために一般的に行わわけで，しかも我々が観測できる時間のスパンにおいてれているのが，無限マルコフ連鎖を有限マルコフ連鎖ではある種の均衡に達していると考えられる．このような近似する方法であろう．この際に問題となるのが平衡状態を特徴付けるものとして考えられているのが準● この方法は近似として意味を持つか？

定常分布（quasi−Stationary distribution）である・非常である．すなわちPnをPから作られた状態数mのエルに小さな確率でしか吸収されない吸収マルコフ連鎖を想ゴード的な推移確率行列（Pnを確率行列にするための操定し，実際に計算機でシミュレーションを行なっ七みて作が必要である）とし訂nをこの定常分布としたときに，ほしい．間邁忙よってはなかなか吸収されないことがわ

1im訂n＝汀

かるであろう（［24］では化学のイオン反応のシミュレー

n一・・・◆Cく）が保証されている必要がある【8】・ただし訂は無限マルコション実験を行なっている）・

いも 興味の対象の部分空間をβ⊂〟とし，∫以外

フ連鎖の定常分布である．
ところで待ち行列の例では，サービスの能力が客の要の状態への初到達時間をrとする．ここで，まだ吸収さ求仕事量を上回っていれば安定的であり，待ち行列長がれていないという事象（r＞m）を考えて，
1im f）【ズn＝Jlズ0＝i，r＞m】＝9j
n→ClO

●

発散することはない．つまり，ある有限の観測期間内に（9）は行列長の上限が存在し，もしその期間内に統計的な均が存在しJ∈ざに関する和が1となる（すなわちβ上の衡状態に到達していれば，この定常状態は有限の準定確率分布となる）場合忙，この確率分布を準極限分布と呼常分布で近似されるであろう．つまり，無限マルコフ連

ふ 代数的には，推移確率行列Pのβ忙関する部分行列

鎖の推移確率行列Pの状態数nでのtrunCationをTとをTとすれば，では

し，この劣礎率行列の準定常分布をqnとすれば，qnのmに関する振舞いやqnと町。およぴ℡との関係など忙Tl≦1；T＞0（10）

も興味がある［14］・を満たし，このような行列を劣確率行列と呼ぶ（（3）と比無限マルコフ連鎖における準定常分布（11）と条件付き較せよ）・Perron−Frobenius（PF）の定理より，既約性の極限確率（9）忙話を移そう・これらの問題は数学的に大条件の下で，

変難しくて，準定常分布が存在するための必要十分条件に関する研究がまだ続けられている【6］・出生死滅過程や

γqT＝qTT，qTl＝1（11）を満たすべクトルq＝（9J）が唯一つ存在し（9J＞0），こ

右へのSkip−free過程4の場合［14，30］が示すように，準定常分布がユニークに定まる場合もあれば無限個存在すのqが準極限分布となる・（11）を満たすべクトルqは準定常分布として特徴付けられ，（11）を準定常方程式と呼ぷ・（11）を（6）と比較すると，準定常方程式ではPF固有値γを計算する必要があるが，定常方程式では（確率さこの場合の上下限は確率順序の意味で与えられる．確率順序忙
ついては【17，29】を見よ・
4右（上）方向へは隣の状態へしか移動できないマルコフ連鎖を右へのSkipTfree過程，左（下）方向へは隣の状態へしか移動でき© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1997年3 月号（35）153

る場合もあり，一般のマルコフ連鎖においてどうなるの［13］Kijima，M・（1992）EvaluationofthedecayparamT

eterforsomespecializedbirth−deathprocesses．］．

かなどは未解決のままである．しかし，多くの待ち行列モデルを特別な場合として含む準出生死滅過程の（busyAp〆Proゐ．，29，78ト791．
［14】Kijima，M・（1993）Qua5i−1imitingdistributionsof

Markov chains that are skip−free to theleftin

periodが長く続いた場合に対応する）準定常分布に関す

COntinuous−time．］．Appl．Prob．，30，509q517．

る結果が最近いくつか得られている［3，18］・準極限分布（9）の存在に関しては，出生死滅過程の場合には（現実的でない一つの場合を除いて）完全に解決された［19】が，一般の場合には何もわかっていないのが現状であり，こ［15］Kijima，M・（1994）Onseparationforbirth−deathprocesses・Prob・Eng．InF Sci．，8，51−68．
【16］Kijima，M．（1995）Boundsforthequasi−Stationary

distributions ofsome specialized Markov chains．
〟α班・Comp．〟odeJJ査犯♂，22，141−147．

の問題に関して現在の最も一般的な結果は［12］である・
ただし［12］の結果は準出生死滅過程の場合をカバーして［17］Kijima，M．（1996）MarkovProcessesfbrSiochas−
iicModeling，Chapman＆Hall．

いる【18］ので，応用上は大変にありがたい結果である．
〔18］K肩ima，M・and Makimoto，N・（1997）Qヮ？Si−
StationarydistributionsofMarkovchainsarlSlng

参考文献

fromqueueナngprOCeSSeS‥Areview・ReceniCon−／′、′J川／…＝J′．・l‖′JいJJ一伸んり川巾州−J．ヾ／…／川、J〃、［1】森村英典（1974），確率・統計，朝倉書店・

Processes，Shant′hikumar，J．G．and Sumita，U．
Ed．，tOappear．

【2］Anderson，W・J・（1991）［19］Kijima，M．，Nair，M．GリPollett，P．K．and van
Doorn，E・A・（1997）Limitingconditionaldistribu−［3］Bean，N．G．，Bright，L．，Latouche，G．，Pearce，．

tionsfbrbirthLdeathprocesses．Adv．Appl．Prob．，

C・E・M・，Po11ett，P・K・and Taylor，P・G・（1996）

29，tO appear．

Thequasistationarybehaviourofquasi−birth−and−death−prOCeSSeS・Ann・Appl・Prob・，tOaPpear・［20】Li，H・andShaked，M・（1996）Aging貢rstTpa5Sagetimes・EncycIopediaofSialisiica［Sciences，Wiley．

［4］Diaconis，P：andFi11，J・A・（1990）Strongstation−
ary times vlaaneWfbrmofduality．Ann．Prob．，［21】Lindvall，T．（1992）上ec加eβ 0乃 班e Co叩J哀乃タ
18，1483−1522．
Meihod，Wiley．
【5］Diaconis，P・チndStroock，D・（1991）Geometricbounds fbr elgenValues of Markov chains．Ann．

［22］Iiund，R・and Tweedie，R・L・（1996）Geomet−

rlC COnVergenCe rateS fbr stochastically ordered

Ap〆Proゐ．，1，36−61．

Markovchains・Maih．Oper．Res．，21，182−194．

［6］Ferrari，P・A・，Kesten，H・，Mチrtfnez，S・andPicco，
P・（1995）Existenceofヮuasl−Stationarydistribu−［23］Neuts，M・F・（1981）Mairix−GeomeiricSoluiionsin．ヾJ…イ川・ト／ハ、．1J…J諭・−．・lJ仁・l／ご／り‖〆い＝け．りり小りJ−ん、
tions‥ArenewaldynamlCalapproach．Ann．Prob．， JohnsHopkinsUniversityPress■．
23，501−521．
［24］Parsons，R・W・andPollett，P・K・（1987）Quasista−［7］Friedland，S・andGurvits，L・（19？4）AりupPer
tionary distributionsfor autocatalytic reactions．

boundfbrtherealpartofnonmaxlmalelgenVal−
uesofnonnegativeirreduciblematrices．SIAMJ．
〟α汁云￡A†lαJ．Ap〆，15，1015−1017．

［8］Heyman，D・P・（1991）Approximatingthestation−

ary distribution of aninfinite stochastic matrix．
J・Ap〆Proみ．，28，96−103．

J．∫ねt．Pんy5盲cざ，46，249−254．
［25］Seneta，E・（1991）Applicationsofergodicitycoefn−
CientstohomogeneousMarkovchai11S．Proceedings
qfiheDoeblinConference，Cohn，H．Ed．，AMSSeT
ries：Contemporary Mathematics．

［26］Seneta，E．（1993）Sensitivity offinite Markov【9］Jarrow，R．A．，Lando，D．and Turnbull，S．M．
Chainsunderperturbation．Siai．Prob．Leiiers，17，（1994）AMarkovmodelforthetermstructureof

163−168．

Creditriskspreads．Workingpaper，CornellUniv．

［27】Sonnenやerg，F・A・andB［10〕Karr，A・F・（1978）Markovchainsandprocesses
With aprescribedinvarlantmeaSure．Sloch．Proc．
4相木7，277−290．
［11］Karr，A・F・（1990）〟αrた0γProce55e5（木島による邦訳あり；確率モデルノ、ンドブック，90−117，朝倉書店）・．

guide．〟edicαJβec壱5盲0乃〟αた主犯タ，13，322−338．

［28】Stewart，W・J・（1994）InlroduciionioiheNumeri−
CalSo［uiionofMarkov Chains，PrincetonUniveト

SityPress．
［29］Szekli，鱒・（1995）馳cんα5わcOrder云乃タα乃dβepe？−［12］Kesten，H・（1995）A ratiolimit theorem fbr（sub）Markovchainson（1，2，・‥）with bounded
JumpS・Adv．Appl．Prob．，27，652L691．

dence m Applied Probabiliiy，Lecture Notesln
Statistics，97，Sprlnger．

［30】vanDoorn，Er・A・（1991）Quasi−Stationaryqistri−butions and convergence to quasi−Stationarlty Of

ない場合を左へのSkip−free過程，両方向へ隣の状態へしか移動

birth−deathprocesses．Adv．Appl．Prob．，23，683−
700．

できないマルコフ連鎖を出生死滅過程と呼ふ

154（36）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オ／ヾレーションズ・リサーチ