PR

マルコフ連鎖の判定法と状態遷移図

マルコフ連鎖の判定法と状態遷移図 確率過程
記事内に広告が含まれています。
スポンサーリンク

どうも!初めましての方は初めまして、初心者のWebサイト勉強のとみーです!

$$\mathbb{P}(X_{n+1} = j | X_n = i, \color{red}\cdots, X_0 = i_0\color{black}) = \mathbb{P}(X_{n+1} = j | X_n = i)$$

を満たす確率過程はマルコフ連鎖と呼ばれ、確率過程の話の中でよく登場します。

とみー
とみー

今回はその判定法を2つ解説します!

数式が得意な方は判定法①、苦手な方は判定法②を使いましょう。

対象レベル

確率の基本的な知識がある方(高校数学〜大学入門)

スポンサーリンク

斉時的なマルコフ連鎖の判定法①

定理

定理

ある集合 $E$ 上で値を取る確率変数 $X_0$ があるとする。

また、別の集合 $F$ 上で値を取る独立同分布の確率変数列 $\{Z_n\}_{n\geq0}$ について、$\{Z_n\}$ と $X_0$ は独立であるとする。

このとき、ある関数 $f: E\times F \longrightarrow E$ が存在し、

$$X_{n+1} = f(X_n, Z_n)$$

が成り立つならば、$\{X_n\}_{n \geq 0}$ は斉時的なマルコフ連鎖となる。

\begin{eqnarray} &&\mathbb{P}(\color{red}X_{n+1}\color{black}=j|X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) \\ &=& \mathbb{P}(\color{red}f(\color{blue}\underline{\color{red}X_n}\color{red}, Z_n)\color{black}=j|\color{blue}X_n=i\color{black}, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) \\ &=& \mathbb{P}(f(\color{blue}i\color{black}, Z_n)=j|X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) \end{eqnarray}

与えられた条件より

\begin{eqnarray} X_n &=& f(X_{n-1}, Z_{n-1}) \\ &=& f(f(X_{n-2}, Z_{n-2})) \\ &=& \cdots \\ &=& f (\cdots(f(X_0, Z_0), Z_1) \cdots, Z_{n-1}) \end{eqnarray}

が成り立つから、$X_n$ は $X_0, Z_0, \cdots, Z_{n-1}$ の関数である。

よって、$X_n$ は $Z_{\color{red}n}$ とは独立であり、同様にして $\{X_0, \cdots, X_n\}$ はすべて $Z_n$ とは独立であることがわかる。

したがって、条件付き確率の条件は無視できて

\begin{eqnarray} \mathbb{P}(f(i, Z_n)=j|\color{red}X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0\color{black}) = \mathbb{P}(f(i, Z_n)=j) \end{eqnarray}

となる。ここで、$\mathbb{P} (f(i, Z_n) = j)$ は $i, j$ だけの関数だから、

\begin{eqnarray} \mathbb{P} (f(i, Z_n) = j) &=& \mathbb{P} (X_{n+1} = j | X_n = i) \\ &=& \mathbb{P} (X_{n} = j | X_{n-1} = i)\\ &=& \cdots \\ &=& \mathbb{P} (X_1 = j | X_0 = i) \end{eqnarray}

以上をまとめると、

\begin{eqnarray} \mathbb{P}(X_{n+1}=j|X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) &=& \mathbb{P} (X_{n+1} = j | X_n = i) \\ &=& \mathbb{P} (X_{n} = j | X_{n-1} = i)\\ &=& \cdots \\ &=& \mathbb{P} (X_1 = j | X_0 = i) \end{eqnarray}

推移確率

この定理を使うと、状態 $i$ から状態 $j$ への推移確率は

$$p_{ij} = \mathbb{P} (f(i, Z_n) = j)$$

で求められます。

\begin{eqnarray} p_{ij} &=& \mathbb{P} (X_{n+1} = j | X_n = i) \\ &=& \mathbb{P} (f(X_n, Z_n) = j | X_n = i) \\ &=& \mathbb{P} (f(i, Z_n) = j | X_n = i) \\ &=& \mathbb{P} (f(i, Z_n) = j) \\ \end{eqnarray}

例題

定理を適用する例として、ある地域のスマートフォンの修理業者を考えてみましょう。

とみー
とみー

この地域はとても広いので、毎日どこかで誰かのスマートフォンが故障します。

スマートフォンの持ち主は、故障した次の日の朝に修理業者に修理を依頼しにきます。

ただし、スマートフォンの修理には時間がかかるので、1日1台までしか修理できず、修理が完了するのは夕方ごろになります。

