マルコフ連鎖の例

確率的構成の例

この記事には、マルコフ連鎖とマルコフ過程の実際の例が含まれています。

すべての例は可算状態空間にあります。一般状態空間におけるマルコフ連鎖の概要については、可測状態空間におけるマルコフ連鎖を参照してください。

離散時間

サイコロを使ったボードゲーム

ヘビと梯子のゲームや、動きが完全にサイコロで決定されるその他のゲームはマルコフ連鎖、まさに吸収マルコフ連鎖です。これは、カードが過去の動きの「記憶」を表すブラックジャックなどのカードゲームとは対照的です。違いを確認するには、ゲーム内のあるイベントの確率を考えてみましょう。上記のサイコロゲームでは、重要なのはボードの現在の状態だけです。ボードの次の状態は、現在の状態と次のサイコロの出目によって決まります。現在の状態になった経緯は関係ありません。ブラックジャックなどのゲームでは、プレーヤーはどのカードがすでに公開されたか（つまり、どのカードがデッキにもう存在しないか）を覚えておくことで有利になるため、ゲームの次の状態（またはハンド）は過去の状態から独立していません。

ランダムウォークマルコフ連鎖

中心偏向ランダムウォーク

数直線上のランダムウォークを考えてみましょう。各ステップで、位置 ( xと呼ぶ) が +1 (右へ) または -1 (左へ) 変化する確率は次のとおりです。

P_{\mathrm {move~left} }={\dfrac {1}{2}}+{\dfrac {1}{2}}\left({\dfrac {x}{c+|x|}}\right)

P_{\mathrm {右へ移動} }=1-P_{\mathrm {左へ移動} }

（cは0より大きい定数）

例えば、定数cが 1 の場合、位置x = −2, −1, 0, 1, 2 における左への移動の確率はそれぞれ次のように表されます。ランダムウォークには中心化効果があり、 c が増加するにつれてその効果は弱まります。 ${\dfrac {1}{6}},{\dfrac {1}{4}},{\dfrac {1}{2}},{\dfrac {3}{4}},{\dfrac {5}{6}}$

確率は現在の位置（xの値）のみに依存し、以前の位置に依存しないため、この偏りのあるランダムウォークはマルコフ連鎖の定義を満たします。

ギャンブル

10 ドルから始めて、1 ドルずつ、終わりのない公平なコイン投げを無期限に、あるいはすべてのお金を失うまで続けるとします。がn 回投げた後のドルの枚数を表し、である場合、シーケンスはマルコフ過程です。現在 12 ドルを持っていることがわかっている場合、均等なオッズであれば、次の投げ後に 11 ドルか 13 ドルを持っていることが予想されます。この推測は、10 ドルから始めて、その後 11 ドルまで上がり、10 ドルまで下がり、11 ドルまで上がり、最後に 12 ドルになったという追加の知識によって改善されることはありません。以前の投げの知識によって推測が改善されないという事実は、マルコフ性、つまり確率過程の記憶のない特性を示しています。^[1] $X_{n}$ $X_{0}=10$ $\{X_{n}:n\in \mathbb {N} \}$

言語のモデル

この例はマルコフ自身によるものです。^[2]マルコフはプーシキンの『エフゲニー・オネーギン』から2万字を選び、母音と子音に分類し、遷移確率を数えました。定常分布は母音が43.2%、子音が56.8%で、これは実際の数に近い値です。^[3] ${\begin{array}{lll}&{\text{母音}}&{\text{子音}}\\{\text{母音}}&.128&.872\\{\text{子音}}&.663&.337\end{array}}$

シンプルな気象モデル

前日の天気を考慮した気象条件（雨または晴れとしてモデル化）の確率は、遷移行列で表すことができます。

P={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}

行列Pは、晴れた日の後には90%の確率で晴れの日が続き、雨の日の後には50%の確率で雨の日が続くという気象モデルを表しています。列には「晴れ」と「雨」のラベルを付け、行には同じ順序でラベルを付けることができます。

( P ) _ijは、特定の日がタイプiの場合、その次にタイプjの日が続く確率です。

Pの行の合計が 1 になることに注意してください。これは、Pが確率行列であるためです。

