Markov Chain
Markov Property
給定隨機變數數列 $\bs X = \{ X_0, X_1, \cdots, X_t, \cdots \}$，其中 $X_t$ 表示隨機變數在時間 $t$ 的狀態，令 $S$ 為 state space，是所有 $X_t$ 可能數值的集合；此變數可以是連續也可以是離散的。
Markov Property 描述的性質為「未來 (future) 的狀態只與現在 (present) 有關，與過去 (past) 無關」，即
$$ \begin{align*} P ( X_{t + 1} | X_t, X_{t - 1}, \cdots) = P (X_{t + 1} | X_{t}), \quad t = \contii \end{align*} $$其中未來、現在與過去可以這樣理解：
$$ \begin{align*} P ( \underset{\text{future}}{\underline{X_{t + 1}}} | \underset{\text{present}}{\underline{X_{t + 1}}}, \underset{\text{past}}{\underline{X_{t - 1}, \cdots}}) \end{align*} $$若隨機數列 $\bs X$ 帶有 markov property 則稱為 markov chain，並稱 $P (X_t | X_{t - 1})$ 為轉移分佈 (transition probability distribution)。
Discrete-Time Markov Chain
Discrete-Time Markov Chain 指的是時間是離散的，而非狀態空間 $S$ 是否為離散。考慮 $\bs X$ 定義在離散的狀態空間 $S$，使得 $P (X_t | X_{t - 1}) = \bs P$ 可以被矩陣表達，以 $\bs P (i, j)$ 表示時間 $t$ 由狀態 $i$ 經轉移後到狀態 $j$ 的機率，即
$$ \begin{align*} \bs P (i, j) = P (X_{t + 1} = j | X_t = i) \end{align*} $$稱其為轉移矩陣 (transition probability matrix)
Chapman - Kolmogorov Equations
定義完 $1$ 步的轉移機率，接著定義 $n$ 步的轉移機率，以 $\bs P^{(n)}$ 描述 $n$ 次轉移後機率，稱為 $n$ 階轉移機率 ($n$-step transition probabilities)
$$ \begin{align*} P^{(n)}(i, j) = P (X_{t + n} = j | X_{t} = i) \end{align*} $$其滿足幾個性質：
- $\bs P^{(2)} = \bs P \bs P$
- $\bs P^{(m + n)} = \bs P^{(m)} \bs P^{(n)}$
這項定理保障了 $n$ 階轉移能用基本的矩陣乘法達成，因此接著能用 $\bs P^n$ 簡寫 $\bs P^{(n)}$。其證明也頗為簡單，從 $n = 2$ 開始
$$ \begin{align*} \bs P^{(2)} (i, j) & = P (X_{t + 2} = j | X_t = i) \\ & = \sum_{k} P (X_{t + 2} = j, X_{t + 1} = k | X_t = i) \\ & = \sum_{k} P (X_{t + 2} = j | X_{t + 1} = k, X_t = i) P ( X_{t + 1} = k | X_t = i) \\ & = \sum_{k} P (X_{t + 2} = j | X_{t + 1} = k) P ( X_{t + 1} = k | X_t = i) \\ & = \sum_{k} \bs P (k, j) \bs P (i, k) \end{align*} $$等價於 $\bs P^2 (i, j) = \sum_k \bs P (i, k) \bs P (k, j)$，即為矩陣乘法，更廣泛的說
$$ \begin{align*} \bs P^{n + m} (i, j) = \sum_k \bs P^n (i, k) \bs P^m (k, j) \end{align*} $$範例
設 $\bs X$ 為天氣的轉移矩陣，$X_t = 1$ 表示第 $t$ 為晴天，$X_t = 2$ 表示為第 $t$ 天為雨天；並且晴天的隔天有 0.9 的機率為晴天，0.1 的機率為雨天，雨天的隔天有 0.5 的機率為晴天，0.5 的機率為雨天，則
$$ \begin{align*} \bs P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix} \end{align*} $$若起始狀態 $x^{(0)} = (1 \ 0)^T$ 為晴天，則 $t = 2$ 的天氣分佈為
$$ \begin{align*} x^{(2)} = x^{(0)} \bs P^2 = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}^2 = \begin{pmatrix} 0.86 \\ 0.14 \end{pmatrix} \end{align*} $$即 0.86 機率為晴天，0.14 機率為雨天
狀態分類
接著討論各種狀態有什麼性質，這是為了後續要討論哪些狀態是穩定之類的所需的步驟。首先定義狀態 $j$ 是能被狀態 $i$ 通訊的 (accessible)，即存在 $n \geq 0$ 使得 $P^n (i, j) > 0$，寫作 $i \to j$。
若兩個狀態能互通，即 $i \to j$ 與 $j \to i$，則寫作 $i \leftrightarrow j$，稱其為交流的 (communicate) 並滿足：
- 反身性：$i \leftrightarrow i$。
- 對稱性：$i \leftrightarrow j$ 則 $j \leftrightarrow i$。
- 遞移性：$i \leftrightarrow j$ 且 $j \leftrightarrow k$，則 $i \leftrightarrow k$。
任意兩個交流的狀態稱其在同一個類 class，且任兩個 class 若不是相同則是互斥 (disjoint)。若某馬可夫鏈只有一個 class，則稱其為 irreducible。
最後一個考慮的性質是狀態是否具有「復發性」，或者說從狀態 $i$ 出發後能再回來狀態 $i$ 的機率是否為 $1$，其最簡單的等價定義為：
- 若 $\sum_{n = 1}^{\infty} P^n (i, i) = \infty$，則狀態 $i$ 為復發的 (recurrent)。
- 若 $\sum_{n = 1}^{\infty} P^n (i, i) < \infty$，則狀態 $i$ 為瞬間的 (transient)。
復發 (recurrent) 與瞬間 (transient) 的都是類 (class) 性質，例如狀態 $i$ 是復發的且 $i \leftrightarrow j$，則 $j$ 也是復發的；換句話說，一個類的元素只能同是復發或瞬間的。
另一方面，在一個馬可夫鏈中不可能所有狀態都是瞬間的；因此會有一個驚人結論「有限 (finite) 狀態且 irreducible 的馬可夫鏈，其所有狀態都是復發的」，這性質保障了後續的穩定狀態是否有唯一解。
Stationary
若機率轉移後與原始機率相同，則稱此分佈為 $\pi = (\contiai{\pi})^T$ 為穩定狀態 (stationary)，即
$$ \begin{align*} \pi = \bs P \pi \end{align*} $$對一個 irreducible 且 positive recurrent 的馬可夫鏈，$\pi$ 為 stationary 的充分與必要條件為有 3 條，能透過此條件找出穩定解
- $\pi_j = \sum_i \pi_i \bs P (i, j) $ 對任意 $i$
- $\pi_i \geq 0$, 對任意 $i$
- $\sum_{i} \pi = 1$
等價於
$$ \begin{align*} & \pi \in \text{Null} (\bs P^T - I) \\ & \norm{\pi}_1 = 1 \end{align*} $$其中 $\text{Null}$ 參見 Kernel (linear algebra)，也能解出 $\pi$ 存在唯一解的條件。若無解，則此馬可夫鏈為瞬間的或 null recurrent。
稱 $m_j = 1 / \pi_i$ 為狀態的 $i$ 的復發週期，即從狀態 $i$ 出發再回到狀態 $i$ 所需步數的期望值。
Limiting Probabilities
最後討論的性質是，$X$ 有多高比例的時間會待在狀態 $j$，對 irreducible 且 aperiodic 的馬可夫鏈來說，此問題與起始狀態無關，且解為
$$ \begin{align*} \lim_{n \to \infty} P (X_n = j) = \pi_j \end{align*} $$範例
給定
$$ \begin{align*} \bs P = \begin{pmatrix} 1/2 & 1/2 & 1/4 \\ 1/4 & 0 & 1/4 \\ 1/4 & 1/2 & 1/2 \end{pmatrix} \end{align*} $$的 stationary 分佈 $\pi = (\pi_1, \pi_2, \pi_3)^T$ 滿足
$$ \begin{align*} & \pi_1 = \frac{1}{2} \pi_1 + \frac{1}{2} \pi_2 + \frac{1}{4} \pi_3 \\ & \pi_2 = \frac{1}{4} \pi_1 + \frac{1}{4} \pi_3 \\ & \pi_3 = \frac{1}{4} \pi_1 + \frac{1}{2} \pi_2 + \frac{1}{2} \pi_3 \\ & \pi_1 + \pi_2 + \pi_3 = 0 \\ & \pi_1, \pi_2, \pi_3 \geq 0 \end{align*} $$解出唯一解
$$ \begin{align*} \pi = \begin{pmatrix} 2/5 & 1/5 & 2/5 \end{pmatrix}^T \end{align*} $$但並非所有 stationary 分佈均有唯一解，例如
$$ \begin{align*} \bs P = \begin{pmatrix} 1 & 1/3 & 0 \\ 0 & 1/3 & 0 \\ 0 & 1/3 & 1 \end{pmatrix}^T \end{align*} $$有兩解
$$ \begin{align*} \pi = \begin{pmatrix} 3/4 & 0 & 1/4 \end{pmatrix}^T \quad \text{and} \quad \pi = \begin{pmatrix} 2/3 & 0 & 1/3 \end{pmatrix}^T \end{align*} $$Continuous-Time Markov Chain
Continuous-Time Markov Chain 指的是時間是連續的，考慮 continuous-time Markov chain $X = \{ X_0, X_1, \cdots, X_t, \cdots \}$ 定義在連續的狀態空間 $S$，定義 transition probability distribution 從狀態 $x \in S$ 轉移至狀態 $A \in S$ 的機率為
$$ \begin{align*} P (x, A) = P (X_t = A | X_{t - 1} = x) = \int_A p (x, y) dy \end{align*} $$其中 $p (x, y)$ 為 $(X_{t - 1}, X_{t}) = (x, y)$ 的 pdf，且滿足
- $p (x, y) \geq 0$ 與
- $P (x, S) = \int_S p (x, y) dy = 1$
定義 $\pi (x)$ 定義在 $S$ 上的分佈，若此分佈對任意 $y \in S$ 滿足
$$ \begin{align*} \pi (y) = \int_{S} p (x, y) \pi (x) dx \end{align*} $$則稱此分佈為 stationary distribution，等價於
$$ \begin{align*} \pi (A) = \int_{S} p (x, A) \pi (x) dx \end{align*} $$或更簡寫的
$$ \begin{align*} \pi = \bs P \pi \end{align*} $$Markov Chain 性質
這邊介紹 discrete-time Markov chain 的性質，這些性質皆能推論至 continuous-time Markov chain。本段的目標為找出唯一的 stationary distribution 解條件。
不可約分的 Irreducible
給定 Markov chain $X = \{X_0, X_1, \cdots, X_t, \cdots \}$ 與狀態空間 $S$，對任意狀態 $i, j \in S$，如果均存在 $t > 0$ 使得
$$ \begin{align*} P (X_t = i | X_0 = j) > 0 \end{align*} $$則稱此 Markov chain 為 Irreducible，即無論起始狀態為何，總能在足夠長的時間觸及所有狀態；反之則為 reducible
例如下述矩陣為 reducible
$$ \begin{align*} \begin{pmatrix} 0 & 1/2 & 0 \\ 1 & 0 & 0 \\ 0 & 1/2 & 1 \end{pmatrix} \end{align*} $$
非週期 Aperiodic
給定 Markov chain $X = \{X_0, X_1, \cdots, X_t, \cdots \}$ 與狀態空間 $S$，對任意狀態 $i \in S$，考慮起始狀態 $i$ 的再次回到自身狀態的時間長度
$$ \begin{align*} \{ t : P (X_t = i | X_0 = i) > 0 \} \end{align*} $$若此集合的最小公因數 (gcd) 為 1，則稱此 Markov chain 為非週期的 (Aperiodic)，反之則為週期性的 (periodic)。
例如下述矩陣為 periodic，且週期為 3
$$ \begin{align*} \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \end{align*} $$
Finite State Markov Chain Stationary
Irreducible 與 aperiodic 的有限狀態 (finite state) Markov chains 有唯一 stationary distribution
Positive Recurrent
給定 Markov chain $X = \{X_0, X_1, \cdots, X_t, \cdots \}$ 與狀態空間 $S$，對任意狀態 $i, j \in S$，定義起始狀態為 $j$，直至時間 $t$ 才首次抵達狀態 $i$，即
$$ \begin{align*} p_{ij}^t = P (X_t = i, X_s \ne i, s = \conti{t - 1} | X_0 = j) \end{align*} $$若 $\lim_{t \to \infty} p_{ij}^t > 0$，對任意 $i, j$，則稱此 Markov chain 為 Positive Recurrent
下述矩陣在 $p > q$ 時為 positive recurrent；在 $p \leq q$ 時則非 positive recurrent
$$ \begin{align*} \begin{pmatrix} p & p & 0 & 0 & \cdots \\ q & 0 & p & 0 & \cdots \\ 0 & q & 0 & p & \cdots \\ 0 & 0 & p & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \end{align*} $$
Ergodic Theorem
給定 Markov chain $X = \{X_0, X_1, \cdots, X_t, \cdots \}$ 與狀態空間 $S$，若 $X$ 為 irreducible、aperiodic 與 positive recurrent，則此 Markov chain 存在唯一 stationary distribution $\pi = (\contiai{\pi})^T$，且
$$ \begin{align*} \lim_{t \to \infty} P (X_t = i | X_0 = j) = \pi_i, \quad i = \contii; j = \contii \end{align*} $$定義 $f (X)$ 是個定義在 S 上的函數，且 $E_{\pi} [|f(X)|] < \infty$，則
$$ \begin{align*} \hat E [f(x)] \to E_\pi [f(x)] \quad \text{as} \quad t \to \infty \end{align*} $$almost surely，其中
$$ \begin{align*} \hat E [f(x)] = \frac{1}{t} \sum_{i = 1}^{t} f (x_i) \end{align*} $$這定理所表達的是，一個 markov chain 滿足 3 個條件後，在時間趨於餘限大時，狀態分佈 趨於 stationary distribution，且樣本平均趨於真實平均。
真實應用下，我們並不知道何時會收斂至 stationary distribution，一般會選取非常大的數字 $m$，考慮在 $m + 1$ 至 $n$ 作為採樣，並以 ergodic mean 取代樣本平均
$$ \begin{align*} \hat E f = \frac{1}{n - m} \sum_{i = m + 1}^{n} f (x_i) \end{align*} $$Reversible Markov Chain
給定 Markov chain $X = \{X_0, X_1, \cdots, X_t, \cdots \}$、狀態空間 $S$ 與 transition probability matrix $\bs P$，若存在狀態分佈 $\pi = (\contiai{\pi})^T$ 對任意 $i, j \in S$ 與任意 $t$ 滿足 detailed balance equation
$$ \begin{align*} P (X_t = i | X_{t - 1} = j) \pi_j = P (X_{t - 1} = j | X_t = i) \pi_i \end{align*} $$或簡寫成
$$ \begin{align*} \bs P_{ij} \pi_j = \bs P_{ij} \pi_i \end{align*} $$則稱此 Markov chain 為 reversible。若狀態分佈 $pi$ 滿足 detailed balance equation，則此 $\pi$ 也為 stationary distribution
下述矩陣為 reversible
$$ \begin{align*} \begin{pmatrix} 1/2 & 1/2 & 1/4 \\ 1/4 & 0 & 1/4 \\ 1/4 & 1/2 & 1/2 \end{pmatrix} \end{align*} $$
參考資料
- LI, Hang. Machine Learning Methods. Springer Nature, 2023.
- Lange, Kenneth, J. Chambers, and W. Eddy. Numerical analysis for statisticians. Vol. 1. New York: springer, 2010.