マルコフ連鎖

マルコフ連鎖について

マルコフ連鎖は、次の状態が現在の状態のみに依存する（記憶なし特性）、固定された遷移確率で状態間を遷移するシステムをモデル化します。信頼性モデリング、待ち行列理論、PageRank、ギャンブラーの破産問題、気象モデルの基盤となっています。各状態からの遷移確率の合計は1でなければなりません（行確率的行列）。

Schematexの強みは、エンジンが丸と矢印を描くだけでなく線形代数の計算を行うことにあります。行確率的行列を検証し、SCC分析によって状態（過渡 / 再帰 / 吸収）を分類し、定常分布 π または吸収連鎖の場合は吸収確率と期待ステップ数を計算します——これらすべてが依存性なし、手書きで実装されています。

1. 最初の連鎖

markov キーワード（エイリアス markovchain）、オプションのタイトルで始め、その後に確率で重み付けされた遷移を記述します。状態は最初に言及されたアークから自動的に作成されます：

markov "Weather"
  Sunny -> Sunny : 0.9
  Sunny -> Rainy : 0.1
  Rainy -> Sunny : 0.5
  Rainy -> Rainy : 0.5

遷移は FROM -> TO : PROBABILITY です。自己ループ（Sunny -> Sunny）はその場に留まる確率です。すべての確率は [0, 1] の範囲でなければならず、各状態からの確率の合計は1でなければなりません。

2. 状態の宣言

状態を明示的に宣言してラベル、順序、または吸収状態としてマークすることができます：

markov "Gambler's ruin"
  state Broke "$0" absorbing
  state Rich  "$4" absorbing
  state S1
  state S2
  Broke -> Broke : 1
  Rich  -> Rich  : 1
  S1 -> Broke : 0.5
  S1 -> S2 : 0.5
  S2 -> S1 : 0.5
  S2 -> Rich : 0.5

state ID "label" absorbing — ラベルはオプション。absorbing は状態がシンク（確率1の自己ループ）であることを宣言します。エンジンはこの宣言を行列に対してクロスチェックします。

3. ディレクティブ

layout: layered       # レイアウトモード
normalize: true        # 各行を合計1にスケール（ハードエラーの代わりに）
analysis: classify, absorbing   # 計算する内容：classify | absorbing | stationary

• normalize: true は各行を合計1になるようにスケールします（A -> B : 1、A -> C : 1 のような正規化されていない重みに便利）。これなしで合計が1にならない行はハードエラーになります。
• analysis: は実行して表示する計算を選択します。

4. 計算による答え

これが差別化要因です。3つの手書き、依存性なしの線形代数パス：

1. 行列の組み立て + 検証 — Pを構築し、行の合計ポリシーを適用します（ハードエラー、または normalize 下でスケール）。
2. 状態分類 — Tarjan SCC → 連絡クラス；クラスが閉じている場合は再帰的、そうでない場合は過渡的；確率1の自己ループを持つ閉じたシングルトンは吸収的。
3. 定量的な答え：
   • 定常分布 π（πP = π、Σπ = 1）：周期連鎖には正確なガウス消去法のフォールバックを持つ冪乗法。
   • 吸収連鎖の場合：基本行列 N = (I−Q)⁻¹、吸収確率 B = N·R、吸収への期待ステップ数 t = N·1。

過渡状態、再帰クラス、吸収状態は別々にレンダリングされ、計算値は data-* に保持されます。

5. よくある間違い

# 間違い — [0,1] 範囲外の確率
A -> B : 1.5

# 間違い — 確率のない遷移
A -> B

# 間違い — 合計が1にならない行（`normalize: true` なし）
A -> B : 0.3
A -> C : 0.3

すべての遷移は [0, 1] の確率を必要とします。各状態の発出確率の合計は1でなければなりません。そうでなければ normalize: true を設定する必要があります。空の連鎖（遷移なし）は拒否されます。

6. 標準への準拠

このモデルは行確率的遷移行列を持つ離散時間、時間均一マルコフ連鎖です。分類（過渡的/再帰的/吸収的）、定常分布、吸収連鎖の基本行列分析は標準的な教科書（Kemeny & Snell, Finite Markov Chains）に従います。

7. ロードマップ

保留中：連続時間連鎖（レート行列）、隠れマルコフモデル、平均初回通過時間、周期性レポート。