浅野直樹の学習日記

マルコフ過程の問題の解き方を考えたので忘れないように書き留めておきます。

１．マルコフ過程とは

マルコフ過程とは、Wikipediaの記述を借りると、「未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程」です。具体例としては、天気の推移、マーケットシェアの推移、人口推移、機械の状態推移などが挙げられます。

 

２．問題例

具体的な問題例を見てもらいましょう。名古屋大学2006年工学部後期の入試問題です。2006　名古屋大学　後期理学部MathJaxを参考にさせてもらいました。

 

A，B2つの町がある．毎年1月1日に，A町の前年の住民のうち4割がB町に，B町の前年の住民のうち2割がA町に，それぞれ引っ越す（住民の数は十分に多く，引っ越す住民の割合は正確に4割，2割と見なしてよい）．それ以外には住民の移動はなく，A町，B町両方をあわせた住民の数は不変である．次の各問に答えよ．

（（１）〜（３）はここでは省略）

（４）　$n$年後にA町とB町それぞれに住んでいる住民の数を$a_n$と$b_n$とで表す．このとき，つぎの極限を求めよ．
$\displaystyle \lim_{n \to \infty} \frac{a_n}{b_n}$

 

３．解き方１：簡便法

上記の（４）で聞かれていることは、長期的にはA町とB町の人口比が何対何になるかということです。

 

「$n+1$年後にA町に住んでいる住民の数$=n$年後にA町に住んでいてとどまった人$+n$年後にB町に住んでいて引っ越した人」と考えることができます。これを数式にすると

$a_{n+1}=0.6a_n+0.2b_n$…①

となります。

同様に

$b_{n+1}=0.4a_n+0.8b_n$…②

です。

 

このようなマルコフ過程では定常状態に落ち着くということを前提にしてもよいならば、定常状態でのA町の人口を$a$、B町の人口を$b$として、①の式に代入すると（②に代入しても最終的に同じ式になります）

$a=0.6a+0.2b$

となります。

これを変形すると

$2a=b$

となるので、長期的にはA町とB町の人口比は$a:b=a:2a=1:2$になることがわかります。

 

この問題のようなマルコフ過程では定常状態に落ち着くということを前提にしてもよいなら上記の簡便法を用いることができます。しかしどちらかというと簡便法で数値を求めることよりも、この問題のようなマルコフ過程では初期値とは関係なく定常状態に落ち着くという事実のほうが興味深いです。そこで以下の方法でそのことを数学的に示します。

 

 

４．解き方２：数列の連立漸化式

先ほどと同じように考えて、①と②の式を作ります。

$a_{n+1}=0.6a_n+0.2b_n$…①
$b_{n+1}=0.4a_n+0.8b_n$…②

これは高校数学で言うところの連立漸化式です。ここでは$a_{n+1}-sb_{n+1}=t(a_n-sb_n)$と変形して解きます（隣接３項間漸化式に持ち込んで解く方法もありますが、この問題では計算が煩雑になります）。

$a_{n+1}-sb_{n+1}=t(a_n-sb_n)$に①と②を代入して

$0.6a_n+0.2b_n-s(0.4a_n+0.8b_n)=t(a_n-sb_n)$

これを整理して$a_n$と$b_n$の係数を比較すると

$0.6-0.4s=t$…③
$0.2-0.8s=-st$…④

となる。③を④に代入してこれを解くと$(s, t)=(-1, 1), (0.5, 0.4)$となる。

$a_{n+1}-sb_{n+1}=t(a_n-sb_n)$に今求めた$(s, t)$を代入して

$a_{n+1}+b_{n+1}=a_n+b_n$…⑤
$a_{n+1}-0.5b_{n+1}=0.4(a_n-0.5b_n)$…⑥

⑤や⑥は等比数列を表しているので

$a_n+b_n=a_1+b_1$…⑦
$a_n-0.5b_n=(a_1-0.5b_1)0.4^{n-1}$…⑧

⑦$-$⑧より

$1.5b_n=a_1+b_1-(a_1-0.5b_1)0.4^{n-1}$

