離散時間マルコフ連鎖

離散時間マルコフ連鎖は、整数時間において可算個の状態間を遷移し、現在の状態のみに依存する確率から次の状態を選択します。これらの確率は遷移行列に簡潔に符号化されます。

Definition

離散時間マルコフ連鎖は、可算集合内のランダムな状態のシーケンスであり、次の状態の確率は現在の状態のみに依存し、これらの1ステップ確率は遷移行列にまとめられます。

Scope

このトピックでは、遷移行列とチャップマン-コルモゴロフ方程式、強マルコフ性、状態の分類（通信クラス、一時的、零再帰的、正再帰的）、周期性、初回通過確率と初回通過期待時間（初回通過解析によって計算）、および整数格子上のランダムウォークにおける再帰の二分法について扱います。

Core questions

• 遷移行列は、多段階にわたる連鎖のダイナミクスをどのように符号化するのでしょうか？
• 状態は、その通信構造と再帰性によってどのように分類されるのでしょうか？
• 初回通過確率と初回通過期待時間はどのように計算されるのでしょうか？
• どのランダムウォークが確実に開始点に戻り、どれが無限に逃れるのでしょうか？

Key concepts

• 遷移行列
• チャップマン-コルモゴロフ方程式
• 通信クラス
• 再帰性と一時性
• 初回通過時間

Key theories

強マルコフ性

マルコフ性は、停止時間と呼ばれる適切なランダムな時点でも引き続き保持されます。したがって、連鎖はその時点での状態から新たに再開され、これは再帰、逸脱、および初回通過時間を分析するための重要なツールとなります。

再帰の二分法

各状態は、確率1で無限回訪問される再帰的状態であるか、または有限回しか訪問されない一時的状態のいずれかです。単純対称ランダムウォークの場合、これは次元に依存し、1次元および2次元では再帰的であり、3次元以上では一時的です。

Clinical relevance

離散時間マルコフ連鎖は、ボードゲーム、在庫および待ち行列システム、PageRank連鎖によるウェブナビゲーション、遺伝的および生態学的遷移をモデル化します。その初回通過時間および再帰理論は、システムが目標状態に到達するまで、または参照条件に戻るまでにどれくらいの時間がかかるかという実用的な問いに答えます。

History

マルコフは1906年にこれらの連鎖を導入し、プーシキンの詩における母音と子音のシーケンスに適用することで、依存変数に対しても大数の法則が成り立つことを示しました。ポリアによる1921年のランダムウォークの解析は、彼の影響を強く受けている次元依存の再帰の二分法を確立しました。

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

再帰状態と一時状態の違いは何ですか？

再帰状態とは、連鎖が確実にそこに戻り、無限回訪問する状態であるのに対し、一時状態は、連鎖が永久に離れてしまう前に有限回しか訪問されない状態です。

単純ランダムウォークが低次元では再帰的であるのに、高次元ではそうでないのはなぜですか？

1次元および2次元では、ウォークは確率1で原点に戻りますが、3次元以上では逃れるのに十分な空間があるため、ウォークは有限回しか戻らず、一時的になります。これはポリアの古典的な結果です。