天気を予測する

0日目（今日）の天気は晴れであると分かっています。これは、「晴れ」の要素が100%、「雨」の要素が0%の初期状態ベクトルで表されます。

\mathbf {x} ^{(0)}={\begin{bmatrix}1&0\end{bmatrix}}

1 日目 (明日) の天気は、0 日目の状態ベクトルに遷移行列を掛けることで予測できます。

\mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}P={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.9&0.1\end{bmatrix}}

したがって、1 日目も晴れる可能性は 90% です。

2 日目 (明後日) の天気は、1 日目に計算した状態ベクトルから同様に予測できます。

\mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P=\mathbf {x} ^{(0)}P^{2}={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}^{2}={\begin{bmatrix}0.86&0.14\end{bmatrix}}

または

\mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P={\begin{bmatrix}0.9&0.1\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.86&0.14\end{bmatrix}}

n日目の一般的なルールは次のとおりです。

\mathbf {x} ^{(n)}=\mathbf {x} ^{(n-1)}P

\mathbf {x} ^{(n)}=\mathbf {x} ^{(0)}P^{n}

天候の安定

この例では、より遠い日の天気予報は、日が経つにつれて変化が小さくなり、定常状態のベクトルに近づく傾向があります。このベクトルは、すべての日の晴天と雨天の確率を表し、初期の天気とは無関係です。

定常状態ベクトルは次のように定義されます。

\mathbf {q} =\lim _{n\to \infty }\mathbf {x} ^{(n)}

しかし、 P が正規の遷移行列である場合にのみ、厳密に正のベクトルに収束します(つまり、すべての要素がゼロでない P ^{n が少なくとも 1 つ存在します)。}

qは初期条件に依存しないため、 Pで変換しても変化しない。^[4] これによりqは固有ベクトル（固有値1）となり、 Pから導出できる。

簡単に言えば、定常ベクトルとは、Pを掛け合わせたときに全く同じベクトルが返されるベクトルのことです。^[5]天気の例では、これを使って行列方程式を立てることができます。

{\begin{aligned}P&={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}\\\mathbf {q} P&=\mathbf {q} &&{\text{(}}\mathbf {q} {\text{ is unchanged by }}P{\text{.)}}\\&=\mathbf {q} I\\\mathbf {q} (P-I)&=\mathbf {0} \\\mathbf {q} \left({\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}-{\begin{bmatrix}1&0\\0&1\end{bmatrix}}\right)&=\mathbf {0} \\\mathbf {q} {\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}&=\mathbf {0} \\{\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}{\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}&={\begin{bmatrix}0&0\end{bmatrix}}\\-0.1q_{1}+0.5q_{2}&=0\end{aligned}}

そして、それらは確率ベクトルなので、

q_{1}+q_{2}=1.

この2つの同時方程式を解くと、定常状態ベクトルが得られます。

{\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}={\begin{bmatrix}0.833&0.167\end{bmatrix}}

結論として、長期的には約83.3%の日が晴れとなります。すべてのマルコフ過程が定常状態ベクトルを持つわけではありません。特に、遷移行列は正則でなければなりません。そうでなければ、状態ベクトルは収束することなく時間の経過とともに振動し続けます。

株式市場

右図は、簡単な例の状態遷移図です。有向グラフを用いて状態遷移を表しています。状態は、仮想の株式市場が特定の週において強気相場、弱気相場、停滞のいずれのトレンドを示しているかを表しています。図によると、強気相場の週の後にはさらに強気相場が続く確率は90%、弱気相場の週は7.5%、停滞相場の週は残りの2.5%です。状態空間に{1 = 強気相場、2 = 弱気相場、3 = 停滞相場}とラベルを付けると、この例の遷移行列は次のようになります。

P={\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}.

状態分布は、確率的行ベクトル $x$ として表すことができ、関係 $x (n + 1) = x (n) P$ を持つ。したがって、時刻 $n$ においてシステムが状態 $x (n)$ にある場合、3期間後の時刻 $n + 3$ における分布は、