このとき、

  • $n$ 日目に壊れたスマホを $Z_n$ 個
  • $n$ 日目の昼時点の未修理台数を $X_n$ 個

としましょう。

独立性の確認

まず、定理を利用するためには、

  1. $\{Z_n\}$ が独立同分布であること
  2. $X_0$ と $\{Z_n\}$ が独立であること

を確認しなければなりません。

$\{Z_n\}$ が独立同分布

普通、今日は壊れやすい日だけど明日は壊れにくい日、といった状況は考えにくいですよね。そのため、ここでは毎日スマホは同じくらい壊れやすい($\{Z_n\}$ は同分布)と考えられます。

また、今日は少ししか壊れなかったから明日はたくさん壊れる、といった因果関係も考えにくいです。なので、$\{Z_n\}$ は互いに独立です。

$X_0$ と ${Z_n}$ が独立

さらに、業者の未修理台数とスマホの壊れる個数には何の関係もないので、$X_0$ と $\{Z_n\}$ は互いに独立です。

とみー
とみー

それでは定理を使うために、$X_{n+1}$ を式で表してみましょう!

$X_n = 0$ の場合

$n$ 日目のお昼の時点で未修理台数が0個の場合、その日は修理を行いません。

故障したスマホが届くのは朝だけです。

そして、次の日の朝には新しく故障したスマホが $Z_n$ 個届きます。

修理が完了するのは夕方なので、$n+1$ 日目のお昼の時点の未修理台数は、

$$X_{n+1} = Z_n$$

となります。

$X_n \geq 1$ の場合

$n$ 日目のお昼の時点で未修理台数が1個以上の場合、その日は修理を行うので、その日の夕方には未修理台数は $X_{n} \, – \, 1$ 個になります。

そして、先ほどの場合と同じように次の日にはまた $Z_n$ 個故障したスマホが届くので、$n+1$ 日目のお昼の時点では、

$$X_{n+1} = X_{n} \, –\, 1 + Z_n$$

となります。

$X_n$ の漸化式

以上を踏まえると、

\begin{eqnarray} X_{n+1} &=& \left \{ \begin{array}{1} Z_n \, &&(X_n = 0)\\ X_n + Z_n \,–\, 1 \, &&(X_n \geq 1) \end{array} \right . \end{eqnarray}

です。よって、どちらの場合も $X_{n+1}$ は $X_n$ と $Z_n$ の関数になっています。

ゆえに、定理より $\{X_n\}$ は(斉時的な)マルコフ連鎖であることがわかります。

スポンサーリンク

斉時的なマルコフ連鎖の判定法②

先ほどの判定法①は数式を使わなければいけないので、少しとっつきにくい部分がありますよね。

とみー
とみー

実は、数式を使わなくても判定できる方法があります。

それが、次の定理です。

定理

定理

確率過程 $\{X_n\}_{n \geq 0}$ は、状態遷移図が描ければ斉時的なマルコフ連鎖である。

状態遷移図というものが作成できれば、それだけでOKという便利な定理です。

状態遷移図とは

状態遷移図というのは、

  • どの状態からどの状態に
  • どの確率で遷移するか

をまとめた図です。

ある状態からある状態への矢印(遷移)が書けるということは、

次の状態は1つ前の状態だけで決まる

というマルコフ性の証明です。

また、状態遷移図に時刻 $n$ の情報がないことから分かる通り、状態間の遷移に時刻は関係ないので、これは斉時的なマルコフ連鎖です。

例題

それでは定理を使ってみましょう。題材は、引き続き先ほどのスマホ修理業者です。

1日にスマホが $k$ 個壊れる確率を $q_k$ とすると、$\{Z_n\}$ は独立同分布なので

$$\forall n \in \mathbb{Z}_+, \quad \mathbb{P} (Z_n = k) = q_k$$

です。

$\mathbb{Z}_+$ は0以上の整数の集合です。

この確率を使うと、次のような $\{X_n\}$ の状態遷移図が描けます。

定理から「状態遷移図が描ける=斉時的なマルコフ連鎖」なので、$\{X_n\}$ は斉時的なマルコフ連鎖です。

とみー
とみー

判定法①の結果と一致していますね。

スポンサーリンク

まとめ

今回は、マルコフ連鎖の判定法をご紹介しました。

とみー
とみー

状態遷移図が描ける場合は積極的に②の判定法を使いたいですね!

確率過程のおすすめ
スポンサーリンク

コメント

タイトルとURLをコピーしました