線形代数 · 第23回 · 動画2 · インタラクティブ教材

マルコフ連鎖はなぜ出発点を忘れるのか：λ = 1 のアトラクター

I重要な公式

公式	名称	説明
$u_{k+1} = A\, u_k$	マルコフ連鎖の反復	連鎖の時間を1ステップ進める
$u_k = c_1 \lambda_1^k x_1 + c_2 \lambda_2^k x_2 + \cdots + c_n \lambda_n^k x_n$	スペクトルによる基本公式	固有ベクトルの基底で見た $A$ のべき乗
$\lambda_1 = 1,\ \ \lvert\lambda_i\rvert < 1$ （ $i \ge 2$ ）	マルコフ行列のスペクトル	列確率行列 $A$ では常に成り立つ
$u_k \to c_1 x_1$ （ $k \to \infty$ ）	定常状態	$\lambda=1$ の方向だけが生き残る

II可視化1 — 最初の配分を忘れる

各ステップで都市 A の割合 $p$ 、都市 B の割合 $q$ が出ていきます。連鎖を進めると、配分は一つの値に落ち着きます。

p (A→B) 0.20 q (B→A) 0.30 A の初期割合 0.90 ステップ k 30

💡 $A = \begin{bmatrix} 1-p & q \\ p & 1-q \end{bmatrix}$ の定常状態は $\tfrac{1}{p+q}(q,\,p)$ です。決めるのは移動の割合だけで、出発点はまったく関係しません。

III可視化2 — 連鎖が忘れる速さ

支配的でない項はどれも $|\lambda_2|^k$ のように減衰します。 $|\lambda_2|$ が 1 に近いほど、連鎖が忘れるのは遅くなります。

|λ₂| 0.70

💡 1% まで縮むのに必要なステップ数が、その連鎖の混合時間です。それを決める比 $|\lambda_2|$ を混合率といいます。

IV可視化3 — すべての道は一つの定常状態へ

直線 $a+b=1$ 上の6通りの最初の配分から出発しても、どの軌跡も同じ定常状態の点へ滑り込んでいきます。

p (A→B) 0.40 q (B→A) 0.20 ステップ k 25

V確認クイズ

問1

どんな列確率のマルコフ行列 $A$ についても、最大の固有値 $\lambda_1$ はいくつですか。

✅ 正解です！ どんな列確率行列も $\lambda_1 = 1$ をもちます。列の和が 1 であることがそれを保証します。

❌ 惜しい！ 列の和が 1 という性質から、ある特定の固有値が必ず現れます。 $\mathbf{1}^T A$ が何に等しいかを考えましょう。

解答を見る

解答：

列確率行列は、どの列も和が 1 です。したがって、全成分が 1 の行ベクトル $\mathbf{1}^T$ は $\mathbf{1}^T A = \mathbf{1}^T$ を満たし、 $\mathbf{1}^T$ は固有値 $1$ の左固有ベクトルです。 $A$ と $A^T$ は同じ固有値をもつので、 $\lambda = 1$ は $A$ の固有値でもあります。

確率行列のすべての固有値について成り立つペロン–フロベニウスの評価 $|\lambda_i| \le 1$ と合わせると、次の結論が得られます。

$\lambda_1 = 1 \text{（常に、ぴったり）}$

問2

あるマルコフ連鎖の固有値は $\lambda_1 = 1$ 、 $\lambda_2 = 0.95$ 、 $\lambda_3 = 0.2$ です。支配的でない成分がおよそ 100 分の 1 に減衰するには、およそ何ステップ $k$ が必要ですか（つまり $|\lambda_2|^k \approx 0.01$ となるのはいつですか）。

✅ 正解です！ $\ln(0.01)/\ln(0.95) \approx 90$ です。混合時間を決めるのは、最もゆっくり減衰する固有値 $\lambda_2 = 0.95$ です。

❌ 惜しい！ 収束を支配するのは2番目に大きい固有値です。 $0.95^k \approx 0.01$ を解きましょう。