$b_n=\frac23\{a_1+b_1-(a_1-0.5b_1)0.4^{n-1}\}$

⑦$+$⑧$\times2$より

$3a_n=a_1+b_1+2(a_1-0.5b_1)0.4^{n-1}$

$a_n=\frac13\{a_1+b_1+2(a_1-0.5b_1)0.4^{n-1}\}$

以上より

$\displaystyle \lim_{n \to \infty} \frac{a_n}{b_n}$

$=\displaystyle \lim_{n \to \infty} \frac{\frac13\{a_1+b_1+2(a_1-0.5b_1)0.4^{n-1}\}}{\frac23\{a_1+b_1-(a_1-0.5b_1)0.4^{n-1}\}}$

$=\frac{\frac13(a_1+b_1)}{\frac23(a_1+b_1)}$

$=\frac12$

となります。

 

５．解き方３：行列

再三使っている①と②の式

$a_{n+1}=0.6a_n+0.2b_n$…①
$b_{n+1}=0.4a_n+0.8b_n$…②

を行列でまとめて表記すると

$\begin{pmatrix}a_{n+1}\\b_{n+1}\end{pmatrix}=\begin{pmatrix}0.6& 0.2\\0.4&0.8\end{pmatrix}\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}$

となります。

$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}=\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}\begin{pmatrix}a_{n-1}\\b_{n-1}\end{pmatrix}$

$\begin{pmatrix}a_{n-1}\\b_{n-1}\end{pmatrix}=\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}\begin{pmatrix}a_{n-2}\\b_{n-2}\end{pmatrix}$

と順に考えていくと

$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}=\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}^n\begin{pmatrix}a_{0}\\b_{0}\end{pmatrix}$

となります。

$\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}^n$

がわかるとうれしいです。

行列の$n$乗と言えば対角化ですね。詳しい説明は省略しますが、固有値と固有ベクトルを用いて

$\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}=\begin{pmatrix}1&1\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\0&0.4\end{pmatrix}\begin{pmatrix}\frac13&\frac13\\\frac23&-\frac13\end{pmatrix}$

と変形することができます。

$\begin{pmatrix}\frac13&\frac13\\\frac23&-\frac13\end{pmatrix}\begin{pmatrix}1&1\\2&-1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}=E$

であることに注意すると

$\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}^n=\begin{pmatrix}1&1\\2&-1\end{pmatrix}\begin{pmatrix}1^n&0\\0&0.4^n\end{pmatrix}\begin{pmatrix}\frac13&\frac13\\\frac23&-\frac13\end{pmatrix}$

となり、右辺を計算すると

$\frac13\begin{pmatrix}1+2\cdot0.4^n&1-0.4^n\\2-2\cdot0.4^n&2+0.4^n\end{pmatrix}$

となります。

よって

$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}=\frac13\begin{pmatrix}1+2\cdot0.4^n&1-0.4^n\\2-2\cdot0.4^n&2+0.4^n\end{pmatrix}\begin{pmatrix}a_{0}\\b_{0}\end{pmatrix}$

から

$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}=\frac13\begin{pmatrix}(1+2\cdot0.4^n)a_0+(1-0.4^n)b_0\\(2-2\cdot0.4^n)a_0+(2+0.4^n)b_0\end{pmatrix}$

となり、

$a_n=\frac13\{(1+2\cdot0.4^n)a_0+(1-0.4^n)b_0\}$

$b_n=\frac13\{(2-2\cdot0.4^n)a_0+(2+0.4^n)b_0\}$

とわかるので、

$\displaystyle \lim_{n \to \infty} \frac{a_n}{b_n}$

$=\frac{\frac13(a_0+b_0)}{\frac23(a_0+b_0)}$

$=\frac12$

と最後の答えを求めることができました。

ちなみにこの大学入試問題の省略した小問は以下の通りです。

