定義隨機過程，並判斷一個過程是否具馬可夫性質。
由文字敘述建立轉移矩陣，用 \(\bm{\pi}_{t+1} = \bm{\pi}_t \bm{P}\) 演化分布，以矩陣冪 \(\bm{P}^n\) 算 \(n\) 步轉移。
求解穩態分布 \(\bm{\pi}\bm{P} = \bm{\pi}\)，敘述不可約、非週期與收斂定理，解釋 PageRank 為何是穩態分布。
用蒙地卡羅方法估計期望值，說明 \(1/\sqrt{N}\) 誤差律與「收斂速度與維度無關」的意義。
解釋 Metropolis–Hastings 與 Gibbs 抽樣，以細緻平衡論證其正確性，理解 burn-in（暖身期）與樣本相關性，並以 Python 實作驗證。
之前各章的主角是「一個」隨機變數，或一組彼此獨立的樣本。可是許多最有趣的隨機現象是隨時間持續演化的，而且「現在」與「過去」糾纏在一起：今天下雨，明天放晴的機會有多大？這類問題的共同數學骨架，就是隨機過程。
隨機過程（stochastic process）是一族以時間為索引、定義在同一機率空間上的隨機變數 \(\{X_t\}_{t \in T}\)。索引集合 \(T\) 代表時間：\(T = \{0, 1, 2, \dots\}\) 稱為離散時間，\(T = [0, \infty)\) 稱為連續時間。\(X_t\) 的所有可能取值構成狀態空間（state space）\(S\)，同樣分為離散與連續兩類。本章聚焦在離散時間、離散狀態空間的過程——已足以支撐從 PageRank 到擴散模型的大量應用。
日常與工程中的隨機過程俯拾皆是：隨機漫步（random walk，每步上下移動、位置隨時間累積）、每日股價、句子中的字詞序列（「時間」是詞的位置、狀態空間是詞彙表——語言模型的原點）、棋局的遊戲狀態、櫃檯前的排隊人數。
最簡單的例子是簡單對稱隨機漫步：\(\iid\) 步伐 \(\Prob(\xi_k = \pm 1) = \tfrac12\)，位置 \(X_t = \xi_1 + \cdots + \xi_t\)（\(\E[X_t] = 0\)、\(\Var(X_t) = t\)：平均哪裡都不去，典型距離卻以 \(\sqrt{t}\) 成長）。它展示了本章的新現象——相依性：\(X_{t+1} = X_t + \xi_{t+1}\) 與 \(X_t\) 高度相關，聯合分布不再拆成邊際的乘積；一次「實驗」的結果也不再是一個數字，而是一整條樣本路徑（sample path）。相依結構毫無限制則分析寸步難行——我們需要一個「夠簡單又夠有用」的相依性假設。注意：給定 \(X_t\) 之後，\(X_{t+1}\) 的分布便與更早的歷史無關——這個觀察正是下一節的主角。
馬可夫鏈：只記得現在的隨機過程
一般的隨機過程中，\(X_{t+1}\) 可以依賴整段歷史 \(X_0, X_1, \dots, X_t\)，需要指定的條件機率數量隨時間爆炸。馬可夫鏈做了一個大膽的簡化：未來只透過現在依賴過去。
隨機過程 \(\{X_t\}\) 具馬可夫性質（Markov property），若對所有 \(t\) 與所有狀態， \[\Prob(X_{t+1} = j \mid X_t = i,\ X_{t-1} = i_{t-1},\ \dots,\ X_0 = i_0) = \Prob(X_{t+1} = j \mid X_t = i):\] 一旦知道現在的狀態，完整歷史對預測未來不再提供額外資訊——無記憶（memoryless）。若此條件機率不隨 \(t\) 改變（時間齊次），過程稱為馬可夫鏈（Markov chain）。有限狀態空間 \(S = \{1, \dots, m\}\) 上的鏈由轉移矩陣（transition matrix）\(\bm{P}\) 完全指定： \[P_{ij} = \Prob(X_{t+1} = j \mid X_t = i), \qquad P_{ij} \ge 0, \qquad \sum_{j=1}^{m} P_{ij} = 1 \ \ (\text{每一列的和為 } 1),\] 即第 \(i\) 列是「從狀態 \(i\) 出發，下一步去哪」的完整分布；這樣的非負矩陣稱為隨機矩陣（stochastic matrix）。
隨機漫步就是馬可夫鏈：給定 \(X_t = i\)，下一步的分布（\(i \pm 1\) 各半）與更早的歷史無關——只是狀態空間是無限的 \(\mathbb{Z}\)。有限狀態的鏈更方便：整個動力學塞得進一個矩陣。把時刻 \(t\) 的狀態分布寫成列向量 \(\bm{\pi}_t = [\Prob(X_t = 1), \dots, \Prob(X_t = m)]\)，由全機率定理（第 2 章）， \[(\bm{\pi}_{t+1})_j = \sum_{i} \Prob(X_t = i)\, P_{ij} \quad\Longleftrightarrow\quad \boxed{\ \bm{\pi}_{t+1} = \bm{\pi}_t \bm{P}\ } \qquad\text{因此}\qquad \bm{\pi}_t = \bm{\pi}_0 \bm{P}^t.\]
「無記憶」不是說過去無關緊要——過去當然影響現在。它說的是：現在的狀態已經總結了所有與未來相關的歷史。你下一步去哪，只取決於你現在站在哪裡，不取決於你是怎麼走到這裡的。這是一個建模假設（通常只是近似），而它換來的報酬極為豐厚：整個系統的動力學被壓縮進一個矩陣 \(\bm{P}\)，「讓時間前進一步」變成「把分布向量乘上 \(\bm{P}\) 一次」。機率問題就此變成線性代數問題。
某城市的天氣簡化為兩種狀態：晴（狀態 1）與雨（狀態 2）。長期觀測顯示：晴天之後 \(70\%\) 仍是晴天、\(30\%\) 轉雨；雨天之後 \(50\%\) 轉晴、\(50\%\) 仍下雨。寫出轉移矩陣，並回答：(a) 今天確定是晴天，明天的天氣分布？(b) 今天晴雨機會各半，明天呢？
依「列＝現在狀態、行＝下一狀態」的約定， \[\bm{P} = \begin{pmatrix} 0.7 & 0.3\\ 0.5 & 0.5 \end{pmatrix},\] 兩列的和分別為 \(0.7 + 0.3 = 1\) 與 \(0.5 + 0.5 = 1\)，確為合法的隨機矩陣。
(a) 今天確定晴天：\(\bm{\pi}_0 = [1, 0]\)，故 \(\bm{\pi}_1 = \bm{\pi}_0\bm{P} = [0.7,\ 0.3]\)——直接讀出 \(\bm{P}\) 的第 1 列。
(b) \(\bm{\pi}_0 = [0.5, 0.5]\) 時， \[\bm{\pi}_1 = [0.5 \times 0.7 + 0.5 \times 0.5,\ \ 0.5 \times 0.3 + 0.5 \times 0.5] = [0.60,\ 0.40].\] 「乘上 \(\bm{P}\)」就是全機率定理的矩陣寫法：對每個目的地，加總「出發地機率 \(\times\) 轉移機率」。
走一步是乘一次 \(\bm{P}\)，走 \(n\) 步呢？答案優雅得令人愉快：乘 \(n\) 次，也就是矩陣冪。
記 \(n\) 步轉移機率 \(P^{(n)}_{ij} = \Prob(X_{t+n} = j \mid X_t = i)\)。則 \[P^{(n)}_{ij} = (\bm{P}^n)_{ij}, \qquad\text{且對任意 } m, n \ge 1:\quad (\bm{P}^{m+n})_{ij} = \sum_{k} (\bm{P}^m)_{ik} (\bm{P}^n)_{kj}.\] 後者稱為 Chapman–Kolmogorov 方程：走 \(m+n\) 步從 \(i\) 到 \(j\)，等於「先走 \(m\) 步到某個中繼狀態 \(k\)、再走 \(n\) 步到 \(j\)」對所有 \(k\) 加總。
證明對中繼時刻的狀態使用全機率定理，再用馬可夫性質丟掉多餘的條件： \[\Prob(X_{m+n} = j \mid X_0 = i) = \sum_k \Prob(X_m = k \mid X_0 = i)\, \Prob(X_{m+n} = j \mid X_m = k),\] 右式正是矩陣乘法 \(\bm{P}^{(m)}\bm{P}^{(n)}\) 的 \((i,j)\) 元素。取 \(m = n-1\)、\(n = 1\) 依序歸納，即得 \(P^{(n)}_{ij} = (\bm{P}^n)_{ij}\)。\(\blacksquare\)
沿用天氣鏈，計算 \(\bm{P}^2\)，並解讀「今天晴、後天雨」的機率。
逐元素計算 \(\bm{P}^2 = \bm{P}\bm{P}\)： \[\bm{P}^2 = \begin{pmatrix} 0.7 \times 0.7 + 0.3 \times 0.5 & 0.7 \times 0.3 + 0.3 \times 0.5\\[2pt] 0.5 \times 0.7 + 0.5 \times 0.5 & 0.5 \times 0.3 + 0.5 \times 0.5 \end{pmatrix} = \begin{pmatrix} 0.64 & 0.36\\ 0.60 & 0.40 \end{pmatrix},\] 每列和仍為 \(1\)——隨機矩陣的乘積仍是隨機矩陣。「今天晴、後天雨」\(= (\bm{P}^2)_{12} = 0.36\)，路徑驗證：晴\(\to\)晴\(\to\)雨貢獻 \(0.7 \times 0.3 = 0.21\)，晴\(\to\)雨\(\to\)雨貢獻 \(0.3 \times 0.5 = 0.15\)，合計 \(0.36\)。\(\checkmark\) 矩陣乘法自動列舉並加總所有中繼路徑——這正是 Chapman–Kolmogorov 方程在做的事。
馬可夫性是假設，不是事實。真實過程很少嚴格無記憶：語言有長程依賴、股價有動量、天氣有季節。用馬可夫鏈建模是選擇忽略較長的記憶以換取可解性；補救之道是擴充狀態——把「最近 \(k\) 期」整包當成一個狀態，\(k\) 階記憶就化為一階馬可夫（練習 11.3）。另一個技術性陷阱：本書約定分布為列向量、右乘 \(\bm{P}\)，有些書用行向量左乘 \(\bm{P}^{\mathsf T}\)——讀文獻先確認「列和為 1 還是行和為 1」。
穩態分布與收斂
把分布一步步往前推：\(\bm{\pi}_0,\ \bm{\pi}_0\bm{P},\ \bm{\pi}_0\bm{P}^2, \dots\) 這串向量最終會走向哪裡？對「行為良好」的鏈，答案出奇地乾淨：不論起點為何，分布都收斂到同一個極限。這個極限就是穩態分布。
狀態上的機率分布 \(\bm{\pi}\)（列向量，\(\pi_i \ge 0\)、\(\sum_i \pi_i = 1\)）若滿足 \[\bm{\pi} \bm{P} = \bm{\pi},\] 則稱為穩態分布（stationary distribution，也稱不變分布）。它是轉移的不動點：分布一旦是 \(\bm{\pi}\)，經過任意多步轉移仍是 \(\bm{\pi}\)。線性代數的觀點：\(\bm{\pi}\) 是 \(\bm{P}\) 對應特徵值 \(1\) 的左特徵向量（即 \(\bm{P}^{\mathsf T}\) 的特徵向量）正規化成總和為 \(1\)；特徵值 \(1\) 必定存在，因為每列和為 \(1\) 使全 \(1\) 向量成為右特徵向量。
「處於穩態」不代表鏈停止移動：個別軌跡照樣跳動，是分布不再改變——每個狀態流出的機率恰被流入補回。
求天氣鏈 \(\bm{P} = \begin{pmatrix} 0.7 & 0.3\\ 0.5 & 0.5 \end{pmatrix}\) 的穩態分布。
設 \(\bm{\pi} = [\pi_1, \pi_2]\)。條件 \(\bm{\pi}\bm{P} = \bm{\pi}\) 展開成 \(0.7\pi_1 + 0.5\pi_2 = \pi_1\) 與 \(0.3\pi_1 + 0.5\pi_2 = \pi_2\)——兩條都化簡為同一條 \(0.3\,\pi_1 = 0.5\,\pi_2\)（機率守恆使方程組必然降一階），必須補上正規化條件 \(\pi_1 + \pi_2 = 1\)。由 \(\pi_1 = \tfrac{5}{3}\pi_2\) 代入： \[\tfrac{5}{3}\pi_2 + \pi_2 = 1 \quad\Longrightarrow\quad \pi_2 = \tfrac{3}{8}, \qquad \pi_1 = \tfrac{5}{8}.\] 所以 \(\bm{\pi} = \bigl[\tfrac58, \tfrac38\bigr] = [0.625,\ 0.375]\)：長期而言，這座城市 \(62.5\%\) 的日子是晴天。驗算：\([0.625, 0.375]\,\bm{P} = [0.4375 + 0.1875,\ 0.1875 + 0.1875] = [0.625, 0.375]\)。\(\checkmark\)
穩態分布回答「長期比例」，但還有一個更深的問題：從任意起點出發，分布真的會收斂到 \(\bm{\pi}\) 嗎？先看數值證據。
分別從「確定晴天」\(\bm{\pi}_0 = [1, 0]\) 與「確定雨天」\(\bm{\pi}_0 = [0, 1]\) 出發，反覆右乘 \(\bm{P}\)。
反覆右乘 \(\bm{P}\)（如 \([1,0]\,\bm{P} = [0.7, 0.3]\)，\([0.7, 0.3]\,\bm{P} = [0.64, 0.36]\)，……），兩個起點的演化如下：
| 起點 \(\bm{\pi}_0 = [1, 0]\)（確定晴） | 起點 \(\bm{\pi}_0 = [0, 1]\)（確定雨） | |||
|---|---|---|---|---|
| 2-3(lr)4-5 \(t\) | \(\Prob(\text{晴})\) | \(\Prob(\text{雨})\) | \(\Prob(\text{晴})\) | \(\Prob(\text{雨})\) |
| 0 | 1.00000 | 0.00000 | 0.00000 | 1.00000 |
| 1 | 0.70000 | 0.30000 | 0.50000 | 0.50000 |
| 2 | 0.64000 | 0.36000 | 0.60000 | 0.40000 |
| 3 | 0.62800 | 0.37200 | 0.62000 | 0.38000 |
| 5 | 0.62512 | 0.37488 | 0.62480 | 0.37520 |
| 10 | 0.62500 | 0.37500 | 0.62500 | 0.37500 |
不論從哪裡出發，\(t = 10\) 時分布與 \([0.625, 0.375]\) 已相差不到 \(10^{-6}\)——鏈徹底忘記了初始條件。而且差距每步縮小為 \(0.2\) 倍（晴的機率誤差：\(0.075 \to 0.015 \to 0.003 \to \cdots\)）；這個 \(0.2\) 正是 \(\bm{P}\) 的第二特徵值，收斂以 \(|\lambda_2|^t\) 的幾何速度進行（練習 11.4）。
收斂並非理所當然——它需要鏈「行為良好」。良好與否由兩個結構性質決定。
不可約（irreducible）：任兩狀態 \(i, j\) 都存在某個 \(n\) 使 \((\bm{P}^n)_{ij} > 0\)——從任何狀態出發，終能以正機率到達任何其他狀態；鏈不會被困在某個角落。
週期（period）：狀態 \(i\) 的週期為 \(d(i) = \gcd\{n \ge 1 : (\bm{P}^n)_{ii} > 0\}\)，即所有「可能返回時刻」的最大公因數。若所有狀態的週期都是 \(1\)，鏈稱為非週期（aperiodic）。實用判準：只要某狀態有自環（\(P_{ii} > 0\)）且鏈不可約，整條鏈就非週期（不可約鏈的所有狀態必同週期）。
有限狀態馬可夫鏈若不可約且非週期，則：
穩態分布 \(\bm{\pi}\) 存在、唯一，且每個分量 \(\pi_j > 0\)；
對任意初始分布 \(\bm{\pi}_0\)，都有 \(\bm{\pi}_0 \bm{P}^t \to \bm{\pi}\)（\(t \to \infty\)）；等價地，\(\bm{P}^t\) 的每一列都收斂到 \(\bm{\pi}\)；
（遍歷性）沿單一軌跡統計的長期停留頻率也收斂：\(\frac{1}{T}\sum_{t=1}^{T} \mathbf{1}\{X_t = j\} \to \pi_j\)（機率 1 成立）。「時間平均 = 空間平均」：看一條夠長的路徑，等於看整個分布。
證明超出本書範圍（標準工具是耦合論證或 Perron–Frobenius 定理），但直觀不難：不可約保證鏈走得遍全空間，非週期排除固定節拍的振盪，初始差異便被隨機性逐步抹平。
「忘記起點」是可以拿來用的魔法。行為良好的鏈跑久了，\(X_t\) 的分布就是 \(\bm{\pi}\)，與起點無關。這件事有兩個改變世界的用法：PageRank 從「隨機網頁漫遊者」鏈讀出穩態分布，作為網頁的重要性分數；MCMC（第 5 節）反向操作——先指定你想要的目標分布，再設計一條以它為穩態的鏈，跑得夠久，鏈的狀態就是目標分布的樣本。一個是「從鏈讀出分布」，一個是「為分布造一條鏈」，用的是同一條定理。
穩態存在 \(\ne\) 分布收斂。週期鏈 \(\bm{P} = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}\) 有唯一穩態 \([\tfrac12, \tfrac12]\)，分布卻永遠在 \([1,0]\) 與 \([0,1]\) 間振盪；可約鏈則會讓極限依賴起點（練習 11.6）。使用「跑久了就是 \(\bm{\pi}\)」之前，先檢查不可約與非週期——在 MCMC 的語境下，這是演算法設計者要負責保證的事。
PageRank：兆元等級的穩態分布
Google 早期的核心演算法 PageRank 把網際網路看成馬可夫鏈：狀態是網頁，「隨機漫遊者」在目前網頁的對外連結中等機率挑一條點下去。穩態分布 \(\pi_j\) 是長期停留在網頁 \(j\) 的時間比例——即重要性分數：重要的頁被造訪得頻繁、每一票更有分量。這個遞迴定義，數學上恰是 \(\bm{\pi}\bm{P} = \bm{\pi}\)。
一個只有三頁的網路：頁 A 連向 B 與 C；頁 B 連向 C；頁 C 連向 A。漫遊者在對外連結中等機率選擇。求穩態分布，並解讀排名。
狀態順序 \((A, B, C)\)。A 有兩條對外連結（各 \(\tfrac12\)），B、C 各只有一條（機率 \(1\)）： \[\bm{P} = \begin{pmatrix} 0 & \tfrac12 & \tfrac12\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}.\] 解 \(\bm{\pi}\bm{P} = \bm{\pi}\)（逐行寫出「流入 = 存量」）：\(\pi_A = \pi_C\)、\(\pi_B = \tfrac12\pi_A\)、\(\pi_C = \tfrac12\pi_A + \pi_B\)，第三條由前兩條自動滿足。補上正規化 \(\pi_A + \pi_B + \pi_C = 1\)： \[\pi_A + \tfrac12\pi_A + \pi_A = \tfrac52 \pi_A = 1 \quad\Longrightarrow\quad \bm{\pi} = \Bigl[\tfrac25,\ \tfrac15,\ \tfrac25\Bigr] = [0.4,\ 0.2,\ 0.4].\] 收斂前提成立：\(A \to B \to C \to A\) 使鏈不可約；返回 \(A\) 可走 2 步（\(A \to C \to A\)）或 3 步，\(\gcd(2,3) = 1\)，非週期。解讀：C 有兩條入鏈，分數 \(0.4\) 不意外；有趣的是 A 只有一條入鏈卻並列第一——那條入鏈來自重要的 C，且 C 把全部的票都投給了 A。PageRank 衡量的不是入鏈數量，而是加權後的重要性流。實務上還會混入阻尼（damping）：漫遊者以機率 \(1 - d \approx 0.15\) 隨機傳送到任意頁，確保不可約且非週期（練習 11.8）。
蒙地卡羅方法
暫時把鏈放下，先解決另一個問題：怎麼計算期望值？貝氏推論、統計物理、財務工程裡的期望值往往是高維積分，沒有閉式解。蒙地卡羅方法的答案樸素而深刻：抽樣，然後取平均。
要估計 \(\mu = \E[g(X)]\)（\(X \sim p\)），蒙地卡羅方法（Monte Carlo method）抽取 \(X_1, \dots, X_N \iid p\)，以樣本平均 \[\hat{\mu}_N = \frac{1}{N} \sum_{i=1}^{N} g(X_i)\] 作為估計。大數法則（第 6 章）保證 \(\hat{\mu}_N \to \mu\)；估計不偏，標準誤為 \(\se(\hat{\mu}_N) = \sigma_g/\sqrt{N}\)（\(\sigma_g^2 = \Var(g(X))\)），中央極限定理再給出近似信賴區間 \(\hat{\mu}_N \pm 1.96\, \hat{\sigma}_g / \sqrt{N}\)。
任何機率都是期望值（\(\Prob(A) = \E[\mathbf{1}_A]\)），任何積分都能寫成期望值（\(\int_0^1 g(x)\dd x = \E[g(U)]\)，\(U\) 為均勻分布），所以「抽樣＋平均」是一把通用鑰匙。
蒙地卡羅的誤差律 \(\se = \sigma/\sqrt{N}\) 完全不依賴問題的維度。把 \([0,1]^{20}\) 上的積分交給格點法，每維取 10 點就要 \(10^{20}\) 次函數求值；蒙地卡羅照樣抽一百萬個點，誤差照樣以 \(1/\sqrt{10^6}\) 的尺度縮小。代價是慢：多一位小數要 \(100\) 倍樣本。「慢，但對維度免疫」——它成為高維機率計算主力的原因（練習 11.11）。
在單位正方形 \([0,1]^2\) 內均勻撒 \(N\) 個點。四分之一圓盤 \(\{x^2 + y^2 \le 1\}\) 的面積是 \(\pi/4\)，故每個點落入的機率為 \(p = \pi/4\)。以 \(\hat{\pi} = 4 \times (\text{落入圓內的點數})/N\) 估計 \(\pi\)。這個估計有多準？
落點指示變數是 Bernoulli(\(p\))，\(p = \pi/4 \approx 0.7854\)，變異數 \(p(1-p) \approx 0.1686\)，故 \(\se(\hat{\pi}) = 4\sqrt{p(1-p)/N} \approx 1.64/\sqrt{N}\)：\(N = 10^4\) 時約 \(0.016\)、\(N = 10^6\) 時約 \(0.0016\)。想多抓一位小數，\(N\) 得乘 \(100\)——\(1/\sqrt{N}\) 誤差律的日常長相。第 7 節會實際跑出 \(\hat{\pi} \approx 3.14\)。
但這有個致命前提：蒙地卡羅需要能從 \(p\) 抽樣。均勻、常態當然沒問題，可是貝氏推論交出的後驗分布（第 9 章）長這樣： \[p(\theta \mid \text{資料}) = \frac{\text{概似} \times \text{先驗}}{Z}, \qquad Z = \int \text{概似} \times \text{先驗} \dd\theta,\] 分子逐點可算，分母 \(Z\)（證據，evidence）卻是常常算不動的高維積分——我們只知道分布「到比例常數為止」。沒有 \(Z\)，連密度都寫不全，遑論抽樣。怎麼辦？讓馬可夫鏈登場。
馬可夫鏈蒙地卡羅（MCMC）
馬可夫鏈蒙地卡羅（Markov chain Monte Carlo, MCMC）不直接從目標分布 \(p\) 抽獨立樣本，而是建構一條穩態分布恰為 \(p\) 的馬可夫鏈，模擬它的軌跡 \(X_0, X_1, X_2, \dots\)，把軌跡上的狀態當作 \(p\) 的（相關的）樣本。收斂定理的第 3 款（遍歷性）保證：只要鏈行為良好，\(\frac{1}{T}\sum_{t=1}^{T} g(X_t) \to \E_p[g]\)——時間平均照樣能當期望值用，即使樣本彼此相關、即使我們從不知道 \(Z\)。
問題化約為：給定目標 \(p\)，怎麼設計一條以 \(p\) 為穩態的鏈？直接解 \(\bm{\pi}\bm{P} = \bm{\pi}\) 是全域條件，難以下手；實務上用一個更強、但逐對可驗證的局部條件。
分布 \(\bm{\pi}\) 與轉移矩陣 \(\bm{P}\) 滿足細緻平衡（detailed balance），若對每一對狀態 \(i, j\)： \[\pi_i P_{ij} = \pi_j P_{ji}.\] 左邊是穩態下每步「從 \(i\) 流向 \(j\)」的機率流量，右邊是反向流量：細緻平衡要求每一對狀態之間的雙向流量各自打平。滿足細緻平衡的鏈稱為可逆（reversible）——影片正著放、倒著放，統計性質相同。
若 \(\bm{\pi}\) 是機率分布且與 \(\bm{P}\) 滿足細緻平衡，則 \(\bm{\pi}\bm{P} = \bm{\pi}\)，即 \(\bm{\pi}\) 是穩態分布。
證明對任意狀態 \(j\)： \[(\bm{\pi}\bm{P})_j = \sum_i \pi_i P_{ij} = \sum_i \pi_j P_{ji} = \pi_j \sum_i P_{ji} = \pi_j \times 1 = \pi_j,\] 第二個等號逐項使用細緻平衡，最後用了「每列和為 1」。\(\blacksquare\)
細緻平衡是充分而非必要條件：穩態只要求每個狀態的總流入等於總流出（全域平衡），細緻平衡額外要求逐對打平。「總量平衡但逐對單向循環」的鏈確實存在——練習 11.7 會用一條循環鏈完整驗證。
驗證天氣鏈與其穩態 \(\bm{\pi} = [\tfrac58, \tfrac38]\) 滿足細緻平衡。
兩狀態只需檢查一對：\(\pi_1 P_{12} = \tfrac58 \times 0.3 = 0.1875\)，\(\pi_2 P_{21} = \tfrac38 \times 0.5 = 0.1875\)。\(\checkmark\) 雙向流量打平，天氣鏈可逆。（事實上任何兩狀態鏈對其穩態都自動滿足細緻平衡——流量只有一對，總平衡就是逐對平衡。）
Metropolis–Hastings 演算法
Metropolis 演算法（1953 年出身於洛沙拉摩斯，1970 年由 Hastings 推廣）用「提議—裁決」迴圈把細緻平衡變成通用抽樣引擎，只需要兩樣東西：能逐點計算的未正規化密度 \(\tilde{p}\)，與容易抽樣的提議分布。
目標 \(p(x) = \tilde{p}(x)/Z\)（只需能算 \(\tilde{p}\)，\(Z\) 可未知）。選一個提議分布（proposal distribution）\(q(x' \mid x)\)，如以現址為中心的常態「隨機漫步提議」\(x' \sim \mathcal{N}(x, s^2)\)。由任意 \(x_0\) 出發，重複：
提議：從 \(q(\cdot \mid x_t)\) 抽出候選點 \(x'\)；
計算接受機率： \[\alpha = \min\!\Bigl(1,\ \frac{\tilde{p}(x')\, q(x_t \mid x')}{\tilde{p}(x_t)\, q(x' \mid x_t)}\Bigr) \overset{\text{對稱提議}}{=} \min\!\Bigl(1,\ \frac{\tilde{p}(x')}{\tilde{p}(x_t)}\Bigr);\]
裁決：抽 \(U \sim \mathrm{Unif}(0,1)\)；\(U \le \alpha\) 則接受（\(x_{t+1} = x'\)），否則拒絕並留在原地（\(x_{t+1} = x_t\)，重複值照樣記入樣本）。
提議對稱（\(q(x' \mid x) = q(x \mid x')\)）的特例稱為 Metropolis 演算法。
Metropolis–Hastings 的高明之處：你永遠不需要正規化常數。接受機率只依賴比值 \(p(x')/p(x_t) = \frac{\tilde{p}(x')/Z}{\tilde{p}(x_t)/Z} = \tilde{p}(x')/\tilde{p}(x_t)\)——難算的 \(Z\) 上下消掉了。這讓完整的貝氏推論變得可行：後驗 \(\propto\) 概似 \(\times\) 先驗——恰好是第 9 章「算得出分子、算不出分母」的處境——如今可以直接抽樣。實作時取對數，用 \(\log U < \log\tilde{p}(x') - \log\tilde{p}(x_t)\) 裁決，避免高維密度的數值下溢。
目標為未正規化密度 \(\tilde{p}(x) = e^{-x^2/2}\)（即標準常態，略去 \(1/\sqrt{2\pi}\)），提議對稱。目前位於 \(x_t = 1.0\)。
(a) 提議 \(x' = 1.8\)：接受機率為何？若裁決時抽到 \(U = 0.41\)，鏈怎麼走？
(b) 提議 \(x' = 0.4\)：接受機率為何？
(a) 比值只需要指數部分： \[\alpha = \min\!\Bigl(1,\ \frac{e^{-1.8^2/2}}{e^{-1.0^2/2}}\Bigr) = \min\!\bigl(1,\ e^{-(1.62 - 0.5)}\bigr) = e^{-1.12} \approx 0.326.\] 抽到 \(U = 0.41 > 0.326\)：拒絕，\(x_{t+1} = 1.0\)——鏈原地停留，樣本序列裡 \(1.0\) 再記一次。重複值不是浪費：它正是「密度高處要多待」的機制。
(b) \(x' = 0.4\) 的密度更高：\(\tilde{p}(0.4)/\tilde{p}(1.0) = e^{-(0.08 - 0.5)} = e^{0.42} \approx 1.52 \ge 1\)，故 \(\alpha = 1\)，必定接受。規則的全貌：往高密度走免審核，往低密度走要抽籤，籤的難度正比於密度落差——長期下來，鏈在各區域的停留時間便與機率成正比。
MH 演算法產生的馬可夫鏈與目標分布 \(p\) 滿足細緻平衡，因此 \(p\) 是該鏈的穩態分布；若提議分布使鏈不可約且非週期（常態隨機漫步提議即滿足），軌跡的時間平均便收斂到 \(\E_p[g]\)。
證明對 \(x \ne x'\)，實際走到 \(x'\) 必須「提議它」且「接受它」，故轉移密度為 \(K(x \to x') = q(x' \mid x)\,\alpha(x, x')\)。以對稱提議計算機率流量： \[p(x)\,K(x \to x') = q(x' \mid x)\;p(x)\,\min\!\Bigl(1, \frac{p(x')}{p(x)}\Bigr) = q(x' \mid x)\,\min\bigl(p(x),\ p(x')\bigr),\] 最右式在對調 \(x \leftrightarrow x'\) 之下不變（提議對稱），故恰等於 \(p(x')\,K(x' \to x)\)——細緻平衡成立，由「細緻平衡 \(\Rightarrow\) 穩態」即得結論；全程只用到比值 \(p(x')/p(x) = \tilde{p}(x')/\tilde{p}(x)\)，\(Z\) 從未出場。非對稱提議用 Hastings 修正後，流量式變成 \(\min\bigl(p(x)\,q(x' \mid x),\ p(x')\,q(x \mid x')\bigr)\)，依然對稱。\(\blacksquare\)
把 MH 想成「尊重地形的隨機漫步」：上坡（\(\tilde p\) 變大）一律放行，下坡以新舊密度比的機率放行，於是漫步者自然聚集在高密度區、偶爾探訪低密度區，出沒頻率恰好正比於 \(p\)。妙處在於決策只用局部資訊（兩點的密度比），不需要全域地圖（\(Z\)）。
Gibbs 抽樣：逐座標的 MCMC
高維目標 \(p(x_1, \dots, x_d)\) 有時整體難抽，但「固定其他座標、只看一個座標」的條件分布卻是熟面孔（常態、Beta、Gamma……）——Gibbs 抽樣專吃這種結構。
Gibbs 抽樣（Gibbs sampling）對目標 \(p(x_1, \dots, x_d)\) 輪流更新每個座標：在第 \(t\) 輪，依序對 \(i = 1, \dots, d\) \[x_i^{(t+1)} \sim p\bigl(x_i \bigm| x_1^{(t+1)}, \dots, x_{i-1}^{(t+1)},\ x_{i+1}^{(t)}, \dots, x_d^{(t)}\bigr),\] 即從「給定目前其他所有座標值」的完整條件分布（full conditional）抽新值。Gibbs 是 MH 的特例：把完整條件分布當提議，接受機率恆為 \(1\)——每一步都被接受，沒有浪費的提議。
例如二元常態目標（相關係數 \(\rho\)）的兩個條件分布都是一維常態（第 5 章）：\(X \mid Y = y \sim \mathcal{N}(\rho y, 1 - \rho^2)\)、\(Y \mid X = x \sim \mathcal{N}(\rho x, 1 - \rho^2)\)；交替抽這兩個一維常態，就能產生二維聯合分布的樣本（練習 11.9）。共軛結構豐富的貝氏階層模型，正是 Gibbs 的主場。
MCMC 樣本不是 \(\iid\) 樣本——別直接套第 6–8 章的公式。三件事必須放在心上：
burn-in（暖身期）：前段軌跡帶著起點的偏見（尚未收斂到穩態），慣例把開頭一段（如前 \(10\%\)）整段丟棄。
自相關：相鄰樣本高度相關，\(T\) 個 MCMC 樣本只相當於 \(T_{\text{eff}} < T\) 個獨立樣本（有效樣本數，effective sample size）；標準誤要用 \(T_{\text{eff}}\) 算，否則高估精度。
混合（mixing）診斷：鏈可能困在某個峰附近，看似收斂實則只探索半張地圖；實務上看軌跡圖（trace plot）、跑多條不同起點的鏈互相比對（\(\hat{R}\) 統計量）。
MCMC 給的是「終究正確」的保證，不是「立刻正確」——鏈要跑得夠久，而「夠久」需要診斷來背書。
馬可夫鏈與蒙地卡羅如何貫穿機器學習
貝氏機器學習的古典引擎。後驗 \(\propto\) 概似 \(\times\) 先驗、證據積分算不動的困境（第 9 章），由 MCMC 正面解決：對後驗抽樣，用樣本回答一切問題。機率程式語言（PyMC、Stan）的核心是進化版 MCMC——哈密頓蒙地卡羅（HMC）用密度的梯度引導提議，骨架仍是「提議—裁決」。
序列建模的原點。神經網路之前，\(n\)-gram 模型統治語言建模數十年：bigram 是詞彙表上的馬可夫鏈，轉移機率由語料計數估計（練習 11.10）。大型語言模型是這條路的延伸：固定上下文窗之內，它是狀態空間巨大無比的高階馬可夫鏈，逐詞抽樣生成文字就是沿學到的鏈漫步。而強化學習（reinforcement learning）把環境形式化為馬可夫決策過程（Markov decision process, MDP）：狀態、行動、轉移機率 \(\Prob(s' \mid s, a)\) 與獎勵；固定策略後 MDP 塌縮成馬可夫鏈，貝爾曼方程能遞迴拆解長期報酬，靠的正是馬可夫性質。
擴散模型：馬可夫鏈的華麗現身。當今領先的圖像生成器——擴散模型（diffusion model）——就是馬可夫鏈。前向鏈把資料一步步加上高斯雜訊： \[X_t = \sqrt{1 - \beta_t}\, X_{t-1} + \sqrt{\beta_t}\, \varepsilon_t, \qquad \varepsilon_t \sim \mathcal{N}(\bm{0}, \bm{I}),\] 每步只依賴上一步——如假包換的馬可夫轉移，走幾百步後圖片化為純雜訊；神經網路學的是反向鏈——從雜訊出發、一步步去噪。生成一張圖，就是把反向鏈完整跑一遍。
馬可夫鏈與蒙地卡羅遍布現代 AI 的地基。MCMC 是貝氏機器學習的古典引擎，凡後驗沒有閉式解，就靠它抽樣。馬可夫鏈建模一切序列：\(n\)-gram 模型是詞彙上的馬可夫鏈，強化學習把世界形式化為馬可夫決策過程（MDP）。最驚人的是擴散模型——前向鏈逐步加噪、學到的反向鏈逐步去噪——生成一張圖片就是跑一條馬可夫鏈。而不論擴散還是自迴歸模型（autoregressive model），「抽樣生成」這件事本身，就是在學到的機率分布上做蒙地卡羅漫步。你在本章學的不是屠龍之技，而是生成式 AI 每天在做的事的數學名字。
Python 實作
動手驗證本章的關鍵論斷：穩態分布的特徵向量解法、長期停留頻率、蒙地卡羅估 \(\pi\)，以及 Metropolis–Hastings 抽樣。
import numpy as np
rng = np.random.default_rng(42)
# — 1. 天氣鏈：列 = 現在狀態（0 晴, 1 雨），行 = 下一狀態 — P = np.array([[0.7, 0.3], [0.5, 0.5]])
# — 2. 穩態分布 = P 轉置的特徵值 1 特徵向量（左特徵向量）— eigvals, eigvecs = np.linalg.eig(P.T) idx = np.argmin(np.abs(eigvals - 1.0)) # 找特徵值最接近 1 者 pi = np.real(eigvecs[:, idx]) pi = pi / pi.sum() # 正規化成機率分布 print(pi) # -> [0.625 0.375] print(pi @ P) # -> [0.625 0.375]（不動點驗證）
# — 3. 遍歷性：單一長軌跡的停留頻率也趨向穩態 — T = 200_000 state, visits = 0, np.zeros(2) for _ in range(T): state = rng.choice(2, p=P[state]) # 依目前狀態那一列轉移 visits[state] += 1 print(visits / T) # -> 約 [0.625 0.375]
特徵向量解與單一軌跡的停留頻率殊途同歸——收斂定理的數值化身。接著是蒙地卡羅與 MH。
# — 4. 蒙地卡羅估計 pi：四分之一圓的落點比例 — N = 1_000_000 pts = rng.random((N, 2)) # 單位正方形內均勻撒點 inside = (pts ** 2).sum(axis=1) <= 1.0 print(4 * inside.mean()) # -> 約 3.1416（誤差 0.0016）
# — 5. Metropolis-Hastings：從未正規化目標 exp(-x^2/2) 抽樣 — def log_p(x): # 只需要對數密度，差一個常數無妨 return -0.5 * x ** 2
n_steps, step = 100_000, 1.0 samples = np.empty(n_steps) x, n_accept = 3.0, 0 # 故意從尾巴出發，觀察 burn-in for t in range(n_steps): x_new = x + step * rng.normal() # 對稱提議：高斯隨機漫步 if np.log(rng.random()) < log_p(x_new) - log_p(x): x, n_accept = x_new, n_accept + 1 samples[t] = x # 拒絕時重複記錄原值
kept = samples[2_000:] # 丟掉前 2000 步暖身期 print(n_accept / n_steps) # -> 接受率約 0.70 print(kept.mean(), kept.std()) # -> 約 0.0 與 1.0
從未寫下正規化常數 \(1/\sqrt{2\pi}\)，保留樣本的均值 \(\approx 0\)、標準差 \(\approx 1\)——標準常態的指紋。起點 \(x_0 = 3.0\) 在目標尾巴上，前幾百步明顯偏高，正是要丟暖身期的原因；步長的權衡見練習 11.12。
隨機過程是以時間為索引的一族隨機變數 \(\{X_t\}\)；一次實現是一條樣本路徑，新挑戰是相依性。
馬可夫性質：未來只透過現在依賴過去——現在的狀態總結全部相關歷史。這是建模假設，換來 \(\bm{\pi}_{t+1} = \bm{\pi}_t\bm{P}\)：一個矩陣抓住整個動力學，\(n\) 步轉移就是 \(\bm{P}^n\)。
穩態分布解 \(\bm{\pi}\bm{P} = \bm{\pi}\)（特徵值 \(1\) 的左特徵向量）。不可約＋非週期的鏈有唯一穩態，不論起點都收斂到它，長期停留頻率亦然（遍歷性）——PageRank 即「隨機漫遊者」鏈的穩態分布。
蒙地卡羅用抽樣平均估計期望，誤差 \(\sigma/\sqrt{N}\) 與維度無關——高維積分的主力。
MCMC 造一條以目標為穩態的鏈：Metropolis–Hastings 的接受機率只用密度比值，正規化常數消失，使貝氏後驗抽樣可行；Gibbs 抽樣輪流抽完整條件分布，是接受率恆為 \(1\) 的 MH 特例。
細緻平衡（\(\pi_i P_{ij} = \pi_j P_{ji}\)）是穩態的充分非必要條件，也是 MH 正確性的來源；MCMC 樣本相關且需暖身——丟 burn-in、關注有效樣本數與混合診斷。
馬可夫鏈與蒙地卡羅貫穿 AI：\(n\)-gram 與語言模型、強化學習的 MDP、擴散模型的前向／反向鏈——生成式模型的「抽樣」就是在學到的分布上做蒙地卡羅漫步。
練習題
建議先獨立完成再對照詳解；標「程式」者需動手寫程式。
兩家電信公司 A 與 B 瓜分市場。每年 A 的客戶有 \(80\%\) 續留、\(20\%\) 跳槽到 B；B 的客戶有 \(70\%\) 續留、\(30\%\) 跳槽到 A。(a) 以「當年所屬公司」為狀態寫出轉移矩陣 \(\bm{P}\)，並驗證每列和為 \(1\)。(b) 這個模型的馬可夫假設在說什麼？請用一句話說明它可能失真之處。(c) 某客戶今年在 A，求兩年後仍在 A 的機率（請用路徑分解與矩陣平方各算一次）。
沿用天氣鏈 \(\bm{P} = \begin{pmatrix} 0.7 & 0.3\\ 0.5 & 0.5 \end{pmatrix}\)（狀態 1 晴、狀態 2 雨）。今天下雨。(a) 求後天（兩天後）下雨的機率，用「列出所有兩步路徑」與「計算 \((\bm{P}^2)_{22}\)」兩種方法互相驗證。(b) 求三天後下雨的機率。
設 \(X_1, X_2, \dots\) 為 \(\iid\) 公正硬幣（正面 \(= 1\)、反面 \(= 0\)）。判斷下列過程是否為馬可夫鏈，並證明或說明：(a) 累積正面數 \(S_t = X_1 + \cdots + X_t\)；(b) 移動平均 \(Y_t = (X_t + X_{t-1})/2\)（提示：比較 \(\Prob(Y_{t+1} = 1 \mid Y_t = \tfrac12)\) 與 \(\Prob(Y_{t+1} = 1 \mid Y_t = \tfrac12, Y_{t-1} = 1)\)）；(c) 若某過程的明天依賴「今天與昨天」兩天的狀態（二階記憶），要怎麼把它改造成馬可夫鏈？以兩種天氣為例，新的狀態空間有幾個狀態？
考慮一般的兩狀態鏈 \(\bm{P} = \begin{pmatrix} 1-p & p\\ q & 1-q \end{pmatrix}\)，\(0 < p + q < 2\)。(a) 解 \(\bm{\pi}\bm{P} = \bm{\pi}\)，證明穩態分布為 \(\bm{\pi} = \bigl[\tfrac{q}{p+q}, \tfrac{p}{p+q}\bigr]\)。(b) 代入天氣鏈（\(p = 0.3\)、\(q = 0.5\)）驗證前文的答案。(c) 用「特徵值之和 = 跡、之積 = 行列式」求 \(\bm{P}\) 的兩個特徵值，說明第二特徵值如何控制收斂速度，並算出天氣鏈的收斂倍率。(d) \(p = q = 1\) 時會發生什麼事？
一部機器每天處於三種狀態之一：正常（G）、老化（W）、故障（F）。動力學：正常的機器隔天 \(90\%\) 仍正常、\(10\%\) 進入老化；老化的機器隔天 \(70\%\) 維持老化、\(30\%\) 故障；故障的機器當天送修，隔天必定回到正常。(a) 寫出轉移矩陣。(b) 求穩態分布（以分數表示）。(c) 長期而言，機器有多少比例的日子處於故障狀態？
判斷下列兩條鏈是否滿足收斂定理的條件，並描述 \(\bm{\pi}_t\) 的長期行為。(a) \(\bm{P}_1 = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}\)：檢查不可約與週期性、求穩態，從 \(\bm{\pi}_0 = [1, 0]\) 出發算 \(\bm{\pi}_1, \bm{\pi}_2, \bm{\pi}_3\)，分布收斂嗎？(b) \(\bm{P}_2 = \begin{pmatrix} 1 & 0\\ 0.5 & 0.5 \end{pmatrix}\)：檢查不可約性、求穩態，從 \(\bm{\pi}_0 = [0, 1]\) 出發求 \(\bm{\pi}_t\) 的一般式與極限。(c) 收斂定理的哪個條件各自失效？結局有何不同？
(a) 證明：若機率分布 \(\bm{\pi}\) 與轉移矩陣 \(\bm{P}\) 滿足細緻平衡 \(\pi_i P_{ij} = \pi_j P_{ji}\)（對所有 \(i, j\)），則 \(\bm{\pi}\) 是穩態分布。(b) 驗證循環鏈 \(\bm{P} = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}\) 以均勻分布為穩態，卻不滿足細緻平衡——結論：細緻平衡是穩態的充分非必要條件。(c) 用「機率流量」的語言解釋 (a) 與 (b) 的差異：細緻平衡要求什麼？穩態只要求什麼？
三頁網路：A 連向 B；B 連向 A；C 連向 A（C 沒有任何入鏈）。採用含阻尼的 PageRank：\(\mathrm{PR}(i) = \tfrac{1-d}{3} + d \sum_{j : j \to i} \mathrm{PR}(j)/L(j)\)，其中 \(L(j)\) 為頁 \(j\) 的對外連結數，阻尼係數 \(d = 0.85\)。(a) 寫出三頁的方程組。(b) 解出三頁的 PageRank 分數（保留四位小數），並驗證總和為 \(1\)。(c) 說明為何 \(\mathrm{PR}(C)\) 恰為 \((1-d)/3\)；若把 \(d\) 設為 \(1\)（無阻尼），這個網路會出什麼問題？（提示：檢查 \(\mathrm{A} \leftrightarrow \mathrm{B}\) 子鏈的週期性與 C 的地位。）
目標分布為二元常態，兩座標的相關係數 \(\rho = 0.8\)，邊際皆為標準常態。已知完整條件分布為 \(X \mid Y = y \sim \mathcal{N}(0.8y, 0.36)\) 與 \(Y \mid X = x \sim \mathcal{N}(0.8x, 0.36)\)。(a) 寫出 Gibbs 抽樣的完整步驟（含初始化與迭代）。(b) 解釋「Gibbs 是接受機率恆為 \(1\) 的 MH 特例」的意義、好處與前提。(c) 當 \(\rho \to 1\) 時，Gibbs 的表現會如何變化？為什麼？
語料庫只有一句話：「我 愛 機率 我 愛 統計」。(a) 用最大概似估計（即計數比例）建立 bigram 模型的轉移機率表。(b) 從「我」出發依鏈生成兩個詞，求生成出「我 愛 統計」的機率。(c) 說明為何 bigram 模型是馬可夫鏈；trigram 模型（下一詞依賴前兩詞）又如何納入馬可夫框架？
你用 \(N\) 次獨立模擬估計某事件的機率 \(p \approx 0.2\)。(a) \(N = 1000\) 時，估計的標準誤約是多少？(b) 想把標準誤縮小為原本的十分之一，需要多少樣本？(c) 已知 \(d\) 維的梯形法數值積分誤差階為 \(N^{-2/d}\)（\(N\) 為函數求值次數），蒙地卡羅為 \(N^{-1/2}\)：\(d\) 超過多少時蒙地卡羅的收斂階勝出？這對貝氏推論意味著什麼？
(a) 模擬天氣鏈 \(200{,}000\) 步，統計兩狀態的停留頻率，與理論穩態 \([0.625, 0.375]\) 比較。(b) 實作 Metropolis–Hastings 抽樣未正規化目標 \(\tilde{p}(x) = e^{-x^2/2}\)（提議 \(x' \sim \mathcal{N}(x_t, 1)\)），丟掉前 \(2000\) 步 burn-in，檢查樣本平均 \(\approx 0\)、標準差 \(\approx 1\)。(c) 把提議步長改為 \(0.05\) 與 \(50\)，記錄接受率並觀察樣本品質，解釋「步長太小」與「步長太大」各自的病徵。
練習題詳解
(a) 狀態順序 \((\mathrm{A}, \mathrm{B})\)： \[\bm{P} = \begin{pmatrix} 0.8 & 0.2\\ 0.3 & 0.7 \end{pmatrix}, \qquad 0.8 + 0.2 = 1,\quad 0.3 + 0.7 = 1. \ \checkmark\]
(b) 馬可夫假設：明年的選擇只依賴今年所屬的公司，與更早的歷史無關。可能失真：「曾被 A 惹惱而離開」的客戶回流意願，可能低於從未用過 A 的客戶——歷史其實有影響，模型選擇忽略它。
(c) 路徑分解：A\(\to\)A\(\to\)A 貢獻 \(0.8 \times 0.8 = 0.64\)，A\(\to\)B\(\to\)A 貢獻 \(0.2 \times 0.3 = 0.06\)，合計 \(0.70\)。矩陣法：\((\bm{P}^2)_{11} = 0.8 \times 0.8 + 0.2 \times 0.3 = 0.70\)。\(\checkmark\)
(a) 路徑法：雨\(\to\)雨\(\to\)雨貢獻 \(0.5 \times 0.5 = 0.25\)，雨\(\to\)晴\(\to\)雨貢獻 \(0.5 \times 0.3 = 0.15\)，合計 \(0.40\)。矩陣法：由第 11.2 節例題 \(\bm{P}^2 = \begin{pmatrix} 0.64 & 0.36\\ 0.60 & 0.40 \end{pmatrix}\)，讀出 \((\bm{P}^2)_{22} = 0.40\)。\(\checkmark\)
(b) 取 \(\bm{P}^3 = \bm{P}^2\bm{P}\) 第 2 列第 2 行：\((\bm{P}^3)_{22} = 0.60 \times 0.3 + 0.40 \times 0.5 = 0.38\)。路徑驗算（四條三步路徑）：雨雨雨雨 \(0.125\)、雨雨晴雨 \(0.075\)、雨晴雨雨 \(0.075\)、雨晴晴雨 \(0.105\)，合計 \(0.38\)。\(\checkmark\) 數列 \(0.5, 0.40, 0.38, \dots\) 正逐步逼近穩態值 \(0.375\)。
(a) 是馬可夫鏈。\(S_{t+1} = S_t + X_{t+1}\)，而 \(X_{t+1}\) 與 \(X_1, \dots, X_t\) 獨立，故 \(\Prob(S_{t+1} = s + 1 \mid S_t = s,\ \text{過去}) = \Prob(X_{t+1} = 1) = \tfrac12\)，只依賴目前的 \(s\)。（狀態空間可數無限，馬可夫性照樣成立。）
(b) 不是馬可夫鏈。依提示計算兩個條件機率。無額外歷史時：\(Y_t = \tfrac12\) 表示 \((X_{t-1}, X_t)\) 為 \((0,1)\) 或 \((1,0)\)，兩者等可能，故 \(\Prob(Y_{t+1} = 1 \mid Y_t = \tfrac12) = \Prob(X_t = 1 \mid Y_t = \tfrac12) \times \Prob(X_{t+1} = 1) = \tfrac12 \times \tfrac12 = \tfrac14\)。加入 \(Y_{t-1} = 1\) 後：\(Y_{t-1} = 1\) 迫使 \(X_{t-1} = 1\)，再由 \(Y_t = \tfrac12\) 得 \(X_t = 0\)，於是 \(Y_{t+1} \le \tfrac12\)， \[\Prob(Y_{t+1} = 1 \mid Y_t = \tfrac12,\ Y_{t-1} = 1) = 0 \ne \tfrac14.\] 更早的歷史改變了預測——馬可夫性不成立。直觀原因：\(Y_t\) 遺失了「哪一枚是正面」的資訊，而那正是預測 \(Y_{t+1}\) 需要的。
(c) 擴充狀態空間：定義 \(Z_t = (X_{t-1}, X_t)\)，把「最近兩天」整包當作新狀態——已知 \(Z_t\) 則明天的分布完全確定，\(\{Z_t\}\) 是一階馬可夫鏈。兩種天氣時新狀態空間有 \(2 \times 2 = 4\) 個狀態。一般地，\(k\) 階記憶可用「最近 \(k\) 期的元組」化為一階馬可夫，代價是狀態數指數成長——\(n\)-gram 模型隨 \(n\) 爆炸的原因（練習 11.10）。
(a) 展開 \(\bm{\pi}\bm{P} = \bm{\pi}\) 的第一個分量：\(\pi_1(1-p) + \pi_2 q = \pi_1\)，即 \(p\,\pi_1 = q\,\pi_2\)（第二個分量給出同一條方程）。配合 \(\pi_1 + \pi_2 = 1\)：由 \(\pi_1 = \tfrac{q}{p}\pi_2\) 代入得 \(\pi_2\bigl(\tfrac{q}{p} + 1\bigr) = 1\)，故 \(\pi_2 = \tfrac{p}{p+q}\)、\(\pi_1 = \tfrac{q}{p+q}\)，即 \(\bm{\pi} = \bigl[\tfrac{q}{p+q},\ \tfrac{p}{p+q}\bigr]\)。直觀：\(p, q\) 是離開狀態 1、2 的速率，越難離開的狀態累積越多機率，\(\pi_1 : \pi_2 = q : p\)。
(b) 天氣鏈 \(p = 0.3\)、\(q = 0.5\)：\(\bm{\pi} = \bigl[\tfrac{0.5}{0.8}, \tfrac{0.3}{0.8}\bigr] = \bigl[\tfrac58, \tfrac38\bigr] = [0.625, 0.375]\)。\(\checkmark\)
(c) 跡為 \(2 - p - q\)，行列式為 \((1-p)(1-q) - pq = 1 - p - q\)；取 \(\lambda_1 = 1\)、\(\lambda_2 = 1 - p - q\) 恰好「和為跡、積為行列式」。把 \(\bm{\pi}_t - \bm{\pi}\) 沿特徵方向分解：偏差全落在 \(\lambda_2\) 方向、每步乘一次 \(\lambda_2\)，故 \(\lVert \bm{\pi}_t - \bm{\pi} \rVert \propto |1 - p - q|^{\,t}\)。天氣鏈 \(\lambda_2 = 0.2\)，與收斂表「差距每步縮小為 \(0.2\) 倍」一致。
(d) \(p = q = 1\) 時 \(\lambda_2 = -1\)：\(\bm{P} = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}\) 是週期 \(2\) 的強制互換鏈。穩態 \([\tfrac12, \tfrac12]\) 仍存在，但偏差方向每步乘 \(-1\)、永不衰減——分布振盪不收斂（詳見練習 11.6）。
(a) 狀態順序 \((\mathrm{G}, \mathrm{W}, \mathrm{F})\)： \[\bm{P} = \begin{pmatrix} 0.9 & 0.1 & 0\\ 0 & 0.7 & 0.3\\ 1 & 0 & 0 \end{pmatrix}.\]
(b) 寫出 \(\bm{\pi}\bm{P} = \bm{\pi}\) 的三個分量（「流入 = 存量」）： \[\begin{aligned} \pi_G &= 0.9\,\pi_G + \pi_F &&\Longrightarrow\ \pi_F = 0.1\,\pi_G,\\ \pi_W &= 0.1\,\pi_G + 0.7\,\pi_W &&\Longrightarrow\ 0.3\,\pi_W = 0.1\,\pi_G \ \Longrightarrow\ \pi_W = \tfrac13\,\pi_G,\\ \pi_F &= 0.3\,\pi_W &&\Longrightarrow\ 0.3 \times \tfrac13\,\pi_G = 0.1\,\pi_G.\ \checkmark\ (\text{自動滿足}) \end{aligned}\] 正規化：\(\pi_G\bigl(1 + \tfrac13 + \tfrac1{10}\bigr) = \tfrac{43}{30}\pi_G = 1\)，故 \(\bm{\pi} = \bigl[\tfrac{30}{43}, \tfrac{10}{43}, \tfrac{3}{43}\bigr]\)。驗算 \(\bm{\pi}\bm{P}\)：第一分量 \(0.9 \times \tfrac{30}{43} + \tfrac{3}{43} = \tfrac{30}{43}\)、第二分量 \(0.1 \times \tfrac{30}{43} + 0.7 \times \tfrac{10}{43} = \tfrac{10}{43}\)、第三分量 \(0.3 \times \tfrac{10}{43} = \tfrac{3}{43}\)，全數吻合。\(\checkmark\)
(c) 長期故障比例 \(= \pi_F = \tfrac{3}{43} \approx 0.0698\)，即約 \(7.0\%\) 的日子在維修。（數值：\(\bm{\pi} \approx [0.6977, 0.2326, 0.0698]\)。）
(a) \(\bm{P}_1\)：不可約——\(1 \to 2\) 與 \(2 \to 1\) 都一步可達。週期性——從狀態 1 只能在偶數步返回，\(d(1) = \gcd\{2, 4, \dots\} = 2\)：週期 2，非週期條件不成立。穩態：\(\pi_1 = \pi_2\) 配合正規化給 \([\tfrac12, \tfrac12]\)（唯一）。但從 \(\bm{\pi}_0 = [1, 0]\) 出發：\(\bm{\pi}_1 = [0,1]\)、\(\bm{\pi}_2 = [1,0]\)、\(\bm{\pi}_3 = [0,1]\)……分布永遠振盪、不收斂（除非恰從 \([\tfrac12,\tfrac12]\) 出發）；不過時間平均仍收斂到 \([\tfrac12, \tfrac12]\)。
(b) \(\bm{P}_2\)：狀態 1 是吸收態（\(P_{11} = 1\)），從 1 永遠到不了 2——不可約條件不成立。穩態：第二分量給 \(0.5\,\pi_2 = \pi_2\)，故 \(\pi_2 = 0\)、\(\bm{\pi} = [1, 0]\)（唯一）。從 \(\bm{\pi}_0 = [0, 1]\) 出發，每步雨側質量減半：\(\bm{\pi}_t = [\,1 - 0.5^{\,t},\ 0.5^{\,t}\,] \to [1, 0]\)，分布仍然收斂——質量被吸收態吸光。
(c) (a) 敗在非週期性：穩態唯一卻因固定節拍振盪而不收斂。(b) 敗在不可約性：此例仍收斂，但那是「被吸收」而非遍歷探索——若鏈中有兩個吸收態，極限就依賴起點。教訓：定理的條件是充分條件，缺了它們，結局可能振盪、可能依賴起點，須逐案分析。
(a) 對任意狀態 \(j\)，利用細緻平衡逐項替換： \[(\bm{\pi}\bm{P})_j = \sum_i \pi_i P_{ij} = \sum_i \pi_j P_{ji} = \pi_j \sum_i P_{ji} = \pi_j,\] 最後一步用了「\(\bm{P}\) 每列和為 1」（\(\sum_i P_{ji} = 1\) 是對狀態 \(j\) 那一列求和）。故 \(\bm{\pi}\bm{P} = \bm{\pi}\)。\(\blacksquare\)
(b) 穩態驗證：循環鏈中每個狀態恰有一個「上游」（機率 1 流入），故 \((\bm{\pi}\bm{P})_1 = \pi_3 = \tfrac13 = \pi_1\)，其餘同理，\([\tfrac13, \tfrac13, \tfrac13]\) 確為穩態。細緻平衡檢查狀態對 \((1, 2)\)：\(\pi_1 P_{12} = \tfrac13 \times 1 = \tfrac13\)，但 \(\pi_2 P_{21} = \tfrac13 \times 0 = 0\)，不相等——細緻平衡不成立。（此鏈週期為 3，分布也不收斂，但穩態照樣存在。）
(c) 細緻平衡要求每一對狀態之間的雙向流量各自打平（系統可逆）；穩態只要求每個狀態的總流入等於總流出，允許「環狀單行道」——(b) 的鏈裡機率沿 \(1 \to 2 \to 3 \to 1\) 永恆繞圈，每站進出平衡，但每段路都是單向的。逐對平衡強於逐站平衡：前者蘊涵後者，反之不然。
(a) 各頁的對外連結數：\(L(\mathrm{A}) = L(\mathrm{B}) = L(\mathrm{C}) = 1\)。入鏈：A 收到 B 與 C 的連結、B 收到 A 的連結、C 沒有入鏈。以 \(d = 0.85\)、\((1-d)/3 = 0.05\)： \[\begin{aligned} \mathrm{PR}(\mathrm{A}) &= 0.05 + 0.85\,\bigl[\mathrm{PR}(\mathrm{B}) + \mathrm{PR}(\mathrm{C})\bigr],\\ \mathrm{PR}(\mathrm{B}) &= 0.05 + 0.85\,\mathrm{PR}(\mathrm{A}),\\ \mathrm{PR}(\mathrm{C}) &= 0.05. \end{aligned}\]
(b) 把 \(\mathrm{PR}(\mathrm{C}) = 0.05\) 與第二式代入第一式： \[\mathrm{PR}(\mathrm{A}) = 0.05 + 0.85\bigl[0.05 + 0.85\,\mathrm{PR}(\mathrm{A}) + 0.05\bigr] = 0.135 + 0.7225\,\mathrm{PR}(\mathrm{A}),\] 解得 \(\mathrm{PR}(\mathrm{A}) = 0.135/0.2775 = \tfrac{18}{37} \approx 0.4865\)，於是 \(\mathrm{PR}(\mathrm{B}) = 0.05 + 0.85 \times 0.4865 \approx 0.4635\)。總和驗算：\(0.4865 + 0.4635 + 0.0500 = 1.0000\)。\(\checkmark\)
(c) C 沒有入鏈，加總項為空，只剩隨機傳送的保底分數 \((1-d)/3\)。若 \(d = 1\)：C 變成分數 \(0\) 的暫態，且 \(\mathrm{A} \leftrightarrow \mathrm{B}\) 子鏈是週期 \(2\) 的強制互換，冪迭代永遠振盪、不收斂。阻尼 \(d < 1\) 讓每頁到每頁都有正機率，一舉保證不可約與非週期——Google 採用 \(d = 0.85\) 的數學理由。
(a) Gibbs 抽樣步驟：
初始化 \((x^{(0)}, y^{(0)})\)，例如 \((0, 0)\)；
第 \(t\) 輪：先抽 \(x^{(t+1)} \sim \mathcal{N}\bigl(0.8\,y^{(t)},\ 0.36\bigr)\)（用舊的 \(y\)），再抽 \(y^{(t+1)} \sim \mathcal{N}\bigl(0.8\,x^{(t+1)},\ 0.36\bigr)\)（用剛更新的 \(x\)）——每次更新都用其他座標的最新值；
重複 \(T\) 輪，丟掉前段 burn-in，其餘 \((x^{(t)}, y^{(t)})\) 即為聯合分布的（相關）樣本。
(b) 把「從完整條件分布抽新值」當提議代入 Hastings 接受率，所有因子恰好相消、\(\alpha = 1\)：沒有提議被浪費，也不需調步長。前提是每個完整條件分布都能精確抽樣——共軛貝氏模型常見；抽不動時退回 MH 或混用。
(c) 條件變異數 \(1 - \rho^2 \to 0\)：給定 \(y\)，\(x\) 幾乎被釘死在 \(\rho y\)，反之亦然。鏈只能沿 \(x \approx y\) 的狹長山脊以極小步伐鋸齒前進，自相關暴增、混合極慢——理論上仍收斂，實務上要極長的鏈；高相關時應改用 HMC 或重新參數化。
(a) 語料的相鄰詞對：（我,愛）、（愛,機率）、（機率,我）、（我,愛）、（愛,統計）。逐詞統計：「我」作為前詞 2 次、後接「愛」2 次，\(\Prob(\text{愛} \mid \text{我}) = 1\)；「愛」作為前詞 2 次、後接「機率」「統計」各 1 次，\(\Prob(\text{機率} \mid \text{愛}) = \Prob(\text{統計} \mid \text{愛}) = \tfrac12\)；「機率」後接「我」1 次，\(\Prob(\text{我} \mid \text{機率}) = 1\)。（「統計」位於句尾，沒有後繼觀測。）
(b) 沿鏈相乘：\(\Prob(\text{我} \to \text{愛} \to \text{統計}) = \Prob(\text{愛} \mid \text{我}) \times \Prob(\text{統計} \mid \text{愛}) = 1 \times \tfrac12 = \tfrac12\)。
(c) bigram 假設「下一個詞只依賴目前這個詞」——詞彙表上的馬可夫性質，語料計數給出轉移機率的最大概似估計。trigram 用練習 11.3(c) 的擴充狀態技巧——以「相鄰詞對」為狀態——化為一階馬可夫鏈，代價是狀態數從 \(|V|\) 變成 \(|V|^2\)。上下文窗長 \(k\) 的語言模型同理是 \(|V|^k\) 個狀態上的馬可夫鏈。
(a) 事件指示變數的變異數為 \(p(1-p)\)，故 \(\se(\hat{p}) = \sqrt{p(1-p)/N} = \sqrt{0.2 \times 0.8/1000} \approx 0.0126\)，估計值約在 \(0.2 \pm 0.025\)（兩個標準誤）之間。
(b) 標準誤 \(\propto 1/\sqrt{N}\)：縮小 \(10\) 倍需要 \(N\) 放大 \(10^2 = 100\) 倍，即 \(N = 100{,}000\)。
(c) 比較收斂階：\(\tfrac12 > \tfrac{2}{d} \Leftrightarrow d > 4\)。維度超過 \(4\)，蒙地卡羅的收斂階就勝過梯形法，且優勢隨 \(d\) 擴大——格點法受維度詛咒，蒙地卡羅免疫。貝氏後驗動輒數十、數百維，抽樣是唯一活路——MCMC 成為貝氏計算基石的根本原因。
(a) 的模擬即第 7 節程式的第 3 段，輸出約 \([0.6249,\ 0.3751]\)，與理論穩態 \([0.625, 0.375]\) 一致（誤差量級 \(1/\sqrt{200000} \approx 0.002\)）——遍歷定理的實地驗證。(b)(c) 參考程式與輸出：
import numpy as np rng = np.random.default_rng(1)
def mh(step, n=100_000, x0=3.0): x, acc = x0, 0 out = np.empty(n) for t in range(n): x_new = x + step * rng.normal() if np.log(rng.random()) < 0.5 * (x**2 - x_new**2): x, acc = x_new, acc + 1 out[t] = x return out[2_000:], acc / n
for step in [0.05, 1.0, 50.0]: s, rate = mh(step) print(step, round(rate, 2), round(s.mean(), 2), round(s.std(), 2))
(b) 步長 \(1.0\) 時接受率約 \(0.70\)，保留樣本的平均 \(\approx 0.00\)、標準差 \(\approx 1.00\)：從未正規化的 \(e^{-x^2/2}\) 成功重建了標準常態。
(c) 步長 \(0.05\)（太小）：接受率約 \(0.98\)，看似極佳實則每步只挪一點點，自相關極強、探索極慢，均值與標準差仍可能明顯偏離目標（有效樣本極少、暖身殘留更久）。步長 \(50\)（太大）：提議幾乎都落在密度近零的遠處，接受率崩到約 \(0.02\)，鏈長時間卡在原地。接受率本身不是目標，「單位計算量走過的有效距離」才是；一維隨機漫步提議的甜蜜區間約為接受率 \(0.4\) 至 \(0.7\)。
公理給了語言，分布給了模型，極限定理給了保證，而馬可夫鏈與蒙地卡羅把這一切變成會動的演算法——下次看到擴散模型生成圖片，你知道那是一條馬可夫鏈正在眼前奔跑。