馬可夫過程

Posted on 08/06/2009 by ccjou

本文的閱讀等級：中級

馬可夫過程 (Markov process) 是一種隨機過程，這裡我們討論的是具有離散狀態的過程，也稱為馬可夫鏈 (Markov chain)。馬可夫鏈不僅是一個應用廣泛的模型分析工具，也是線性代數裡一些數值演算法的基礎。馬可夫鏈常以矩陣形式的差分方程描述，通過分析此問題可以了解動態過程如何由矩陣的特徵值和特徵向量規範。

Andrey Markov (1856-1922) From http://upload.wikimedia.org/wikipedia/commons/a/a8/Andrei_Markov.jpg

 
我們用一個人口生態學的例子來說明。如果台北市每年有 \frac{2}{10} 的人口移出至外縣市，而每年有 \frac{1}{10} 的外縣市人口遷入台北市，假設總人口數不變，我們想知道根據這個人口遷移模型，台北市人口和外縣市人口是否收斂至一比值？令 s_k 代表外縣市人口數，t_k 代表台北市人口數，k 為年份。第 k 年結束時，人口變化由下式決定：

\begin{aligned} s_{k+1}&=0.9s_k+0.2t_k\\ t_{k+1}&=0.1s_k+0.8t_k,\end{aligned}

或用簡潔的矩陣方程式表示

\begin{bmatrix} s_{k+1}\\ t_{k+1} \end{bmatrix}=\begin{bmatrix} 0.9 & 0.2\\ 0.1 & 0.8 \end{bmatrix}\begin{bmatrix} s_k\\ t_k \end{bmatrix}。

根據給定的問題性質可知對於任意 k，s_k+t_k 為常數，且 s_k 和 t_k 都不為負數。這兩個性質也反映在人口轉移矩陣 (transition matrix)，該矩陣的元為非負實數且每一行 (column) 的所有元之和等於 1。具有上述兩個性質的矩陣稱為馬可夫矩陣[1]。

markov-process

虛構的人口遷移模型

 
我們的問題是計算 s_k 與 t_k，k\to\infty。底下使用線性代數方法解差分方程，再檢視其解是否收斂至一個穩定狀態。對於一般差分方程式 \mathbf{u}_{k+1}=A\mathbf{u}_k，若 A 可對角化為 A=S\Lambda S^{-1}，則解可由下式得出

\mathbf{u}_k=A^{k}\mathbf{u}_0=S\Lambda^{k}S^{-1}\mathbf{u}_0，

其中 \mathbf{u}_0 是已知的初始值。此例，

A=\begin{bmatrix} 0.9&0.2\\ 0.1&0.8 \end{bmatrix}

的特徵值為 \lambda_1=1 和 \lambda_2=0.7，且 A 有相異的特徵值，故為可對角化，如下：

A=S\Lambda S^{-1}=\begin{bmatrix} 2/3 & 1/3\\ 1/3 & -1/3 \end{bmatrix} \begin{bmatrix} 1&0\\ 0&0.7 \end{bmatrix} \begin{bmatrix} 1&1\\ 1&-2 \end{bmatrix}。

代入解的公式，展開整理後可得到具有如 c_1\lambda_1^k\mathbf{x}_1+c_2\lambda_2^k\mathbf{x}_2 形式的解：

\mathbf{u}_k=\begin{bmatrix} s_k\\ t_k \end{bmatrix}=(s_0+t_0)\begin{bmatrix} 2/3\\ 1/3 \end{bmatrix}+(s_0-2t_0)(0.7)^k\begin{bmatrix} 1/3\\ -1/3 \end{bmatrix}。

當 k 增至無窮大時，(0.7)^k 趨於零，解將會逼近

\mathbf{u}_\infty=\begin{bmatrix} s_{\infty}\\ t_{\infty} \end{bmatrix}=(s_0+t_0)\begin{bmatrix} 2/3\\ 1/3 \end{bmatrix}。

不論最初人口分布為何 (但總不能沒半個人)，外縣市人口最終將收斂至總人口的 \frac{2}{3}，台北市人口則占總人口的 \frac{1}{3}，此狀態稱為穩態 (steady state)，參見下圖。注意，穩態滿足

\begin{bmatrix} 0.9&0.2\\ 0.1&0.8 \end{bmatrix}\begin{bmatrix} 2/3\\ 1/3 \end{bmatrix}=\begin{bmatrix} 2/3\\ 1/3 \end{bmatrix}。

以符號表示為 A\mathbf{u}_{\infty}=\mathbf{u}_{\infty}，穩態即為對應特徵值 \lambda_1=1 的特徵向量。

trajectory1

人口分布收斂圖

 
提問是求知的第一步。首先我們問：\lambda=1 是否總是馬可夫矩陣 A 的一個特徵值？或者說 A-I 不是可逆矩陣？因為 A-I 的每行各元之和為 1-1=0，故 A-I 所有列的加總為零列，A-I 包含線性相關的列，故 A-I 不是可逆矩陣，這確定馬可夫矩陣必定有特徵值 1。

 
第二個問題：除了 \lambda=1，馬可夫矩陣 A 的其他特徵值有何性質？考慮解的一般形式： \mathbf{u}_k=c_1\lambda_1^{k}\mathbf{x}_1+\cdots+c_n\lambda_n^{k}\mathbf{x}_n，可以確定 \vert\lambda\vert\le 1，否則 \mathbf{u}_k 將會發散至無窮大 (人口大爆炸)。

 
第三個問題：為何對應 \lambda=1 的特徵向量就是穩態？除了少數特例，譬如，A=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} 有特徵值 1 和 -1，意指每年台北市人和外縣市人像候鳥一樣彼此相互遷移，此情況不存在一個穩態。設 \lambda_i 按其絕對值大小排序，若 A 有特徵值 \lambda_1=1，其他 \vert\lambda_i\vert<1，則解將逼近 \mathbf{u}_k\rightarrow c_1\mathbf{x}_1=\mathbf{u}_{\infty}。

 
最後，我們將馬可夫矩陣 A 的重要性質整理如下 (部分證明相當複雜，在此從略)：

  1. 所有特徵值 \lambda_i 皆滿足 \vert\lambda_i\vert\le 1 (見“每週問題 October 17, 2011”)。
  2. \lambda_1=1 為一特徵值，對應的特徵向量 \mathbf{x}_1 的各元必不為負，此因 A\mathbf{x}_1=\mathbf{x}_1，\mathbf{x}_1 為此過程的一個穩態。
  3. 每一滿足 \vert\lambda_i\vert=1 的特徵值 \lambda_i 的代數重數等於幾何重數。
  4. 當 A 僅有一個絕對特徵值為 1，A^k\mathbf{u}_0 逼近特徵向量方向 \mathbf{x}_1。

註解
[1] 馬可夫矩陣區分為兩類：右馬可夫矩陣的每一列和等於 1，左馬可夫矩陣的每一行和等於 1。

This entry was posted in 機率統計 and tagged , , , , , . Bookmark the permalink.

1 Response to 馬可夫過程

  1. 蘇子翔 says:
    09/10/2018 at 3:25 pm

    特徵值 0.7哪裡來的 ?

    Reply

Leave a comment