(1)　ある年の末にA町とB町それぞれに住んでいる住民の数を$a_0，b_0$とする．1年後にA町とB町それぞれに住んでいる住民の数$a_1，b_1$を表す式を$\begin{pmatrix}a_{1}\\b_{1}\end{pmatrix}=M\begin{pmatrix}a_{0}\\b_{0}\end{pmatrix}$とおくとき，$2×2$の行列$M$を具体的に示せ．
(2)　以下の式を満足する実数$\alpha, \beta$の値を求めよ．ただし$E$は$2×2$の単位行列である．
$M(M−\alpha{E})=\beta(M−\alpha{E})$
(3)　(2)で与えられた式は，$\alpha$と$\beta$を入れ換えても成り立つ．このことと(2)の結果を用いて$M^n$を求めよ．ただし$n$は正の整数とする．

(1)

$M$は上記で登場した$\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}$です。

(2)

力技で解くのが早いと思います。

$M(M−\alpha{E})=\beta(M−\alpha{E})$

$\begin{pmatrix}0.6&0.2\\0.4&0.8\end{pmatrix}\begin{pmatrix}0.6-\alpha&0.2\\0.4&0.8-\alpha\end{pmatrix}=\begin{pmatrix}\beta(0.6-\alpha)&0.2\beta\\0.4\beta&\beta(0.8-\alpha)\end{pmatrix}$

$\begin{pmatrix}0.6(0.6-\alpha)+0.08&0.12+0.2(0.8-\alpha)\\0.4(0.6-\alpha)+0.32&0.08+0.8(0.8-\alpha)\end{pmatrix}=\begin{pmatrix}\beta(0.6-\alpha)&0.2\beta\\0.4\beta&\beta(0.8-\alpha)\end{pmatrix}$

それぞれの要素を比較してうまく式変形をすると

$\alpha+\beta=\frac75, \ \alpha\beta=\frac25$

を得ます。

解と係数の関係より、このような$\alpha, \beta$は

$5x^2-7x+2=0$の解であるので、これを解いて$x=1, \frac25$

以上より、$(\alpha, \beta)=(1, \frac25), (\frac25, 1)$である。

(3)

$M(M−\alpha{E})=\beta(M−\alpha{E})$の両辺に左から$M$をかけると

$M^2(M−\alpha{E})=\beta{M}(M−\alpha{E})=\beta^2(M−\alpha{E})$

となる。これを繰り返すと

$M^n(M−\alpha{E})=\beta^n(M−\alpha{E})$

$M^{n+1}-\alpha{M}^n=\beta^n{M}-\alpha\beta^n{E}$…(A)

が得られる。

$\alpha$と$\beta$を入れ替えて同様の操作をすると

$M^n(M−\beta{E})=\alpha^n(M−\beta{E})$

$M^{n+1}-\beta{M}^n=\alpha^n{M}-\alpha^n\beta{E}$…(B)

が得られる。

(A)$-$(B)より

$(\beta-\alpha)M^n=(\beta^n-\alpha^n)M-\alpha\beta(\beta^{n-1}-\alpha^{n-1})E$

ここに$\alpha=\frac25, \beta=1$を代入して

$\frac35M^n=\begin{pmatrix}0.6(1-0.4^n)&0.2(1-0.4^n)\\0.4(1-0.4^n)&0.8(1-0.4^n)\end{pmatrix}-\begin{pmatrix}0.4-0.4^n&0\\0&0.4-0.4^n\end{pmatrix}$

$\frac35M^n=\begin{pmatrix}0.2+0.4\cdot0.4^n&0.2-0.2\cdot0.4^n\\0.4-0.4\cdot0.4^n&0.4+0.4\cdot0.4^n\end{pmatrix}$

$M^n=\frac13\begin{pmatrix}1+2\cdot0.4^n&1-0.4^n\\2-2\cdot0.4^n&2+0.4^n\end{pmatrix}$

と求めることができました。

(4)は先ほど対角化で解いた際の記述と同じでよいです。

 

６．まとめ

定常状態の比率の数字だけほしければ簡便法が圧倒的に簡単です。行列をやっていない人は数列のほうがとっつきやすいでしょうが、行列のほうが応用しやすいです。