pjt222 マルコフ連鎖のモデリング
生の遷移データまたはドメイン仕様から離散時間または連続時間マルコフ連鎖を構築、分類、分析し、定常分布、平均初到達時間、シミュレーションベースの検証を生成する。DTMCとCTMCの両方のワークフローをエンドツーエンドで網羅する。
使用タイミング
- 将来の状態が現在の状態のみに依存するシステム（記憶なし性質）をモデル化する必要がある時
- 有限の状態集合間の遷移カウントまたはレートが観測されている時
- プロセスの長期的な定常状態確率を計算したい時
- 期待到達時間または吸収確率を決定する必要がある時
- 構造分析のために状態を一時的、再帰的、または吸収的に分類する時
- 同じシステムに対する代替マルコフモデルを比較したい時
- より高度なモデル（隠れマルコフモデル、強化学習MDP）の基礎を構築する時
入力
必須
| 入力 | 型 | 説明 |
|---|---|---|
state_space |
list/vector | 連鎖内のすべての状態の網羅的列挙 |
transition_data |
matrix, data frame, or edge list | 生の遷移カウント、確率行列、またはレート行列（CTMCの場合） |
chain_type |
string | "discrete"（DTMC）または"continuous"（CTMC） |
任意
| 入力 | 型 | デフォルト | 説明 |
|---|---|---|---|
initial_distribution |
vector | uniform | 開始状態確率 |
time_horizon |
integer/float | 100 | シミュレーションのステップ数（DTMC）または時間単位（CTMC） |
tolerance |
float | 1e-10 | 反復計算の収束許容度 |
absorbing_states |
list | auto-detect | 吸収的と明示的にマークされた状態 |
labels |
list | state indices | 各状態の人間が読める名前 |
method |
string | "eigen" |
ソルバー方法: "eigen"、"power"、または"linear_system" |
手順
ステップ1: 状態空間と遷移の定義
1.1. すべての異なる状態を列挙する。リストが網羅的かつ排他的であることを確認する。
1.2. 生の観測から作業する場合、遷移カウントをn x nのカウント行列Cに集計する。ここでC[i,j]は状態iから状態jへの観測された遷移数である。
1.3. 連続時間連鎖の場合、遷移先と共に各状態での滞在時間を収集する。
1.4. すべての観測された起点と目的地が状態空間に含まれることを確認し、列挙から欠落している状態がないか検証する。
1.5. データソース、観測期間、適用されたフィルタリングを文書化する。この来歴記録は分析の再現と異常の説明に不可欠である。
期待結果: サイズnの明確に定義された状態空間と、すべての観測された遷移をカバーするカウント行列または（起点、目的地、レート/カウント）タプルのリスト。状態空間は行列演算に十分小さくあるべきである（密な方法では通常n < 10000）。
失敗時: 状態が欠落している場合、ソースデータを再調査し列挙を拡張する。状態空間が行列方法には大きすぎる場合、まれな状態を集約「その他」状態にまとめるか、シミュレーションベースの分析に切り替えることを検討する。カウント行列が極度にスパースな場合、観測期間が典型的な遷移を捕捉するのに十分長いか検証する。
ステップ2: 遷移行列または生成子の構築
2.1. 離散時間（DTMC）: カウント行列の各行を正規化して遷移確率行列Pを取得する:
P[i,j] = C[i,j] / sum(C[i,])- すべての行の和が1であることを検証する（許容度内で）。
2.2. 連続時間（CTMC）: レート（生成子）行列Qを構築する:
- 非対角:
Q[i,j] = iからjへの遷移レート - 対角:
Q[i,i] = -sum(Q[i,j] for j != i) - すべての行の和が0であることを検証する（許容度内で）。
2.3. ゼロカウント行（起点として一度も観測されなかった状態）をスムージング戦略で処理する: ラプラススムージング、吸収規約、またはレビュー用のフラグ立て。
2.4. 下流の計算に適した形式で行列を保存する（小さな連鎖には密、大きなものにはスパース）。
期待結果: 有効な確率的行列P（行の和が1）または生成子行列Q（行の和が0）。Pに負の非対角要素がなく、Qに正の対角要素がないこと。
失敗時: 行の和が許容度を超えて逸脱する場合、データの破損または浮動小数点の問題を確認する。再正規化またはソースデータの再調査を行う。
ステップ3: 状態の分類
3.1. 遷移行列によって誘導される有向グラフの強連結成分を見つけることにより、通信クラスを計算する（正の確率を持つ辺のみ）。
3.2. 各通信クラスについて決定する:
- 他のクラスへの出発辺がない場合は再帰的。
- 出発辺がある場合は一時的。
- クラスが
P[i,i] = 1の単一状態で構成される場合は吸収的。
3.3. クラス内の任意の状態から到達可能なすべてのサイクル長のGCDを計算して、各再帰クラスの周期性を確認する。
- 周期 = 1は非周期的を意味する。
3.4. 連鎖が既約（単一通信クラス）か可約（複数クラス）かを決定する。
3.5. 要約する: 各クラスとそのタイプ（一時的/再帰的）、周期、吸収状態の有無をリストする。
期待結果: 完全な分類: すべての状態が通信クラスに割り当てられ、ラベル（一時的、正再帰的、零再帰的、吸収的）と周期性が付与されていること。
失敗時: グラフ分析が矛盾する場合、遷移行列に負のエントリがなく、行の和が正しいことを検証する。非常に大きな連鎖の場合、完全な行列べき乗の代わりに反復グラフアルゴリズムを使用する。
ステップ4: 定常分布の計算
4.1. 既約非周期連鎖: sum(pi) = 1の制約の下でpi * P = piを解く。
pi * (P - I) = 0に正規化制約を加えて再定式化する。- 固有値分解を使用する:
piは固有値1に対応するPの左固有ベクトルであり、和が1になるよう正規化する。
4.2. 既約周期連鎖: 定常分布は存在するが、連鎖は任意の初期状態からそれに収束しない。4.1と同じ方法で計算する。
4.3. 可約連鎖: 各再帰クラスの定常分布を独立に計算する。全体の定常分布は一時的状態からの吸収確率に依存する凸結合である。
4.4. CTMC: sum(pi) = 1の下でpi * Q = 0を解く。
4.5. 検証: 計算されたpiをP（またはQ）に乗じ、結果が許容度内でpiに等しいことを確認する。
4.6. 可約連鎖の場合、各一時的状態から各再帰クラスへの吸収確率を計算する。これらの確率をクラス別定常分布と組み合わせることで、開始状態に条件付けた長期的な挙動が得られる。
4.7. スペクトルギャップ（最大と2番目に大きい固有値の大きさの差）を記録する。この量は定常状態への収束率を支配し、ステップ6で必要なシミュレーションステップ数の決定に有用である。
期待結果: 長さnの確率ベクトルpi。すべてのエントリが非負、和が1、許容度内で平衡方程式を満たすこと。非周期既約連鎖ではスペクトルギャップが正であるべきである。
失敗時: 固有値ソルバーが収束しない場合、反復べき乗法（pi_k+1 = pi_k * Pを収束まで）を試みる。複数の固有値が1に等しい場合、連鎖は可約である — ステップ4.3に従って処理する。スペクトルギャップが極めて小さい場合、連鎖の混合が遅く、検証に非常に長いシミュレーションが必要になる。
ステップ5: 平均初到達時間の計算
5.1. 平均初到達時間m[i,j]を、状態iから開始して状態jに到達するまでの期待ステップ数として定義する。
5.2. 既約連鎖の場合、線形方程式系を解く:
m[i,j] = 1 + sum(P[i,k] * m[k,j] for k != j)すべてのi != jに対してm[j,j] = 1 / pi[j]（平均再帰時間）
5.3. 吸収連鎖の場合、吸収確率と吸収までの期待時間を計算する:
Pを一時的（Q_t）ブロックと吸収ブロックに分割する。- 基本行列:
N = (I - Q_t)^{-1} - 吸収までの期待ステップ:
N * 1（1の列ベクトル） - 吸収確率:
N * RここでRは一時的から吸収的へのブロック。
5.4. CTMCの場合、生成子行列を使用してステップカウントを期待滞在時間で置換する。
5.5. 主要な状態ペアのペアワイズ初到達時間の行列またはテーブルとして結果を提示する。
期待結果: 対角エントリが平均再帰時間（1/pi[j]）に等しく、通信する状態ペアの非対角エントリが有限である平均初到達時間の行列。
失敗時: 線形系が特異な場合、連鎖にターゲットに到達できない一時的状態がある。到達不可能なペアを無限大として報告する。ステップ3の連鎖構造を検証する。
ステップ6: シミュレーションによる検証
6.1. 初期分布から開始して、連鎖のK本の独立なサンプルパスを各Tステップシミュレートする。
6.2. バーンイン期間を除外した後、すべてのパスにわたる状態占有頻度をカウントして、定常分布を経験的に推定する。
6.3. シミュレートされた頻度を解析的定常分布と比較する。全変動距離またはカイ二乗統計量を計算する。
6.4. 反復にわたって各ターゲット状態の初到達時間を記録し、平均初到達時間を経験的に推定する。
6.5. 一致の指標を報告する:
- 解析的とシミュレートされた定常確率間の最大絶対偏差。
- シミュレートされた初到達時間の95%信頼区間 vs 解析値。
6.6. 不一致が許容度を超える場合、遷移行列の構築と分類ステップを再調査する。
期待結果: シミュレートされた定常分布が解析解の全変動距離0.01以内にあること（十分に長い実行の場合）。シミュレートされた平均初到達時間が解析値の10%以内にあること。
失敗時: シミュレーション長Tまたは反復数Kを増加する。不一致が持続する場合、解析解に数値エラーがある可能性がある — より高い精度で再計算する。
バリデーション
- 遷移行列
Pのすべてのエントリが非負で、各行の和が1であること（CTMCの場合Qの行の和が0） - 定常分布
piがpi * P = piを満たす有効な確率ベクトルであること - 各再帰状態
jについて平均再帰時間が1/pi[j]に等しいこと - シミュレートされた状態頻度が解析的定常分布に収束すること
- 状態分類が一貫していること: 再帰状態がその通信クラスを離れる辺を持たないこと
Pのすべての固有値の大きさが最大1で、再帰クラスごとにちょうど1つの固有値が1に等しいこと- 吸収連鎖の場合: 各一時的状態からの吸収確率がすべての吸収クラスにわたって1に合計すること
- 基本行列
N = (I - Q_t)^{-1}のすべてのエントリが正であること（期待訪問カウントは正） - 連鎖が可逆である場合かつその場合に限り詳細バランスが成り立つ: すべての
i,jに対してpi[i] * P[i,j] = pi[j] * P[j,i]
よくある落とし穴
- 非網羅的状態空間: 欠落した状態は部分確率的行列（行の和が1未満）を生成する。分析前に常に行の和を検証すること。
- DTMCとCTMCの混同: レート行列は非正の対角と行の和が0でなければならない。レート行列にDTMC公式を適用すると無意味な結果を生む。
- 周期性の無視: 周期連鎖は有効な定常分布を持つが、通常の意味ではそれに収束しない。混合時間分析は周期を考慮しなければならない。
- 大きな連鎖での数値不安定性: 大きな密行列の固有値分解は計算コストが高く精度を失う可能性がある。数百以上の状態の連鎖にはスパースソルバーまたは反復法を使用する。
- ゼロ確率遷移: 遷移行列の構造的ゼロは連鎖を可約にする可能性がある。単一の定常分布を計算する前に既約性を検証すること。
- 不十分なシミュレーション長: 混合が不良な短いシミュレーションはバイアスのある推定を生む。常に有効サンプルサイズを計算し、トレースプロットを確認すること。
- 検証なしの可逆性の仮定: 多くの解析的ショートカット（例: 詳細バランス）は可逆連鎖にのみ適用される。可逆性に依存する結果を使用する前に
pi[i] * P[i,j] = pi[j] * P[j,i]を検証すること。 - べき乗法での浮動小数点蓄積:
pi * Pを多数回反復すると丸め誤差が蓄積する。べき乗反復中に定期的にpiを和が1になるよう再正規化すること。
関連スキル
- Fit Hidden Markov Model -- マルコフ連鎖を観測された放出を持つ潜在状態モデルに拡張する
- Simulate Stochastic Process -- マルコフ連鎖のサンプルパスとモンテカルロ検証に適用可能な一般的なシミュレーションフレームワーク