{\begin{aligned}x^{(n+3)}&=x^{(n+2)}P=\left(x^{(n+1)}P\right)P\\\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P\right)P^{2}\\&=x^{(n)}P^{3}\\\end{aligned}}

特に、時刻 $nで$ システムが状態2（弱気）にある場合、時刻 $n + 3$ では分布は

{\begin{aligned}x^{(n+3)}&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}^{3}\\[5pt]&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.7745&0.17875&0.04675\\0.3575&0.56825&0.07425\\0.4675&0.37125&0.16125\\\end{bmatrix}}\\[5pt]&={\begin{bmatrix}0.3575&0.56825&0.07425\end{bmatrix}}.\end{aligned}}

遷移行列を用いることで、例えば、市場が停滞する週の長期的な割合や、停滞相場から強気相場に移行するまでの平均週数を計算することができます。遷移確率を用いた定常状態確率は、以下の理由により、62.5%の週が強気相場、31.25%の週が弱気相場、6.25%の週が停滞相場となることを示しています。

\lim _{N\to \infty }\,P^{N}={\begin{bmatrix}0.625&0.3125&0.0625\\0.625&0.3125&0.0625\\0.625&0.3125&0.0625\end{bmatrix}}

詳細な展開と多くの例は、オンラインモノグラフMeyn & Tweedie 2005に記載されています。^[6]

有限状態機械はマルコフ連鎖の表現として用いることができます。独立かつ同一分布に従う入力信号（例えば、コイントスで選ばれた2進アルファベットの記号）の系列を仮定すると、機械が時刻nにおいて状態yにある場合、時刻n + 1 において状態xに遷移する確率は、現在の状態のみに依存します。

連続時間

誕生と死のプロセス

オーブンで100粒のポップコーンを弾けさせるとします。それぞれの粒が独立な指数分布の時刻で弾けた場合、これは連続時間マルコフ過程となります。時刻tまでに弾けた粒の数をとすると、問題は「後の時刻に弾けたであろう粒の数を求める」と定義できます。必要なのは、時刻「t」より前に弾けた粒の数だけです。弾けた時刻を知る必要はないので、それ以前の時刻「t」を知ることは重要ではありません。 $X_{t}$ $X_{t}$

ここで説明するプロセスはポアソン点過程の近似です。ポアソン過程はマルコフ過程でもあります。

参照

参考文献

^ Øksendal, BK (Bernt Karsten), 1945- (2003).確率微分方程式：応用入門（第6版）. ベルリン: Springer. ISBN 3540047581 OCLC 52203046 。{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ Markov, AA「エフゲニー・オネーギンのテキストの統計分析例：試行の連鎖の関連性を示す」サンクトペテルブルク帝国科学アカデミー紀要、第6巻（1913年）：153162。
^ グリンステッドとスネルの確率論入門、465ページ
^ Van Kampen, NG (2007).物理と化学における確率過程. オランダ: ノースホラントエルゼビア. pp. 73–95. ISBN 978-0-444-52965-7。
^ 「マルコフ過程による定常状態への移行」Bloomington Tutors.
^ SP MeynとRL Tweedie、2005年。マルコフ連鎖と確率的安定性。2013年9月3日アーカイブ、Wayback Machineにて。

外部リンク

マルコフ連鎖としての独占

[:3-1] Øksendal, BK (Bernt Karsten), 1945- (2003).確率微分方程式：応用入門（第6版）. ベルリン: Springer. ISBN 3540047581 OCLC 52203046 。{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)

[2] Markov, AA「エフゲニー・オネーギンのテキストの統計分析例：試行の連鎖の関連性を示す」サンクトペテルブルク帝国科学アカデミー紀要、第6巻（1913年）：153162。

[3] グリンステッドとスネルの確率論入門、465ページ

[:1-4] Van Kampen, NG (2007).物理と化学における確率過程. オランダ: ノースホラントエルゼビア. pp. 73–95. ISBN 978-0-444-52965-7。

[5] 「マルコフ過程による定常状態への移行」Bloomington Tutors.

[MCSS-6] SP MeynとRL Tweedie、2005年。マルコフ連鎖と確率的安定性。2013年9月3日アーカイブ、Wayback Machineにて。