跳轉到

6.2 Markov 鏈（1906）#

本章導言#

獨立是理想，現實有記憶。馬可夫鏈只保留最小限度的記憶：下一步只依賴現在。Andrei Markov（馬可夫，1856–1922） 1906 年建立此模型，動機竟是哲學論戰——他要證明大數法則不需要獨立性。本節介紹馬可夫鏈的定義、平穩分布與收斂理論，以及它從聖彼得堡的辯論到 Google 搜尋引擎的旅程。

Markov 的哲學動機#

十九世紀末，Nekrasov（涅克拉索夫） 宣稱大數法則依賴於「自由意志」：獨立性在道德哲學上是自由意志的化身，因此機率論證明了俄羅斯教會的教義。Markov——性格剛烈、以筆戰聞名的聖彼得堡數學家——被此謬論激怒，決定證明相依變數也服從大數法則。他在 1906 年的論文中考慮「只依賴前一步」的變數序列，證明其時間平均收斂。馬可夫鏈作為「反神學的數學」誕生——數學史上又一次，抽象理論起於具體的爭議。

Markov 本人的示範應用也充滿文學趣味：1913 年他分析了普希金《葉甫蓋尼．奧涅金》前兩萬個字母，把字母分為母音/子音兩態，計算轉移頻率（母音後 66.3% 是子音等），驗證了鏈式相依模型對文本的描述力——史上第一次對文學文本的統計建模，比資料科學早了一百年。

定義與基本例子#

馬可夫性： \(\mathbb{E}[\text{未來} \mid \text{現在與過去}] = \mathbb{E}[\text{未來} \mid \text{現在}]\) 。離散時間有限狀態鏈由轉移矩陣 \(P = (p_{ij})\) 完全刻畫：

\[ p_{ij} = P(X_{n+1} = j \mid X_n = i), \qquad \sum_j p_{ij} = 1, \quad p_{ij} \ge 0. \]

\(n\) 步轉移機率由矩陣冪給出： \(P^{(n)} = P^n\) ，這是 Chapman–Kolmogorov 方程（Chapman 1928、Kolmogorov 1936）的矩陣形式：兩步機率 = 一步機率的矩陣乘積（經由所有中間狀態求和）。經典例子：

  • 天氣鏈：晴/雨兩態， \(P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}\) （晴後 90% 仍晴、雨後 50% 轉晴）。
  • 隨機漫步（6.1 節）：整數軸上的鏈， \(p_{i, i\pm 1} = \frac{1}{2}\) 。
  • Ehrenfest 罐子模型（1907，物理中的熱力學不可逆性模型）： \(N\) 個球在兩罐間隨機移一顆，狀態 = 左罐球數；它展示了「微觀可逆 + 宏觀趨平衡」的範式。

平穩分布與收斂#

平穩分布 \(\pi\) ： \(\pi = \pi P\) （行向量的不變測度），分量 \(\pi_j \ge 0\) 、 \(\sum \pi_j = 1\) 。若鏈不可約（任一狀態可達任一狀態）且正常返（平均返回時間有限），則平穩分布唯一存在，且若鏈非週期（各狀態的返回步數最大公因數為 1），則：

\[ P^n \longrightarrow \mathbf{1}\pi \quad \text{（每行趨於 } \pi\text{）}, \qquad \frac{1}{n} \sum_{k=0}^{n-1} \mathbf{1}\{X_k = j\} \to \pi_j \ \text{幾乎必然}. \]

第二式是遍歷定理（Markov 1906 年的原始結果）：時間平均 = 平穩平均——它正是 Markov 為反駁 Nekrasov 而證的定理：相依序列也有大數法則。平穩分布的逐分量解釋優美： \(\pi_j = \frac{1}{\mathbb{E}[\text{返回 } j \text{ 的時間}]}\) ——長期停留比例 = 平均返回時間的倒數（Kac 遞迴公式, 1947）。

