PR

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

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

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

P(Xn+1=j|Xn=i,⋯,X0=i0)=P(Xn+1=j|Xn=i)

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

参考 マルコフ連鎖について詳しくはこちら！

マルコフ連鎖とは？数式と具体例を通してわかりやすく解説
どうも！初めましての方は初めまして、初心者のWebサイト勉強のとみーです！ 待ち行列理論や確率過程について勉強していると出会うのが、マルコフ連鎖です。 とみー 今回は、そのマルコフ連鎖についてわかりやすくまとめてみました！ 対象レベル 確率...
www.beginner-blogger.com
とみー
とみー

今回はその判定法を２つ解説します！

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

対象レベル

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

スポンサーリンク

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

定理

定理

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

また、別の集合 F 上で値を取る独立同分布の確率変数列 {Zn}n≥0 について、{Zn} と X0 は独立であるとする。

このとき、ある関数 f:E×F⟶E が存在し、

Xn+1=f(Xn,Zn)

が成り立つならば、{Xn}n≥0 は斉時的なマルコフ連鎖となる。

P(Xn+1=j|Xn=i,Xn−1=in−1,⋯,X0=i0)=P(f(Xn―,Zn)=j|Xn=i,Xn−1=in−1,⋯,X0=i0)=P(f(i,Zn)=j|Xn=i,Xn−1=in−1,⋯,X0=i0)

与えられた条件より

Xn=f(Xn−1,Zn−1)=f(f(Xn−2,Zn−2))=⋯=f(⋯(f(X0,Z0),Z1)⋯,Zn−1)

が成り立つから、Xn は X0,Z0,⋯,Zn−1 の関数である。

よって、Xn は Zn とは独立であり、同様にして {X0,⋯,Xn} はすべて Zn とは独立であることがわかる。

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

P(f(i,Zn)=j|Xn=i,Xn−1=in−1,⋯,X0=i0)=P(f(i,Zn)=j)

となる。ここで、P(f(i,Zn)=j) は i,j だけの関数だから、

P(f(i,Zn)=j)=P(Xn+1=j|Xn=i)=P(Xn=j|Xn−1=i)=⋯=P(X1=j|X0=i)

以上をまとめると、

P(Xn+1=j|Xn=i,Xn−1=in−1,⋯,X0=i0)=P(Xn+1=j|Xn=i)=P(Xn=j|Xn−1=i)=⋯=P(X1=j|X0=i)

推移確率

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

pij=P(f(i,Zn)=j)

で求められます。

pij=P(Xn+1=j|Xn=i)=P(f(Xn,Zn)=j|Xn=i)=P(f(i,Zn)=j|Xn=i)=P(f(i,Zn)=j)

例題

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

とみー
とみー

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

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

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

このとき、

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

としましょう。

独立性の確認

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

  1. {Zn} が独立同分布であること
  2. X0 と {Zn} が独立であること

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

{Zn} が独立同分布

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

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

X0 と Zn が独立

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

とみー
とみー

それでは定理を使うために、Xn+1 を式で表してみましょう！

Xn=0 の場合

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

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

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

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

Xn+1=Zn

となります。

Xn≥1 の場合

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

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

Xn+1=Xn–1+Zn

となります。

Xn の漸化式

以上を踏まえると、

Xn+1={Zn(Xn=0)Xn+Zn–1(Xn≥1)

です。よって、どちらの場合も Xn+1 は Xn と Zn の関数になっています。

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

スポンサーリンク

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

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

とみー
とみー

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

それが、次の定理です。

定理

定理

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

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

状態遷移図とは

状態遷移図というのは、

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

をまとめた図です。

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

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

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

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

例題

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

１日にスマホが k 個壊れる確率を qk とすると、{Zn} は独立同分布なので

∀n∈Z+,P(Zn=k)=qk

です。

Z+ は０以上の整数の集合です。

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

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

とみー
とみー

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

スポンサーリンク

まとめ

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

とみー
とみー

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

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

コメント

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