Pythonでマルコフ連鎖の特定時刻における状態到達確率を求める方法

マルコフ連鎖のグラフ g が与えられているとします。時刻 t = 0 に状態 S から出発したとき、時刻 T に状態 F へ到達する確率を求めるのが目的です。

マルコフ連鎖とは、複数の「状態」と、ある状態から別の状態へ遷移する「確率」から構成される確率過程のことです。これは有向グラフとして表現でき、ノードが状態を、エッジがあるノードから別のノードへ移動する確率を表します。ある状態から別の状態への移動には単位時間がかかり、各ノードの出ていくエッジの確率の合計は必ず 1 になります。

問題の例

たとえば、N = 6（状態数）、S = 4（開始状態）、F = 2（目標状態）、T = 100（時刻）が入力として与えられた場合、出力は 0.28499144801478526 となります。

解法のアプローチ：動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。基本的な考え方は次のとおりです。

• table := サイズ (N+1) × (T+1) の二次元配列を作成し、すべて 0.0 で初期化する。table[j][i] は「時刻 i に状態 j にいる確率」を表す。
• 初期条件として table[S][0] := 1.0 を設定する（時刻 0 では開始状態 S にいる確率が 1）。
• i を 1 から T まで繰り返す：
  • j を 1 から N まで繰り返す：
    • G[j] に含まれる各要素 k（遷移先の状態とその確率）に対して、table[j][i] += k[1] * table[k[0]][i - 1] を実行する。
• 最後に table[F][T] を返す。これが求める確率となる。

Pythonでの実装例

以下のコードで実際の実装を確認できます。

def get_probability(G, N, F, S, T):
    # (N+1) x (T+1) のテーブルを 0.0 で初期化
    table = [[0.0 for j in range(T+1)] for i in range(N+1)]

    # 時刻 0 で開始状態 S にいる確率は 1
    table[S][0] = 1.0

    # 各時刻・各状態について確率を漸化的に計算
    for i in range(1, T+1):
        for j in range(1, N+1):
            for k in G[j]:
                table[j][i] += k[1] * table[k[0]][i - 1]

    return table[F][T]

# グラフの定義（隣接リスト形式：[(遷移先, 確率), ...]）
graph = []
graph.append([])
graph.append([(2, 0.09)])
graph.append([(1, 0.23),(6, 0.62)])
graph.append([(2, 0.06)])
graph.append([(1, 0.77),(3, 0.63)])
graph.append([(4, 0.65),(6, 0.38)])
graph.append([(2, 0.85),(3, 0.37), (4, 0.35), (5, 1.0)])

N = 6
S, F, T = 4, 2, 100
print(get_probability(graph, N, F, S, T))

入力

N = 6, S = 4, F = 2, T = 100

出力

0.28499144801478526

計算量について

このアルゴリズムの時間計算量は O(N × T × E) です。ここで E は各状態からの平均遷移数です。空間計算量は O(N × T) となり、テーブル全体を保持する必要があります。なお、直前の時刻の値のみを使用するため、空間を O(N) に削減することも可能です。