天氣鏈的平穩分布：解 \(\pi = \pi P\) ，即 \(\pi_1 = 0.9\pi_1 + 0.5\pi_2\) 、 \(\pi_1 + \pi_2 = 1\) ，得 \(\pi = (0.833, 0.167)\) ——無論明天天氣，長期而言 83.3% 的日子晴朗。初始條件被遺忘（收斂），這是馬可夫鏈的第一神蹟。

不可逆性與熵：物理的借用#

天氣鏈的轉移矩陣不對稱（ \(0.1 \ne 0.5\) ），但長期分布穩定——微觀過程可以不可逆、宏觀分布卻趨平衡。這正是 Boltzmann 統計力學的核心悖論的離散版：Ehrenfest 夫婦 1907 年的罐子模型精確演示了「熵增」的機率本質（離開平衡態的機率隨距離指數下降，但精確可逆的動力學不禁止返回）。馬可夫鏈因此成為統計力學、化學動力學（反應速率方程是連續時間馬可夫鏈）、排隊論（Erlang 1909 年的電話流量理論是先驅）的共同語言。

一個具體例題#

例題 6.2.1：某串流平台的會員狀態分為「活躍 A」與「沉睡 S」。每日轉移：A → A 0.8、A → S 0.2；S → A 0.3、S → S 0.7。(a) 求平穩分布；(b) 活躍用戶「連續 3 天活躍」的機率；(c) 從沉睡狀態出發，平均多久首次回到活躍？(d) 討論平台應如何用此模型。

解：

(a) 解 \(\pi = \pi P\) ：

\[ \pi_A = 0.8\pi_A + 0.3\pi_S \ \Rightarrow\ 0.2\pi_A = 0.3\pi_S \ \Rightarrow\ \frac{\pi_A}{\pi_S} = \frac{3}{2}, \]

加上歸一 \(\pi_A + \pi_S = 1\) ，得 \(\pi = (0.6, 0.4)\) 。長期 60% 的日子處於活躍。

(b) 連續 3 天活躍（已知今天是 A，接下來兩天也是 A）：

\[ P(\text{接下來兩天皆 A} \mid \text{今天 A}) = 0.8^2 = 0.64. \]

（若不條件於今天，則用 \(\pi_A \times 0.8^2 = 0.6 \times 0.64 = 0.384\) 。）

(c) 首次返回時間的期望：對正常返狀態， \(\mathbb{E}[\text{返回 S 時間}] = \frac{1}{\pi_S} = \frac{1}{0.4} = 2.5\) 天——但題問的是「離開 A 後多久回到 A」：設 \(m_A\) = 從 A 出發返回 A 的期望時間 \(= \frac{1}{0.6} \approx 1.67\) 天；而「從 S 到 A 的首達期望」 \(f_S\) 滿足 \(f_S = 1 + 0.7 f_S\) ，得 \(f_S = \frac{1}{0.3} \approx 3.33\) 天。兩者不同：返回時間與首達時間是不同概念，Kac 公式管前者。

(d) 此模型的商業用途：計算「沉睡用戶的再活化期望時間」（3.33 天決定喚醒節奏的頻率）、估算長期活躍占比（60%，行銷目標的理論上限）、以及「連續沉睡 \(k\) 天的機率」 \(0.7^k\) （決定流失警示閾值，如 \(k = 5\) 時僅 \(0.168\) ，可作為觸發促銷的界）。這類「狀態遷移 + 平穩分析 + 首達時間」的組合是現代用戶行為分析（客戶生命週期模型）的標準工具，其數學正是 1906 年的馬可夫鏈。

歷史啟示#

  • 爭議催生理論：Nekrasov 的神學謬論引出了馬可夫鏈——科學史中「反駁荒謬」的生產力常被低估。
  • 最小記憶假設的威力：只記住現在，鏈的理論卻能覆蓋排隊、遺傳（Hardy–Weinberg 動力學）、語言、網頁——「局部性」假設的普遍適用令人驚訝。
  • 時間平均 = 空間平均：遍歷定理是統計力學與機率論的橋樑（5.1 節場景四），Markov 與 Boltzmann 的思想在此匯流。
  • 初始遺忘與平穩性：「系統忘記起點、趨向固定分布」是熱平衡、市場均衡、搜尋收斂的共同數學。

