アメリカの大学で奮闘中

アメリカの大学でプログラミングを学ぶべくコンピューターサイエンス学部に留学したものの挫折し数学科に転部した著者が、自分の挫折ポイントを踏まえて数学、プログラミング、アルゴリズムついてできる限り分かりやすく解説してみるブログ。*できる限り記事の内容は技術的な間違いをしないように気をつけていますが、もし間違いがあれば教えていただけると助かります。

マルコフ連鎖②~グラフを考える~

前回の記事の続きです。

 

astrostory.hatenablog.com

 

この記事ではマルコフ連鎖をグラフとして見ていきます。なお、今回も例は前回の記事の天気の例を利用します。

 

簡単に再度説明しますと

 

晴れ、曇り、雨という3つの状態があり、そのいずれかの状態から別の状態に遷移します。

遷移の確率はそれぞれいかになります。

晴れ→晴れの確率をp1、曇り→晴れの確率をq1、雨→晴れの確率をr1

晴れ→曇りの確率をp2、曇り→曇りの確率をq2、雨→曇りの確率をr2

晴れ→雨の確率をp3、曇り→雨の確率をq3、雨→雨の確率をr3

 

グラフとして見る

マルコフ連鎖をグラフとして見ると以下のようになります。

 

f:id:Astrostory:20220217155251p:plain

 

グラフの特徴として、マルコフ連鎖はループを含む(かもしれない)有向グラフになります。

 

遷移行列

グラフには隣接行列という、行列にそれぞれのノードをとってどことどこのノードがつながっているかの情報を0と1であらわして、隣接状況を表現する隣接行列というものがありました。

 

もしご存知でない方はこちらもご参考ください。

astrostory.hatenablog.com

 

マルコフ連鎖にもそのような行列が存在します。マルコフ連鎖の隣接行列は、状態の遷移を表すため遷移行列と呼ばれ、隣接しているか否かの0,1でなく、0か遷移する時の確率で示します。

 

天気の例での遷移確率は以下のようになります。

   A   B   C

A   p1 q1  r1

B   p2 q2 r2

C   p3 q3 r3

 

これ今ある状態(行)から次(tからt+1)に遷移する状態(列)の確率をまとめていますが、この行列式を二乗すればtからt+2の遷移行列になり、この行列式を三乗するとtからt+3の遷移行列になります。

 

これってプログラムで扱うには便利な性質だと思いませんか?

 

にほんブログ村 教育ブログ プログラミング教育へ
にほんブログ村