Wizard Notes

Python, JavaScript を使った音楽信号分析の技術録、作曲活動に関する雑記

マルコフ連鎖で定常分布を固有値問題として算出するときの注意点

マルコフ連鎖でコード進行を自動生成 において、定常分布を求めるのに少し分かりにくい箇所ががあったので説明します。

マルコフ連鎖の定常分布は、遷移行列の固有値1に対応する固有ベクトル確率密度関数として正規化することで算出することができます。

ここで、マルコフ連鎖でコード進行を自動生成 のように、遷移行列 P の各行ベクトルが、ある状態において次の各状態への遷移確率を格納しているとします。

その前提で、任意の初期状態 s に対して以下のように(極限分布である)定常分布 π を考えます。

f:id:Kurene:20191109105610p:plain

このとき、π は次の式を満たします。

f:id:Kurene:20191109105624p:plain

np.linalg.eig() などを使ってこの固有値問題を解けばよいのですが、式の通り、この遷移行列 P の定義では、P の転置行列に関して固有値問題を解く必要があります。

つまり、np.linalg.eig()を使う場合は次のようになります。 多くの場合、遷移行列は非対称行列となるため注意が必要です。

eig_val, eig_vec = np.linalg.eig(P.T)

固有値 eig_val固有ベクトル eig_vec が得られたら、固有値が1の固有ベクトルを取り出します。その後、総和で正規化し、確率密度関数化します。なお、遷移行列は実非対称行列であるため、固有値固有ベクトル複素数が出てきます

idx = np.argmin(np.abs(np.real(eig_val) - 1))
w = np.real(eig_vec[:, idx]).T 
w /= np.sum(w)

以上の処理により、定常分布 w を漸化式を使わず固有値分解で得ることができました。

ただし、極限分布である定常分布を持つ場合には、

  • 既約・到達可能 (Irreducible, accessible) :どの状態から開始しても、任意の状態に到達可能
  • 非周期性 (aperiodic) :定時間後に必ず戻ってくるような状態がない
  • 状態数が有限

の3つの性質を満たす必要があります。 このとき、そのマルコフモデルはエルゴート性を持つといいます。

例えば、遷移行列が対角行列のとき、(0以外の)固有値は全て1になり、定常分布は極限分布とはなりません。

参考文献