マルコフ連鎖の基礎
後藤順哉
中央大学経営システム工学科
2012年度「OR第2」
. . .1 簡単な例 . . .2 マルコフ連鎖 マルコフ性 推移確率行列 チャップマン・コルモゴロフの定理 定常分布と極限分布 状態空間の分割 . . .3 様々な応用例 GoogleのPageRank マルコフ連鎖による最適打順評価 マルコフ連鎖による格付け推移確率
みかん取りゲーム . 【例4.1】蜜柑取りゲーム1（森・松井, 2004）［改題］ . . . .. . . . 浩君と美智子さんが,正月にエアホッケーをして,勝った方が相手から蜜 柑を1個もらえるものとする. 最初, 2人はそれぞれ3個ずつ蜜柑を持っ ていて,どちらかの蜜柑が無くなるまでゲームは続けられる. 2人のエア ホッケーの腕が対等であれば,勝負は5分5分であろう. もし浩君の方が 少しうまく, 6-4で勝つとしたら,美智子さんが蜜柑を全部取られてしま う可能性はどれくらいになるか? . 【例4.2】蜜柑取りゲーム2 . . . .. . . . 上と同じゲームで, 2人のエアホッケーの腕が対等であるとして,最初持っ ている蜜柑が浩君が3個,美智子さんが2個であるとしたら,美智子さん が蜜柑を全部取られてしまう可能性はどれくらいになるか? 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 3 / 29
推移図 . Exercise 4.1 . . . .. . . . 蜜柑取りゲームにおいて,浩君の蜜柑の個数を状態として推移図を描け. . 【例4.3】天気の推移 . . . .. . . . ある地方の天気を観察したところ,天気（晴れor雨）が以下の規則で変 わるとする. 前日の天気が晴れの場合,翌日70%の確率で晴れ（30%で 雨）になる. 前日の天気が雨の場合,翌日60%の確率で雨（40%で晴れ） になる.天気を状態として推移図を描け.
破産の問題 . 【例4.4】破産の問題（森・松井, 2004） . . . .. . . . ある単純なパチンコでは玉が1個入ると2個出て,入らなければそのまま 取られてしまう.つまり,確率pで手持ちの玉が1個増え,確率1−pで1 個減る. b個の手持ちから始めて,手持ちの玉がN個に届くか, 0個になっ たらゲームが終了する. p=0.45,b=90,N =100のとき,破産する（N に届く前に0個になる）確率はいくらか? . Exercise 4.2 . . . .. . . . 破産の問題において,手持ち玉の個数を状態として推移図を描け. 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 5 / 29
確率過程 時刻t で添字づけされた確率変数の列{Xt}を と呼ぶ # Xtの分布のみを考える限りは,数値でなくてもOK tが取りうる値の集合をT :={0,1,2, ...}とする. {Xt} = {X0,X1,X2, ...}（離散時間モデル） #連続時間マルコフ連鎖も重要だが,以下では扱わない Xt がとりうる状態の集合を という 以下ではそれをSで表し, Sの要素数は有限とする #離散無限個のマルコフ連鎖もありうるが,以下では扱わない
マルコフ性
これまで通ってきた道筋（履歴）とは関係なく,現在の状態が分かってい
れば,次の状態がいくつになるか確率的に予測できる性質のことを
という. .
Def.マルコフ性Markov property
. . . .. . . . 任意の状態i0,i1, ...,i,j∈S,任意の時刻t ∈T に対して,以下が成り立つと き{Xt}は を持つという. P{Xt+1=j|X0 =i0,X1=i1, ...,Xt =i}=P{Xt+1=j|Xt =i} 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 7 / 29
n重マルコフ性 . Def. 2重マルコフ性 . . . .. . . . ∀i0,i1, ...,i,j,k ∈S,∀t ∈Tに対して,以下が成り立つとき{Xt} は2重マルコフ 性を持つという. P{Xt+1=j|X0=i0, ...,Xt−1=i,Xt =k} = P{Xt+1=j|Xt−1=i,Xt =k} . Def. n重マルコフ性 . . . .. . . . ∀t ∈T ,∀i0,i1, ...,it,it+1∈S,に対して,以下が成り立つとき{Xt} はn重マルコフ 性を持つという. P{Xt+1=it+1|X0=i0, ...,Xt−n+1=it−n+1, ...,Xt =it} =P{Xt+1=it+1|Xt−n+1=it−n+1, ...,Xt =it} . 【例4.5】天気の推移2 . . . .. . . . 例4.3の拡張として,天気が2日前までの天気に依存するとする.例えば,一昨日 晴れ,昨日晴れのとき今日晴れの確率が90%,一昨日雨,昨日晴れのとき今日晴 れの確率が50%,一昨日晴れ,昨日雨のとき今日雨の確率が70%,一昨日雨,昨日 雨のとき今日晴れの確率が50%とした場合, 2重マルコフとして記述できる.
シャノンのn重マルコフ連鎖による英語文書の再現 . 使用頻度に基づくランダム発生（n=0） . . . .. . . .
OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL
. マルコフ連鎖（n=1） . . . .. . . .
ON IE ANSOUTINYS ARE T INCOTORE ST BE S DEAMY ACHIN DILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE . 2重マルコフ連鎖（n=2） . . . .. . . .
IN NO IST LAT WHEY CRATICT FROURE GROICD PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE
推移確率行列 すべてのj,k ∈S,t ∈Tについて P{Xt+1=k|Xt =j} = P{X1=k|X0 =j} (=:pjk) が成り立つとき,マルコフ連鎖{Xt}は斉時的であるという. 斉時的マルコフ連鎖は、以下の の形にまとめることがで きる： P := p11 p12 · · · p1N p21 p22 · · · p2N ... ... ... pN1 pN2 · · · pNN ただし、pjk :=P{X1 =k|X0=j}, j,k =1, ...,N . Exercise 4.3 . . . .. . . . 例4.1∼4.4の推移確率行列を記せ
. Exercise 4.4 . . . .. . . . 推移図が右のように与えられるマルコフ連 鎖において,推移確率行列を求めよ. a b C d 1/3 1/4 1/5 1/6 . Exercise 4.5 . . . .. . . . 推移図が下のように与えられるマルコフ連鎖において,推移確率行列を求 めよ. b d g c 1/3 1/5 5/6 a f e 1/50 1/50 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 11 / 29
星座占いの順位のモデル化 12星座占いの順位変動（60日分） 第t+1日の順位 1 2 3 4 5 6 7 8 9 10 11 12 計 1 0 30 2 0 0 0 1 7 8 3 5 4 60 2 2 0 30 0 0 0 8 2 11 0 4 3 60 3 30 2 0 0 0 0 5 8 2 5 3 5 60 第 4 0 0 0 0 30 2 6 4 1 1 7 9 60 t 5 0 0 0 2 0 30 4 5 2 10 0 7 60 日 6 0 0 0 30 2 0 4 2 4 9 9 0 60 の 7 2 6 6 5 3 6 0 24 3 1 4 0 60 順 8 4 3 4 6 6 5 5 0 17 4 2 4 60 位 9 4 2 1 3 8 10 18 1 0 9 1 3 60 10 7 5 8 4 2 2 6 0 1 0 20 5 60 11 7 5 4 5 3 4 0 5 6 1 0 20 60 12 4 7 5 5 6 1 3 2 5 17 5 0 60 Yahoo!占いを集計したもの
チャップマン・コルモゴロフの定理 斉時的マルコフ連鎖の場合 pjk(2):=P{Xt+2=k|Xt =j} = S ∑ h=1 pjh·phk 2ステップの推移確率行列P(2):= ( pjk(2) ) は P(2) =P2 同様にして, mステップの推移行列P(m) := ( pjk(m) ) も Pm . Exercise 4.6 . . . .. . . . 例4.3で, 2ステップ後, 3ステップ後の推移確率を求めよ. 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 13 / 29
mステップ後の状態確率 π(m) k ：mステップ後に状態kにいる確率 π(m):= (π(m) 1 , ..., π (m) S )： 時刻mでの状態確率ベクトル（状態分布） π(m)=π(m−1)P =π(0)Pm . Exercise 4.7 . . . .. . . . 例4.3で,晴れの状態から始めたときと雨の状態から始めた時それぞれに ついて, mステップ後の状態分布を求めよ.
定常分布 確率ベクトルπ∗が π∗=π∗P を満たすとき,π∗を推移確率行列P の という. 仮に初期分布として定常分布を採用するπ(0)=π∗として各時点の状態分 布を求めると π(0)=π∗ π(1)=π(0)P =π∗P =π∗ π(2)=π(1)P =π∗P =π∗ ... π(m)=π(m−1)P =π∗P =π∗ と,すべての時刻mで状態分布が定常分布に一致する. . Exercise 4.8 . . . .. . . . 例4.1∼4.4の定常分布を求めよ. 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 15 / 29
到達可能性 状態推移を繰り返すことで状態iから状態jへ到達できるときiからj へ到達可能であるといい, i ⇒jと表す. iとjが互いに到達可能なとき連結であるといい, i ⇔jと表す. 連結関係⇔は同値関係であり,以下を満たす 反射律 ：i ⇔i 対称律 ：i ⇔jならばj ⇔i 推移律 ：i ⇔j, j⇔kならばi ⇔k 状態空間を同値類に分けることで,そのマルコフ連鎖の特徴が明確にな る. 同値類は以下のいずれかである： 閉じたクラス 既約なクラスirreducible set closed set 吸収状態absorbing state 一時的なクラスtransient set
. Exercise 4.8.5 . . . .. . . . 例4.1∼4.4それぞれについて,連結性に基づき状態空間を分割するクラ スを求めよ. 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 17 / 29
マルコフ連鎖の周期 dj:={k|pjj(k)>0}の最大公約数 を状態jの という dj≥2のとき状態jは周期性を持つ（周期的である）という dj=1のとき非周期的であるという . Exercise 4.9 . . . .. . . . 例4.1∼4.4の周期を求めよ. . Exercise 4.10 . . . .. . . . 推移図が右のように与えられるマルコフ連 鎖において,各状態a, b, c, dの周期を求 めよ. a b C d 1/6 1/3 1/4 1/5 2/3 3/4 4/5 5/6
定常分布の意味 . Theorem (定常分布と極限分布が一致する十分条件) . . . .. . . . 状態空間が有限で既約で非周期的ならば, lim k→∞p (k) jk =π∗k for any j .
.
.1 時間的に定常な分布 （導入時に示した通り） ..
.2 既約で非周期的ならば, p(k) jk の収束先 ..
.3 観測時間を長くした場合,状態kの現れる回数の相対頻度（or時間 平均） 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 19 / 29【トピック】GoogleのPageRankとマルコフ連鎖 リンクがたくさん貼られているHPはそれだけ良いページ ハイパーリンク行列H= [hij] hij = { 1/ℓi HPiからHPjにリンクがあるとき 0 otherwise ただし,ℓi:=HPiがリンクを貼るHPの総数 . Exercise 4.11 . . . .. . . . 右図の状況のとき, Hはどうな るか? 1 2 3 4 6 7 5
ランダム・サーファー・モデル ノードiが行き止まり⇒Hの第i行= (0, ...,0) 行き止まりノードに到達したら,次は確率1/Nでどこかに飛ぶ S :=H+a⊤(1 NeN) ただし, ai:= { 1 HP iが行き止まりノード 0 otherwise Sは確率行列（Hはそうでない！） 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 21 / 29
ランダム・サーファー・モデル(cnt’d) さらに,各ノードで一定の確率で他のノードにワープする これらを総合した確率行列 G:=αS+ (1− α)1 NeNe ⊤ N の定常分布がPageRankの基になっている（らしい）
. Assignment 4.1 . . . .. . . . .
.
.1 右のウェブグラフが与えられたとき, H およびSを求めよ. ..
.2 グーグル行列Gを求めよ. ..
.3 ページランクスコアを求めよ. ただし α =0.85とする. a d C b e 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 23 / 29【トピック】 マルコフ連鎖による最適打順評価 D’Esopo& Lefkowitz(1977)の進塁モデル 打者が置かれる状況をアウトカウントと走者の位置から25状態と し,その間の推移をマルコフ連鎖としてモデル化 0アウト 0アウト 1アウト 1アウト 0アウト 1アウト ヒット(H) 四死球(W) pS+pW アウト(O) pO pD 二塁打(D) 本塁打(H) pH pH pO pO pH pH pD pS pS pD pS+pW pH pD pD
2008年シーズンデータに基づく最適打順 通常打順 最適打順 最低打順 打順 打者 打率 打者 打者 １番 イチロー 0.310 青木 イチロー ２番 中島 0.331 中島 青木 ３番 青木 0.347 内川 岩村 ４番 稲葉 0.301 村田 城島 ５番 城島 0.227 小笠原 村田 ６番 小笠原 0.310 城島 小笠原 ７番 村田 0.323 イチロー 内川 ８番 内川 0.378 稲葉 稲葉 ９番 岩村 0.274 岩村 中島 期待得点 6.0408 6.5314 5.8707 ［出典］菅原（2010）経シス卒論
【トピック】 マルコフ連鎖による格付け推移確率 国債や社債などの債券の元本や利息の支払いが契約通りに行われるかど うかの信用度を適当な方法で分類したものを格付けという. 格付け会社（民間）が行うが、債券発行のコストに直結するなど、非常 に影響度が大きい. 信用リスク ムーディーズ 他の4社 信用リスクが低い Aaa AAA Aa AA A A 中程度の水準 Baa BBB Ba BB B B Caa CCC Ca CC 信用リスクが高い C C 債務不履行に陥っている D D 後藤(中央大 経営システム工学科) マルコフ連鎖 2012年度「OR第2」 27 / 29
破産の問題
aj :=手持ちの玉数がj個からスタートしてNに達する前に破産する確率
aj =paj+1+ (1−p)aj−1, j=1, ...,N−1
参考文献 森雅夫・松井知己『オペレーションズ・リサーチ』朝倉書店, 2004年. 岡村寛之,マルコフ連鎖の極限推移確率とWebリンク解析,オペレー ションズ・リサーチvol.54, no.12, pp.739(25)–743(29), 2009年. 宇野裕之,ウェブページのランキング技術,オペレーションズ・リ サーチvol.57, no.6, pp.308(136)–314(142), 2012年.
D’Esopo DA. Lefkowitz B The distribution of runs in the game of baseball, In Optimal Strategies in Sports (Ladany SP, Machol RE eds.), North-Holland, 1977.
Hillier FS, Lieberman GL Introduction to Operations Research –ninth
edition– (chapter 16), McGraw Hill, 2010.
Langville AN, Meyer CD（岩野他訳）『Google PageRankの数理』共 立出版, 2009年.（原題：Google’s PageRank and Beyond, Princeton
Univ. Press, 2006年）