與其他章節及領域的關聯#

  • 6.1 節：隨機漫步是最簡馬可夫鏈；賭徒破產的差分方程是其勢論。
  • 4.3、5.3 節：馬可夫性是條件期望語言下的性質；鏈的構造依賴 Kolmogorov 延拓定理。
  • 6.3 節：Poisson 過程是連續時間馬可夫鏈（純生過程）的基礎。
  • 7.2 節：Wiener 過程是連續時間連續狀態的馬可夫過程。
  • 10.2 節：MCMC（Metropolis–Hastings、Gibbs）以馬可夫鏈的收斂定理為根基——現代貝氏計算的全部合法性來自本節。
  • 遺傳學：Fisher–Wright 與 Moran 模型（1950s）以馬可夫鏈描述基因頻率漂移。
  • 語言與資料科學：Markov 1913 年的文本分析 → 隱馬可夫模型（1960s–70s，語音辨識）→ 現代序列模型的前身。

練習#

  1. 對天氣鏈 \(P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}\) ，計算 \(P^2\) ，並求「今天晴、後天雨」的機率。
  2. 證明：若 \(P\) 的所有元素皆正，則鏈不可約且非週期。
  3. Ehrenfest 模型（ \(N = 2\) ）：寫出轉移矩陣、求平穩分布（答案應為 \(\binom{N}{j}/2^N\) ，二項分布！），並解釋與 Maxwell–Boltzmann 分布的關係。
  4. 例題 6.2.1 中，求「從 A 出發、首次進入 S 發生在第 3 天」的機率（首達時間分布）。
  5. 思考題：Markov 1913 年以母音/子音兩態分析《奧涅金》。請設計一個三態模型（如字長）分析中文文本，討論「馬可夫性」假設在語言中的合理與不合理之處（提示：語法有長程結構）。

進階研讀：鏈理論的五個深化場景#

場景一：分支過程與滅絕。Galton–Watson 過程（1874）：每個個體獨立產生後代，後代數分布的 PGF 為 \(G\) （2.3 節場景三）。滅絕機率 \(q\) 是 \(q = G(q)\) 的最小非負根； \(\mathbb{E}[\text{後代}] \le 1\) 必滅絕、 \(> 1\) 時滅絕機率 \(< 1\) 。它是馬可夫鏈的「狀態 = 人口數」特例，應用於姓氏存續（Galton 的原始問題）、鏈式反應（Neutron 增殖與核武臨界質量, 1940s）、病毒傳播的早期傳染學。

場景二：可逆鏈與細致平衡。若存在 \(\pi\) 使 \(\pi_i p_{ij} = \pi_j p_{ji}\) （細致平衡），則 \(\pi\) 是平穩分布且鏈可逆。Metropolis–Hastings 演算法（10.2 節）的設計目標正是「構造以目標分布為平穩分布的可逆鏈」——統計力學的平衡態思想（Boltzmann 分布）直接成為演算法的設計準則。這是二十世紀機率、物理、計算的三方會師。

場景三：收斂速率與譜隙。鏈收斂到平穩分布的速度由轉移矩陣的第二大特徵值 \(\lambda_2\) 控制：總變差距離 \(\le C \lambda_2^n\) 。譜隙 \(1 - \lambda_2\) 越大、混合越快。「洗牌需要洗幾次才均勻」的著名研究（Aldous–Diaconis 1986： riffle shuffle 約 7 次，閾值現象）是此理論的明星應用；混合時間也決定 MCMC 的實際可用性——馬可夫鏈的「效率學」。

場景四：隱馬可夫模型。狀態不可觀測、只能觀測到狀態的隨機函數（發射機率），構成 HMM（Baum 等人 1960s）。維特比演算法（1967）求最可能狀態序列、Baum–Welch（EM 演算法, 1970）估參數——語音辨識、基因序列註解、金融體制轉換模型（regime switching）皆以此為骨幹。「看不見的狀態 + 看得見的證據」是機率建模深化的代表範式，也預告了 9.3 節貝氏方法中的隱變數思想。

