放浪問題の別解

『数学ガール/乱択アルゴリズム』の問8-2 放浪問題は、確率過程の一種、離散マルコフ連鎖の簡単な例のようです。また、線形代数に関する知識をもう少し使うと、次のようにも解くことができます(定理になるような部分は赤字で強調しました)。勉強のモチベーションに繋がれば、幸いです。

解答

\((a_{n+1}, b_{n+1})\)と\((a_{n}, b_{n})\)との間を結ぶ行列を\(T\)と書く。この行列の1行2列成分の意味を時刻n+1の立場から考えると、「今A国にいて、B国から来た」だ。他も同様の解釈ができて、i行j列成分の意味は、「今C[i]国にいて、C[j]国から来た」(C=["A", "B"]とする)と解釈できる。この解釈から、C[i]国に来る方法が、A国からかB国からの必ずどちらかなので、\(\sum_{i=1}^{2}T_{i,j} = 1\)になることが分かる。

固有値

これを使うと\(\boldsymbol{v}^{(0)} = (1, 1)^{t}\)は転置行列\(T^{t}\)の固有ベクトルになっていることが確かめられる。計算すると\(T^{t}\boldsymbol{v}^{(0)} = \boldsymbol{v}^{(0)}\)が成り立ち、固有値は1になる。また、行列式は固有値の積で書けるので、残りの固有値は\(\det(T^{t}) =1-p-q\)だ。転置行列ともとの行列の固有値は全て等しいので\(T\)の固有値は\(1, 1 - p - q\)になる。全て異なる固有値を持つ行列の固有ベクトルは線形独立で、一般に次元dのとき、任意のd次元ベクトルは線形独立なd個のベクトルで展開できるので、任意のベクトルは固有ベクトルで展開できる。

固有ベクトル

固有方程式にそれぞれの固有値を代入して、それに対応する固有ベクトルを計算する。結果は
\[
\left(\boldsymbol{v}^{(1)}\right)^{t} = (q, p),~~
\left(\boldsymbol{v}^{(2)}\right)^{t} = (1, -1)
\]
になる。

n年目C[i]国にいる確率

\(\boldsymbol{p}_{n} = (a_{n},b_{n})^{t}\)と書くことにすると\(\boldsymbol{p}_{n} = T^{n}\boldsymbol{p}_{0}\)である。\(\boldsymbol{p}_{0}\)を固有ベクトルで展開すれば、\(T^{n}\boldsymbol{v}^{(i)} = \lambda_{i}^{n}\boldsymbol{v}^{(i)}\)になるので、すぐさま\(\boldsymbol{p}_{n}\)を求めることができるので、さいごに展開係数を求める。\(\boldsymbol{p}_{0} = c_{1}\boldsymbol{v}^{(1)} + c_{2}\boldsymbol{v}^{(2)}\)とすると、規格化条件から\(c_{1}=1/(p+q)\)に決まり、\((\boldsymbol{p}_{0})_{1} = r\)とすると\(c_{2} = r-q/(p+q)\)に決まる。\(r=1/2\)にすると本の結果に一致する。

宣伝

最後まで読んでくださりありがとうございます。数学ガール/乱択アルゴリズムに登場する擬似コードの実行環境『Hello Algorithm』を開発しています。よろしくお願いします。