機械学習と情報技術

マルコフ連鎖の基本をわかりやすく解説

確率過程

マルコフ連鎖は確率過程の中で最も基本的かつ重要な概念です。「未来の状態は現在の状態のみに依存し、過去の履歴には依存しない」というマルコフ性を持つ確率過程であり、自然言語処理、金融工学、物理学、生物学など、極めて多くの分野で応用されています。

Google の PageRank アルゴリズム、MCMCによるベイズ推論、強化学習、HMM（隠れマルコフモデル）など、マルコフ連鎖は現代のデータサイエンスの基盤技術です。

本記事の内容

  • マルコフ性の定義
  • 遷移確率と遷移行列
  • 状態の分類
  • 定常分布の計算
  • Pythonでのシミュレーション

前提知識

この記事を読む前に、以下の概念を理解しておくと理解が深まります。

  • 条件付き確率
  • 行列の基本演算

マルコフ性

定義

確率変数の列 $\{X_n\}_{n=0,1,2,\dots}$ がマルコフ性を持つとは、

$$ P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i) $$

が任意の $n$ と任意の状態 $i_0, \dots, i_{n-1}, i, j$ に対して成り立つことです。

直感的な理解

マルコフ性は「過去の履歴は現在の状態に集約されている」ことを意味します。言い換えると、未来を予測するために必要な情報は、現在の状態だけで十分であり、どのようにしてその状態に到達したかは関係ありません。

天気のモデルで例えると、「明日の天気は今日の天気だけで決まり、昨日や一昨日の天気は関係ない」ということです。

遷移確率と遷移行列

遷移確率

状態 $i$ から状態 $j$ への1ステップの遷移確率は、

$$ p_{ij} = P(X_{n+1} = j \mid X_n = i) $$

時刻 $n$ に依存しない場合、時間的同次（time-homogeneous）であるといいます。以下では時間的同次を仮定します。

遷移行列

遷移確率を行列にまとめたものが遷移行列 $\bm{P}$ です。

$$ \bm{P} = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1N} \\ p_{21} & p_{22} & \cdots & p_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ p_{N1} & p_{N2} & \cdots & p_{NN} \end{pmatrix} $$

遷移行列の性質:

  • $p_{ij} \geq 0$ （すべての要素が非負）
  • $\sum_{j} p_{ij} = 1$ （各行の和が1）

このような行列を確率行列（stochastic matrix）と呼びます。

$n$ ステップ遷移確率

$n$ ステップ後の遷移確率は、

$$ p_{ij}^{(n)} = P(X_{m+n} = j \mid X_m = i) $$

で与えられ、行列で書くと $\bm{P}^{(n)} = \bm{P}^n$（遷移行列の $n$ 乗）です。

具体例: 天気モデル

天気を「晴れ（S）」と「雨（R）」の2状態でモデル化します。

$$ \bm{P} = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix} $$

  • 晴れの翌日が晴れる確率: 0.8
  • 晴れの翌日が雨になる確率: 0.2
  • 雨の翌日が晴れる確率: 0.4
  • 雨の翌日も雨が続く確率: 0.6

2日後の遷移確率:

$$ \bm{P}^2 = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}^2 = \begin{pmatrix} 0.72 & 0.28 \\ 0.56 & 0.44 \end{pmatrix} $$

今日晴れなら、2日後に晴れる確率は0.72です。

状態の分類

到達可能性

状態 $j$ が状態 $i$ から到達可能（accessible）であるとは、ある $n \geq 0$ が存在して $p_{ij}^{(n)} > 0$ となることです。$i \to j$ と書きます。

$i \to j$ かつ $j \to i$ のとき、$i$ と $j$ は連絡する（communicate）といい、$i \leftrightarrow j$ と書きます。

既約性

すべての状態対が連絡するとき、マルコフ連鎖は既約（irreducible）であるといいます。

周期性

状態 $i$ の周期 $d(i)$ は、$p_{ii}^{(n)} > 0$ となる $n$ の最大公約数です。$d(i) = 1$ のとき、状態 $i$ は非周期的（aperiodic）であるといいます。

エルゴード性

マルコフ連鎖が既約かつ非周期的であるとき、エルゴード的（ergodic）であるといいます。エルゴード的マルコフ連鎖は、初期状態に依存しない一意の定常分布に収束します。

定常分布

定義

確率ベクトル $\bm{\pi} = (\pi_1, \pi_2, \dots, \pi_N)$ が定常分布（stationary distribution）であるとは、

$$ \bm{\pi} \bm{P} = \bm{\pi} $$

かつ $\sum_i \pi_i = 1$, $\pi_i \geq 0$ を満たすことです。

定常分布の意味

定常分布に従う状態から出発すると、遷移後も同じ分布に従います。また、エルゴード的マルコフ連鎖では、十分長い時間が経つと、状態 $i$ にいる割合が $\pi_i$ に収束します。

定常分布の計算

天気モデルの場合、$\bm{\pi}\bm{P} = \bm{\pi}$ を解きます。

$$ \begin{cases} 0.8\pi_S + 0.4\pi_R = \pi_S \\ 0.2\pi_S + 0.6\pi_R = \pi_R \\ \pi_S + \pi_R = 1 \end{cases} $$

第1式より $0.4\pi_R = 0.2\pi_S$、つまり $\pi_S = 2\pi_R$ です。$\pi_S + \pi_R = 1$ と合わせて、

$$ \pi_S = \frac{2}{3}, \quad \pi_R = \frac{1}{3} $$

長期的には、晴れの日が2/3、雨の日が1/3の割合になります。