場景五：連續時間與無窮狀態。轉移速率矩陣 \(Q\) （生成元）取代 \(P\) ， \(P(t) = e^{tQ}\) （矩陣指數，2.3 節場景五的半群）；生滅過程（出生率 \(\lambda_n\) 、死亡率 \(\mu_n\) ）涵蓋排隊論（M/M/1，Erlang–Kendall 1953）、流行病（SIR 的隨機版）、族群動態。狀態無窮時平穩分布可能不存在（如純生過程爆炸，Kolmogorov 1940 年代研究）——「爆炸」問題把鏈理論推向邊界，連通了 7 章的隨機分析。

名詞速查表（本節出現的核心術語）#

  • 馬可夫性：未來只依賴現在。
  • **轉移矩陣 \(P\) **： \(p_{ij}\) = 一步轉移機率； \(n\) 步 = \(P^n\) 。
  • Chapman–Kolmogorov 方程：路徑分解的矩陣乘法。
  • 平穩分布： \(\pi = \pi P\) ，長期停留比例。
  • 不可約 / 正常返 / 非週期：平穩分布唯一與收斂的三大條件。
  • 遍歷定理：時間平均幾乎必然收斂到 \(\pi_j\) （Markov 1906）。
  • Kac 遞迴公式： \(\pi_j = 1/\mathbb{E}[\text{返回時間}]\) 。
  • 細致平衡： \(\pi_i p_{ij} = \pi_j p_{ji}\) ，MCMC 的設計準則。
  • 譜隙：第二大特徵值決定混合速度。
  • 隱馬可夫模型：狀態隱藏、觀測發射的雙層鏈。

年表速查（本節涉及的關鍵年份）#

  • 1906：Markov 論文，相依序列的大數法則。
  • 1907：Ehrenfest 罐子模型。
  • 1909：Erlang 電話流量理論（排隊論先驅）。
  • 1913：Markov 分析《奧涅金》文本。
  • 1928：Chapman 方程。
  • 1936–39：Kolmogorov 連續時間馬可夫過程理論。
  • 1947：Kac 遞迴公式。
  • 1953：Metropolis 演算法。
  • 1967：維特比演算法。
  • 1970：Baum–Welch（EM）。
  • 1986：Aldous–Diaconis 洗牌與閾值現象。
  • 1998：PageRank。

深化問答三則#

問：馬可夫性在真實世界裡「成立」嗎？ 答：幾乎從不嚴格成立（天氣有季節記憶、用戶有長期偏好），但常常夠用：只要長程記憶對下一步的邊際影響微弱，鏈模型是高性價比的近似。更精緻的處理有兩路：擴大狀態（把 \(k\) 步歷史壓入狀態，代價是狀態爆炸）、或用 HMM/貝氏網路顯式建模隱藏記憶。建模的藝術在於「記憶的折現率」：馬可夫鏈是「遺忘得快」的數學。

問：為什麼「時間平均 = 平穩平均」如此重要？ 答：因為它是「觀測單一軌跡能否推斷系統」的合法性證書：統計力學只能觀測一個樣本盒、網站只能觀測一條用戶流——遍歷定理保證長期單軌觀測等價於對平穩分布的抽樣。沒有它，時間序列資料（經濟學、氣候、感測器）的統計推論全部失去根據。這是 Markov 1906 年論文真正的、超越論戰的價值。

問：洗牌「7 次」的結論對統計學有什麼啟示？ 答：它示範了「混合時間」的概念可以定量回答「系統多久忘記初始」：6 次後仍明顯不均勻、7 次後接近均勻——閾值現象（cutoff）。對統計的啟示：任何依賴馬可夫鏈的方法（MCMC）都必須面對「燒入期（burn-in）要多久」；Aldous–Diaconis 的理論把這個實務問題變成譜隙的計算。馬可夫鏈的「遺忘速度」於是成為計算統計的核心工程指標。

（本節完）