マルコフ連鎖①〜グラフ理論と確率〜
マルコフ連鎖というグラフ理論を用いた確率の考え方があり、これはプログラムの実装も可能で便利だと思うのでこの記事で詳しく説明できればと思います。
いつものように数学的な厳密性は少し欠けていても分かりやすい記事を目指します。
マルコフ連鎖とは
マルコフ連鎖とはt(時間)が離散的なマルコフ過程の一種です。
マルコフ過程とは、次に起こる事象が今と過去の状態に依存することなく、現在の状態のみで決まる確率過程のことをいいます。
現在も状況のみで決まるというポイントが確率の表記を簡単に、コンピューターサイエンスに応用しやすくしているポイントだと思います。
実際にマルコフ連鎖を表現する数式は以下のように記述することができます。
P{xn = an | xm = am, m < n} = P{xn = an | xn−1 = an−1}
(n-1を現在としてみれば)t =nでx=aとなる状態に来るまでt=m(0<=m<=n)の過程があったにも関わらず、その確率はt=n-1のみの条件付き確率になっている。すなわち現在の状態によって未来の状態が決まる確率という式になっているかと思います。
t=n+1の確率をt=nの時の状態で決まるというふうに書いても大丈夫です。
表記はいくつか方法があるかと思います。
例えば
𝑃 (𝑋𝑛+1 = 𝑗 | X𝑛 = 𝑖, X𝑛−1 = 𝑖𝑛−1,...,X0 = 𝑖0) = 𝑝(𝑖,𝑗)
t=0~nの時にi_0 ~ i_nの状態経てXn+1の時にjになるのは、iとjのみの要素で決まるという意味の式です。
具体例
例えば、マルコフ連鎖の説明でよく出てくる天気の例を出したいと思います。
晴れの事象をA、曇りの事象をB、雨の事象をCとし、
晴れ→晴れの確率をp1、曇り→晴れの確率をq1、雨→晴れの確率をr1とします。
そうすると、
次の日腫れる確率は以下になる。
今日晴れの時 ... p・An
今日曇りの時は ... q・Bn
今日雨の時は ... r・Cn
なので、このように3つの状態から晴れになる遷移をするマルコフ連鎖の確率Pn+1は以下のように表されます。
Pn+1 = p1・An + q1・Bn + r1・Cn
さらに
晴れ→曇りの確率をp2、曇り→曇りの確率をq2、雨→曇りの確率をr2
晴れ→雨の確率をp3、曇り→雨の確率をq3、雨→雨の確率をr3とすると
次の日曇りになる確率と次の日雨になる確率は以下のようになる。
Qn+1 = p2・An + q2・Bn + r2・Cn
Rn+1 = p3・An + q3・Bn + r3・Cn
このような確率過程をマルコフ連鎖といいます。
グラフ理論ともう少し絡めてマルコフ連鎖を実装する時に役立つ知識を紹介している記事も興味のある方はどうぞ。