Pythonでのシミュレーション

マルコフ連鎖のシミュレーション

import numpy as np
import matplotlib.pyplot as plt

def simulate_markov_chain(P, initial_state, n_steps):
    """マルコフ連鎖をシミュレーション"""
    n_states = P.shape[0]
    states = [initial_state]
    current = initial_state
    for _ in range(n_steps):
        current = np.random.choice(n_states, p=P[current])
        states.append(current)
    return np.array(states)

# 天気モデル
P = np.array([[0.8, 0.2],
              [0.4, 0.6]])
state_names = ['Sunny', 'Rainy']

np.random.seed(42)
n_steps = 200
states = simulate_markov_chain(P, initial_state=0, n_steps=n_steps)

fig, axes = plt.subplots(2, 1, figsize=(12, 8))

# 状態の遷移
ax = axes[0]
ax.step(range(n_steps + 1), states, where='post', linewidth=1)
ax.set_yticks([0, 1])
ax.set_yticklabels(state_names)
ax.set_xlabel('Time step')
ax.set_title('Markov chain simulation (Weather model)')
ax.grid(True, alpha=0.3)

# 晴れの割合の収束
ax = axes[1]
sunny_ratio = np.cumsum(states == 0) / np.arange(1, n_steps + 2)
ax.plot(range(n_steps + 1), sunny_ratio, 'b-', linewidth=1.5)
ax.axhline(y=2/3, color='r', linestyle='--', linewidth=2, label='$\\pi_{\\mathrm{Sunny}} = 2/3$')
ax.set_xlabel('Time step')
ax.set_ylabel('Fraction of sunny days')
ax.set_title('Convergence to stationary distribution')
ax.legend()
ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.savefig('markov_chain_simulation.png', dpi=150, bbox_inches='tight')
plt.show()

遷移行列のべき乗と収束

import numpy as np
import matplotlib.pyplot as plt

P = np.array([[0.8, 0.2],
              [0.4, 0.6]])

# P^n の各成分の変化を可視化
n_max = 30
p_values = np.zeros((n_max, 2, 2))
P_n = np.eye(2)

for n in range(n_max):
    P_n = P_n @ P
    p_values[n] = P_n

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

# P^n の第1行（晴れからスタート）
ax = axes[0]
ax.plot(range(1, n_max + 1), p_values[:, 0, 0], 'b-o', markersize=3, label='$P^n_{SS}$')
ax.plot(range(1, n_max + 1), p_values[:, 0, 1], 'r-o', markersize=3, label='$P^n_{SR}$')
ax.axhline(y=2/3, color='blue', linestyle='--', alpha=0.5)
ax.axhline(y=1/3, color='red', linestyle='--', alpha=0.5)
ax.set_xlabel('$n$')
ax.set_ylabel('Probability')
ax.set_title('Starting from Sunny')
ax.legend()
ax.grid(True, alpha=0.3)

# P^n の第2行（雨からスタート）
ax = axes[1]
ax.plot(range(1, n_max + 1), p_values[:, 1, 0], 'b-o', markersize=3, label='$P^n_{RS}$')
ax.plot(range(1, n_max + 1), p_values[:, 1, 1], 'r-o', markersize=3, label='$P^n_{RR}$')
ax.axhline(y=2/3, color='blue', linestyle='--', alpha=0.5)
ax.axhline(y=1/3, color='red', linestyle='--', alpha=0.5)
ax.set_xlabel('$n$')
ax.set_ylabel('Probability')
ax.set_title('Starting from Rainy')
ax.legend()
ax.grid(True, alpha=0.3)

plt.suptitle('Convergence of $P^n$ to stationary distribution', fontsize=13)
plt.tight_layout()
plt.savefig('markov_convergence.png', dpi=150, bbox_inches='tight')
plt.show()

初期状態が「晴れ」でも「雨」でも、十分な時間が経つと同じ定常分布 $(\pi_S, \pi_R) = (2/3, 1/3)$ に収束することが確認できます。

定常分布の計算（固有値問題として）

import numpy as np

P = np.array([[0.8, 0.2],
              [0.4, 0.6]])

# 定常分布は P^T の固有値1に対応する固有ベクトル
eigenvalues, eigenvectors = np.linalg.eig(P.T)

# 固有値1に対応する固有ベクトルを取得
idx = np.argmin(np.abs(eigenvalues - 1.0))
stationary = np.real(eigenvectors[:, idx])
stationary = stationary / stationary.sum()  # 正規化

print(f"固有値: {eigenvalues}")
print(f"定常分布: {stationary}")
print(f"検証 π P = π: {stationary @ P}")

まとめ

本記事では、マルコフ連鎖の基本を解説しました。

  • マルコフ性: 未来は現在の状態のみに依存し、過去の履歴には依存しない
  • 遷移行列: 各行の和が1の確率行列で遷移確率を表す
  • $n$ ステップ遷移: $\bm{P}^n$ で計算できる
  • 定常分布: $\bm{\pi P} = \bm{\pi}$ を満たす確率分布
  • エルゴード性: 既約かつ非周期的なら、初期状態によらず定常分布に収束

マルコフ連鎖は、MCMC（マルコフ連鎖モンテカルロ法）やHMM（隠れマルコフモデル）の基盤です。次のステップとして、ポアソン過程について学びましょう。

関連記事

前の記事

【大規模モデル】Tensor/Pipeline並列化の理論と実装

次の記事

Flash Attentionの仕組み — IO-Aware なアテンション高速化

関連タグ: マルコフ連鎖 定常分布 確率論 確率過程 遷移行列