解答を見る

解答：

収束の速さを決めるのは、2番目に大きい固有値の大きさ $|\lambda_2| = 0.95$ です。次の式を満たすステップ数を求めます。

$0.95^k \approx 0.01$

対数をとると $k \approx \dfrac{\ln(0.01)}{\ln(0.95)} = \dfrac{-4.605}{-0.0513} \approx 89.8$ です。

したがって約 90 ステップです。 $\lambda_3 = 0.2$ ははるかに速く減衰する（ $0.2^{90}$ は天文学的に小さい）ので、関係ありません。混合時間を支配するのは、支配的でない固有値のうち最も減衰の遅いものです。

問3

正しいか誤りか：（性質のよい）マルコフ連鎖では、定常状態 $u_\infty$ は最初の分布 $u_0$ によって決まる。

✅ 正解です！ 定常状態 $c_1 x_1$ は行列の $\lambda=1$ に対応する固有ベクトルで決まり、確率の条件によって $c_1$ も決まります。 $u_0$ にはよりません。

❌ 惜しい！ 可視化3を振り返りましょう。6通りの最初の配分は、どれも同じ赤い星印へ流れ込みました。

解答を見る

解答：

基本公式から $u_k = c_1 \cdot 1^k \cdot x_1 + c_2 \lambda_2^k x_2 + \cdots$ です。 $k \to \infty$ とすると最初の項だけが生き残るので、次のようになります。

$u_\infty = c_1 x_1.$

向き $x_1$ は行列 $A$ で決まり、 $u_0$ にはまったくよりません。スカラー $c_1$ は原理的には $u_0$ によりますが、確率ベクトル $u_0$ （成分が 0 以上で和が 1）であれば、 $u_\infty$ の和も 1 という条件によって $c_1$ がただ一つに決まります。

結論：確率ベクトルである最初の分布は、どれも同じ定常状態に収束します。連鎖は自分の出発点を忘れるのです。

（注意：ここでは $\lambda = 1$ の重複度が 1 で、連鎖が既約かつ非周期的である、つまり性質のよい場合を仮定しています。）

問4

次の列確率行列を考えます。 $A = \begin{bmatrix} 0.7 & 0.4 \\ 0.3 & 0.6 \end{bmatrix}.$

定常分布（ $\lambda = 1$ に対応する固有ベクトルを、成分の和が 1 になるように正規化したもの）はどれですか。

✅ 正解です！ $(A-I)x = 0$ を解いて正規化すると $(4/7, 3/7)$ になります。

❌ 惜しい！ $(0.5, 0.5)$ が定常状態になるのは、行列が対称な場合（たとえば $p = q$ ）だけです。ここでは $p \ne q$ です。

❌ 惜しい！ 対角成分を読み取ることは、 $Ax = x$ を解くことと同じではありません。固有値の方程式を立てましょう。

❌ 惜しい！ 成分を入れ替えてしまったのかもしれません。 $(A-I)x = 0$ を丁寧に解きましょう。

解答を見る

解答：

$A x = x$ 、つまり $(A - I)x = 0$ を解きます。

$A - I = \begin{bmatrix} -0.3 & 0.4 \\ 0.3 & -0.4 \end{bmatrix}.$

1行目から $-0.3 x_1 + 0.4 x_2 = 0$ なので $x_2 = \tfrac{3}{4} x_1$ 、すなわち $(x_1, x_2) \propto (4, 3)$ です。

成分の和が 1 になるように正規化します。

$x_1 = \left(\frac{4}{7},\ \frac{3}{7}\right) \approx (0.571,\ 0.429).$

2×2 の列確率行列の近道 $\begin{bmatrix} 1-p & q \\ p & 1-q \end{bmatrix}$ ：定常状態は $\dfrac{1}{p+q}(q, p)$ です。ここでは $p = 0.3$ 、 $q = 0.4$ なので、 $(0.4, 0.3)/0.7 = (4/7, 3/7)$ となります。

正解数：0 / 4