多步轉移與查普曼-柯爾莫哥洛夫方程

從一步到兩步：對中間點求和

在第 1 篇裡你認識了[[transition-matrix|轉移矩陣]] P，它的元素 P(i, j) 是一步之內從狀態 i 跳到狀態 j 的機率。那一個數字回答了「下一步去哪」。但幾乎所有關於馬可夫鏈的實際問題，都是關於較長期的：一個桌遊問你的棋子三回合後會在哪，一個天氣模型問一星期後下雨的機率。所以我們想要一個新的量，叫兩步轉移機率，寫作 P^(2)(i, j)：從 i 出發，恰好兩步之後落在 j 的機率——不管中間做了什麼。

解開一切的那個念頭就在這裡。要在兩步內從 i 到 j，這條鏈在中途點必定會經過某個中間狀態 k——而在任何一趟旅程中恰好只發生一個這樣的 k。這些中間狀態互斥且窮盡，所以由全機率定律，我們把每一條路線 i -> k -> j 的機率全部加起來。一條這樣的路線的機率是 P(i, k) 乘以 P(k, j)：第一個因子是第一跳的機率，第二個是第二跳的機率。關鍵在於，我們之所以能把它們相乘，是因為馬可夫性質說一旦你落在 k，過去的 i 就被遺忘了——第二跳只取決於 k。

P^(2)(i, j) = sum over all k of  P(i, k) * P(k, j)

             first hop  ---^         ^--- second hop
             i -> k                  k -> j

兩步機率是對每一個可能的中間狀態 k 的求和——把每一條路線 i -> k -> j 都算進去。

那個求和其實是偽裝的矩陣乘法

仔細看那條公式：「對 k 求和，把 P(i, k) 乘以 P(k, j)」。如果你在線性代數那幾階見過矩陣乘法，你的心跳應該要加快了——那正是 P 與自身相乘後第 (i, j) 個元素的配方。換句話說，兩步機率構成的矩陣就只是 P^2 = P 乘以 P。我們根本不必發明新的運算；你早已會的代數免費把它交給了我們。這就是讓馬可夫鏈如此好算的那個小奇蹟。

這個模式毫不費力地一直延續下去。要在 n 步內從 i 到 j，就對「前 n - 1 步之後（或等價地，第一步之後）你在哪」做條件並相加。收集所有 n 步機率的那個矩陣，就是[[n-step-transition-matrix|n 步轉移矩陣]]，而它不過就是 P 的 n 次方：矩陣 P^(n) 等於 P^n。想知道七天後下雨的機率嗎？把 P 升到七次方，再讀出今天天氣對應的那一列。一趟漫長隨機旅程的幾何，被壓縮成了一個俐落的運算：把一個小矩陣反覆相乘。

查普曼-柯爾莫哥洛夫方程：在任意一點切開旅程

兩步的論證只是一個更普遍真理的特例，而它值得用全名稱呼。[[chapman-kolmogorov-equations|查普曼-柯爾莫哥洛夫方程]]說，你可以在任何你喜歡的中間時刻把一趟 (m + n) 步的旅程切開。挑一個切點：鏈在那一刻必定處於某個狀態 k，所以 P^(m+n)(i, j) = 對 k 求和，把 P^(m)(i, k) 乘以 P^(n)(k, j)。用矩陣形式來寫，這就是那個簡單到幾乎令人不好意思的陳述 P^(m+n) = P^m 乘以 P^n——矩陣的指數律。兩步用的是 m = n = 1 這個切點；這條方程讓你可以在任何地方切。

為什麼「能在任何地方切」這件事重要？因為它是本階段後面每一個結果背後的正式引擎。當我們問一條鏈是否會安定到一個長期的平衡，我們研究的是 n 變大時 P^n 的行為，而查普曼-柯爾莫哥洛夫方程正是讓我們能把 P^(2n) 與 P^n 連起來的工具。當我們在下一篇把狀態分類為常返或暫態，判準是看那些元素 P^(n)(i, i) 加起來是否為無限大——這是只有 n 步機率才提得出的問題。這條方程不是用一次就丟的把戲；它是整個學科書寫所用的文法。

鏈究竟在哪裡：分布，而非單一點

到目前為止我們固定了一個起始狀態 i。但通常我們並不確定鏈從哪裡開始——我們只有一個[[initial-distribution|初始分布]]，一個列向量 pi_0，它的各個元素是從每個狀態出發的機率，且必須加總為 1。自然的問題變成：n 步之後的分布是什麼？答案又是同一套代數的一行。把起始列向量在右邊乘上 P，每走一步就乘一次：n 步之後的分布是 pi_n = pi_0 乘以 P^n。每一次乘上 P，就把整朵機率雲往時間前方推進一格。

把你對鏈所在位置的當前信念寫成一個列向量 pi，其元素皆非負且總和為 1。
計算 pi 乘以 P 來前進一步；結果仍是一個合法的分布，因為 P 的每一列都加總為 1，機率因此守恆。
重複以抵達任意時間視野：pi 乘以 P 再乘以 P，依此類推——等價於用 pi_0 乘以 P^n 得到 n 步分布。
要讀出時刻 n 在某個特定狀態的機率，就取出 pi_n 的那個元素；要讀「i 到 j」，則直接讀 P^n 的第 (i, j) 個元素。

這個向量觀點，也是看清接下來會發生什麼最清晰的方式。對許多行為良好的鏈，序列 pi_0、pi_1、pi_2、... 會停止移動：它安定到一個固定的列向量 pi，滿足 pi P = pi，也就是[[limiting-distribution|極限分布]]。線索其實早就藏在我們的演算範例裡——不斷把那個天氣矩陣相乘，下雨機率就會悄悄趨向一個穩定的值，不管今天的預報是什麼。第 4 篇會把這個收斂講精確；現在只要留意：把 P 升冪，正是揭露長期行為的那個動作。

誠實的提醒：升冪能告訴你什麼、不能告訴你什麼

有幾個值得點名的陷阱。第一，P^(n)(i, j) 是「在時刻 n 正好位於 j」的機率，而不是「到時刻 n 為止曾經造訪過 j」的機率——這是兩個不同的問題，把它們搞混是個經典的失誤。第二，P^n 的元素仍是貨真價實的機率，但單一個矩陣元素不是一條路徑：從 i 到 j 的許多條不同路線，在它裡面被加在一起，而這條方程是刻意丟掉了「走的是哪一條」這個資訊。第三，不要期待 P^n 對每一條鏈都收斂。一條嚴格在兩個狀態間交替的鏈，其 P^2 等於單位矩陣，所以它的冪會永遠來回振盪、絕不安定——這個現象叫週期性，正是下一篇的主題。

最後一個之後會有回報的連結。一條鏈之所以能遺忘起點並收斂，是因為它的狀態彼此能對話——如果從任何狀態最終都能到達任何其他狀態，這條鏈就能自由地把機率攪勻。這個性質，封裝為[[communicating-classes|互通類]]與不可約性，正是保證有單一極限分布、而非好幾個彼此不連通的分布的關鍵。而查普曼-柯爾莫哥洛夫方程提供了這套分類所倚靠的 n 步可達性：狀態 j 從 i 可達，恰恰就是當 P^(n)(i, j) 對某個 n 為正的時候。因此多步轉移不只是計算上的方便——它正是描述一條鏈結構所用的語言本身。