馬可夫鏈

馬可夫鏈maa5 ho2 fu1 lin2（英文：Markov chain）係概率論同統計學等領域上常用嘅一種隨機模型，個名嚟自創始呢個概念嘅 19 世紀俄羅斯數學家安德里·馬可夫（Andrey Markov）。簡單講，一條馬可夫鏈會將分析緊嘅系統想像成一嚿帶有隨機性嘅數學物體，即係會將研究緊嘅系統諗做由以下呢兩樣嘢構成^[1]：

• 若干個可能嘅狀態（state），
• 每個可能狀態 ${\displaystyle x_{i}}$ 都會褦住柞數 ${\displaystyle \{p_{0},p_{1},p_{2}...\}}$ 嚟表示「世界由 ${\displaystyle x_{i}}$ 呢個狀態變成另一個狀態嘅機會率」，

附圖 1；一條簡單嘅馬可夫鏈個有向圖圖解；條鏈有兩個可能狀態－${\displaystyle {\text{E}}}$ 同 ${\displaystyle {\text{A}}}$。

例如幅附圖 1 入面嗰條簡單嘅馬可夫鏈就係噉：條鏈有 ${\displaystyle {\text{E}}}$ 同 ${\displaystyle {\text{A}}}$ 兩個可能狀態；如果家陣世界嘅狀態係 ${\displaystyle {\text{E}}}$，下一刻狀態變成 ${\displaystyle {\text{A}}}$ 嘅機率係 70% / 0.7，狀態繼續維持係 ${\displaystyle {\text{E}}}$ 嘅機率係 30% / 0.3；如果家陣世界嘅狀態係 ${\displaystyle {\text{A}}}$，下一刻狀態變成 ${\displaystyle {\text{E}}}$ 嘅機率係 40% / 0.4，狀態繼續係 ${\displaystyle {\text{A}}}$ 嘅機率係 60% / 0.6。除此之外，馬可夫鏈仲可以按好多特性分做進階嘅類別，例如隱馬可夫模型就係一種特殊嘅馬可夫鏈，指條鏈當中有一部份嘅狀態係研究者觀察唔到嘅（隱藏），研究者要齋靠觀察淨低嗰啲－觀察得到嘅－狀態嚟對啲隱藏狀態作出判斷^[2]。

喺好多自然科學同工程學領域裏面，馬可夫鏈都係一種有用嘅分析工具，可以攞嚟模擬研究緊嘅現象^[3]，例如人工智能（AI）上嘅研究就好興教啲人工智能程式將世界抽象化噉諗做一條條嘅馬可夫鏈，用過往所得嘅數據建立心目中嘅馬可夫鏈模型－「根據過去經驗，而家狀態係 ${\displaystyle {\text{E}}}$ 下一刻變 ${\displaystyle {\text{A}}}$ 嘅機率係咁多咁多」，而人工智能程式跟住就會按「跟住落嚟世界變成呢個狀態嘅機率係幾多」等嘅資訊嚟做決策^[4][5]。

定義

附圖 2；馬可夫鏈轉移矩陣嘅示意圖；表示返上高幅有向圖入面嗰啲轉移（${\displaystyle K=2}$）。

内文：概率論同馬可夫性質

睇埋：圖論

喺定義上，一條基本嘅馬可夫鏈係具有以下呢三大特性嘅隨機過程^{[註 1][6]}：

1. 有若干個可能狀態（state）。技術性啲噉講，即係話狀態 ${\displaystyle X_{a}}$ 嘅可能數值組成 ${\displaystyle \left\{1,2,\ldots ,k\right\}}$ 噉嘅一個狀態空間（state space；指一個系統啲可能狀態冚唪唥包埋一齊嘅一個集）^[7][8]－
   • 呢個狀態空間係一個可數集，${\displaystyle \forall a,a\in \mathbb {N} }$（${\displaystyle a}$ 所有可能數值都係自然數），而且
   • 條馬可夫鏈仲要有個概率分佈表示每個狀態有幾大概率會係初始狀態，${\displaystyle \Pr(X_{0}=s)=q_{0}(s)}$ 。
2. 有若干條規則指明狀態之間嘅轉移概率（transition probability）；通常嚟講，馬可夫鏈啲狀態轉移會由時間決定，所以轉移概率可以寫做 ${\displaystyle A_{ij}^{(n+1)}}$ 噉嘅樣，當中 ${\displaystyle n}$ 係指時間點，即係^[9]：

   ${\displaystyle \Pr(X_{n+1}=j|X_{n}=i)=A_{ij}^{(n+1)}}$

   • 用日常用語講嘅話，上面呢條式嘅意思如下：${\displaystyle A_{ij}^{(n+1)}}$ 嘅數值反映「如果已知呢一刻時間嘅狀態（${\displaystyle X_{n}}$）係 ${\displaystyle i}$，噉下一刻時間嘅狀態（${\displaystyle X_{n+1}}$）係 ${\displaystyle j}$」嘅概率。
3. 滿足到馬可夫性質（Markov property），噉講意思即係話個系統冇「記憶」呢種功能，「下一刻狀態會變乜」完全淨係取決於而家呢刻嘅狀態，而家呢刻打前嗰啲時間點嘅狀態唔會影響下一刻嘅狀態係乜^{[註 2]}。技術啲噉講嘅話，馬可夫性質可以用以下噉嘅形式表達：

   ${\displaystyle \forall n,\Pr(X_{n}|X_{1},\ldots ,X_{n-1})=\Pr(X_{n}|X_{n-1})\,}$

   • 當中 ${\displaystyle \forall n}$ 意係話「無論 ${\displaystyle n}$ 處於邊個可能數值都好，條式都會成立」^[10]。

一條馬可夫鏈可以用最少兩種方法嚟表示：一方面，馬可夫鏈可以畫做好似附圖 1 噉嘅有向圖，即係話幅圖有若干個頂點（喺附圖 1 當中，頂點係嗰啲有字母喺裏面嘅圓圈），頂點之間有啲箭咀表示頂點之間可以點樣變化，而每個箭咀都褦住個喺 0 同 1 之間嘅數，表示個箭咀指定嘅嗰種狀態轉移發生嘅概率，當中可以有頂點係有箭咀指住自己嘅，表示嗰啲頂點有可能轉移返去自己嗰度；另一方面，馬可夫鏈又可以寫做好似附圖 2 噉嘅轉移矩陣（transition matrix），即係話畫返個 ${\displaystyle K\times K}$ 嘅矩陣 ${\displaystyle \mathbf {A} ^{(1)},\dots \mathbf {A} ^{(N-1)}}$ 俾條 ${\displaystyle X_{1},\dots X_{N}}$ 鏈，當中 ${\displaystyle K}$ 係啲可能狀態嘅數量，矩陣打戙行表示「而家啲狀態」，打橫行表示「跟住落嚟啲狀態」，而啲矩陣嘅每個元素都係一個 ${\displaystyle A_{ij}^{(n+1)}}$。技術性啲噉講，將馬可夫鏈寫做矩陣令到研究者有得用線性代數嚟做馬可夫鏈相關嘅運算。

馬可夫鏈嘅概念源自廿世紀初。早喺廿世紀前經已有人提出過類似連續時間馬可夫鏈嘅諗頭^[11][12]，而俄羅斯數學家安德里·馬可夫（Andrey Markov；馬可夫鏈個名就係由佢嗰度嚟嘅）為咗研究有關隨機過程嘅問題，喺 1906 年嗰度發表論文提出咗「將個系統想像成有若干個會狀態，狀態之間會隨機噉轉移」嘅諗頭，正式開展咗數學上對馬可夫鏈嘅研究^[13][14]。

特性

想像一個簡單嘅情況：家陣有個人，佢每日會由三樣嘢食當中隨機噉揀一樣做嗰日嘅早餐－

• 提子（圖中嘅 grapes）、
• 生菜（圖中嘅 lettuce）、
• 芝士（圖中嘅 cheese）、

而佢嘅決策方式成一條馬可夫鏈，例如如果佢今日揀咗早餐食提子，佢有 10% 機會聽日早餐又食提子，有 50% 機會聽日早餐食生菜，有 40% 機會聽日早餐食芝士，淨低嗰啲情況如圖所示。呢條馬可夫鏈有三個狀態（${\displaystyle K=3}$）；條鏈不可約而且常返（啲狀態全部都係常返嘅）。

睇埋：隨機過程同有限狀態機

馬可夫鏈可以具有以下呢啲數學特性^[6][15]：

• 聯合概率分佈：攞一條馬可夫鏈，有 ${\displaystyle N}$ 個觀察到嘅值，條鏈啲狀態嘅聯合概率分佈可以表示成^{[註 3][16]}：

  ${\displaystyle \Pr(X_{1}=x_{1},\ldots X_{N}=x_{N})=\Pr(X_{1}=x_{1})\prod _{n=2}^{N}\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1})}$

  • 用日常用語講嘅話，想像家陣時間消逝，個系統經歷咗一連串 ${\displaystyle N}$ 個狀態位（${\displaystyle X_{1},X_{2},X_{3}...X_{N}}$），每個位嘅狀態係 ${\displaystyle \{x_{1},x_{2},x_{3}...x_{N}\}}$。係噉「會出一串噉嘅狀態」嘅概率，等如初始個狀態嘅概率一路乘上啲條件轉移概率；每轉一吓乘一次，所以連乘 ${\displaystyle N-1}$ 咁多次。
• 不可約性（irreducibility）：簡單噉講，即係話每個狀態都有可能喺有限步數內轉移去任何一個其他可能狀態嗰度。定義上，不可約性即係話想像有條鏈 ${\displaystyle (X_{t})_{t\geq 0}}$，

  ${\displaystyle \forall i,j}$（是但搵兩個狀態 ${\displaystyle i}$ 同 ${\displaystyle j}$），

  ${\displaystyle \exists t>0}$（都會有個數值 ${\displaystyle t}$，${\displaystyle t>0}$，而且...）有個概率 ${\displaystyle \Pr _{ij}(t)>0}$ 俾某條轉移路徑由 ${\displaystyle i}$ 去 ${\displaystyle j}$ 嘅。

• 週期（period）：想像有條馬可夫鏈其中有個狀態 ${\displaystyle x}$，如果話「${\displaystyle x}$ 嘅週期係 ${\displaystyle k}$ 咁多」，意思即係話一旦離開咗 ${\displaystyle x}$，要返去 ${\displaystyle x}$ 需要經過嘅時間長度 ${\displaystyle l_{i}}$ 實會係 ${\displaystyle k}$ 嘅倍數（${\displaystyle \forall l_{i},l_{i}=mk}$，當中 ${\displaystyle m}$ 係個整數）；如果 ${\displaystyle k=1}$，噉狀態 ${\displaystyle x}$ 就算係冇週期性嘅（aperiodic）。

... 等等。

即逝常返

睇埋：環 (圖論)

即逝性（transience）同常返性（recurrence）係用嚟描述馬可夫鏈嘅狀態嘅兩個特性。家吓設返回時間 ${\displaystyle \tau _{ii}}$，${\displaystyle \tau _{ii}}$ 表示「離開咗狀態 ${\displaystyle i}$ 之後，最少需要幾耐時間（過咗幾多步）先會返返 ${\displaystyle i}$ 狀態」；攞式嚟表示即係：

${\displaystyle \tau _{ii}=\min\{t>0:X_{t}=i|X_{0}=i\}}$

即逝性同常返性嘅定義如下：

• 如果有個狀態 ${\displaystyle i}$，一旦離開咗個狀態，就有機會永遠都唔再返去嗰個狀態嘅－${\displaystyle \Pr(\tau _{ii}=\infty )>0}$，噉呢個狀態就算係即逝嘅；
• 相反嚟講，如果有個狀態係一旦離開咗最後實會返去一次嘅－${\displaystyle \Pr(\tau _{ii}<\infty )=1}$（即係話個狀態唔係即逝嘅），就算平均嚟睇係要無限時間都好，噉呢個狀態都算係常返嘅。

常返性又有得再細分做正常返（positive recurrence）同零常返（null recurrence）：設平均返回時間 ${\displaystyle \mathbb {E} [\tau _{ii}]}$（即係 ${\displaystyle \tau _{ii}}$ 嘅期望值）^[17]，對於狀態 ${\displaystyle i}$ 嚟講：

• ${\displaystyle \mathbb {E} [\tau _{ii}]<\infty }$，即係個平均返回時間 ${\displaystyle \mathbb {E} [\tau _{ii}]}$ 係一個有限值，噉個狀態 ${\displaystyle i}$ 係「正常返嘅」；
• ${\displaystyle \mathbb {E} [\tau _{ii}]=\infty }$，即係個平均返回時間 ${\displaystyle \mathbb {E} [\tau _{ii}]}$ 係無限大（而當中噻次個別可以係有限值），噉個狀態 ${\displaystyle i}$ 係「零常返嘅」。

呢兩個特性亦都可以攞嚟形容一條馬可夫鏈：若果有條馬可夫鏈啲狀態冚唪唥都係常返嘅，噉條鏈就可以叫做常返嘅鏈；同一道理，如果條鏈啲狀態冚唪唥都係正常返嘅，噉條鏈可以叫做正常返嘅鏈^[6][15]。

靜止分佈

睇埋：特徵值

靜止分佈（stationary distribution）係馬可夫鏈研究上嘅一個重要概念：假想有個概率分佈 ${\displaystyle \pi }$ 基於狀態空間 ${\displaystyle X=\{x_{0},x_{1},x_{2}...\}}$－簡單講嘅話，即係 ${\displaystyle \pi }$ 表示緊「响每個時間點 ${\displaystyle n}$，每個狀態有幾大概率係條鏈身處嘅狀態」；如果話 ${\displaystyle \pi }$ 係一個靜止分佈，意思即係話以下條式成立：

${\displaystyle \pi (x')=\sum _{x\in X}\pi (x)\Pr(x,x'),\forall x'\in X}$，

簡化噉講嘅話，

• ${\displaystyle \pi (x')}$ 係指「而家呢個時間點處於 ${\displaystyle x'}$ 嘅概率」；
• ${\displaystyle \sum _{x\in X}\pi (x)\Pr(x,x')}$ 係指「跟住嗰個時間點處於 ${\displaystyle x'}$ 嘅概率」；

喺呢種情況下，條馬可夫鏈會「靜止」－雖然狀態係有可能變化，但成條鏈都唔會隨時間而演變，無論時間過咗幾耐，每個可能狀態成為條鏈嘅現時狀態嘅概率都唔會變^[6]。

向量表示

如果用向量同矩陣嚟想像嘅話，一個靜止分佈會係一個向量 ${\displaystyle \Phi }$，而以下呢條式成立^[18][19]：

${\displaystyle \Phi {\text{P}}=\Phi }$

當中 ${\displaystyle {\text{P}}}$ 係條馬可夫鏈嘅轉移矩陣^[20]。想像家陣有條三個狀態（${\displaystyle K=3}$）嘅馬可夫鏈，設個向量 ${\displaystyle \phi =[\phi _{1},\phi _{2},\phi _{3}]}$ 做一個分佈嚟表達條鏈嘅狀態（嗰三個數分別表示條鏈處於每個狀態嘅概率），又設時間點 ${\displaystyle =0}$ 而條鏈家陣處於第一個狀態，${\displaystyle \phi =[1,0,0]}$，跟住再計^{[註 4]}

${\displaystyle \phi {\text{P}}}$

例如設

${\displaystyle {\text{P}}={\begin{bmatrix}0.6&0.1&0.3\\0.1&0.7&0.2\\0.2&0.2&0.6\end{bmatrix}}}$

噉 ${\displaystyle \phi {\text{P}}}$ 得出嘅新向量（新 ${\displaystyle \phi }$）如下：

${\displaystyle \phi _{1}=0.6\phi _{1}+0.1\phi _{2}+0.2\phi _{3}}$

${\displaystyle \phi _{2}=0.1\phi _{1}+0.7\phi _{2}+0.2\phi _{3}}$

${\displaystyle \phi _{3}=0.3\phi _{1}+0.2\phi _{2}+0.6\phi _{3}}$

乘多幾次之後，${\displaystyle \phi }$ 會慢慢噉變，例如變成 ${\displaystyle [0.2759,0.3448,0.3793]}$，而嗰三個數分別反映「根據已有嘅經驗，每個狀態跟住落嚟發生嘅可能概率」；做上述嘅乘法做咗好多次之後，就會攞到個最終向量 ${\displaystyle \phi _{f}}$，而且

${\displaystyle \phi _{f}{\text{P}}=\phi _{f}}$

呢個向量就反映咗條馬可夫鏈嘅靜止分佈^[20]。可以睇埋特徵值（eigenvalue）嘅概念。

建立方法

一個兩變數嘅聯合概率分佈

睇埋：統計模型、時間序列、機械學習同蒙地卡羅方法

馬可夫鏈喺科學上相當有用：想像有位科學家，佢將研究緊嘅系統抽象化噉諗做一條馬可夫鏈；喺呢個過程當中，研究者會用演算法嚟建立一條馬可夫鏈（簡單講即係用一啲特製嘅程式），由過往嘅數據嗰度估計出「個系統有邊啲狀態」同埋「每對狀態之間嘅轉移概率係幾多」等嘅參數^{[註 5]}。如果最後得出嗰條馬可夫鏈有返咁上下準確－柞轉移概率有返咁上下準，條鏈就算係大致噉模擬緊個系統，於是嗰位科學家第時就可以攞條馬可夫鏈嚟預計嗰個系統嘅行為，包括係答以下呢啲問題^[21]：

• 有一串特定嘅狀態串連，呢串狀態串連發生嘅概率（${\displaystyle \Pr(X_{1}=x_{1},\ldots X_{N}=x_{N})}$）係幾多？
• 攞其中一個狀態，個系統保持喺呢個狀態度嘅概率係幾多？
• 攞其中一個狀態，個系統預期會維持喺呢個狀態幾耐？

... 等等。

蒙地卡羅方法

内文：馬可夫鏈蒙地卡羅

馬可夫鏈蒙地卡羅（Markov chain Monte Carlo，MCMC）係一系列統計學上成日用嘅演算法，建基於蒙地卡羅方法（簡單講就係啲程式帶有隨機性），做到由數據嗰度建立一條馬可夫鏈嚟表達一個系統嘅狀態，跟手再靠用條馬可夫鏈做模擬嚟搵出想要嘅概率分佈^[21][22]。當中吉布斯抽樣（Gibbs sampling）係最基本嗰種馬可夫鏈蒙地卡羅做法。吉布斯抽樣最簡單嗰個版本如下^[23][24]：

• 想像家陣有一個聯合概率分佈，${\displaystyle p(X,Y)}$，反映緊一對變數之間嘅概率分佈，研究者唔知呢個聯合概率分佈係乜樣；
• 研究者用 ${\displaystyle \Pr(X|Y)}$ 同 ${\displaystyle \Pr(Y|X)}$ 呢兩個條件概率數值嚟計數－喺實際應用上，呢啲條件概率數值可以輕易噉由數據嗰度計到出嚟（想像計「根據過往數據，每次狀態係 ${\displaystyle Y}$，跟住响下一刻時間狀態變做 ${\displaystyle X}$ 嘅概率係幾多」，然後又幫 ${\displaystyle X}$ 做同樣嘅嘢）。用虛擬碼寫出嚟嘅話，吉布斯抽樣做嘅嘢係噉嘅：

 初始化
 迴圈，for j = 1, 2, 3... do
   抽樣計 ${\displaystyle \Pr(X|Y^{j-1})}$
   抽樣計 ${\displaystyle \Pr(Y|X^{j})}$
 end for    

• 搵到嗮每對可能狀態之間嘅 ${\displaystyle \Pr(X|Y)}$（打前嗰個狀態係 ${\displaystyle Y}$，跟住係 ${\displaystyle X}$ 嘅概率）同 ${\displaystyle \Pr(Y|X)}$（打前嗰個狀態係 ${\displaystyle X}$，跟住係 ${\displaystyle Y}$ 嘅概率）之後，就可以估計到嗰兩個變數之間嘅聯合概率分佈；

當個研究者搵到嗮每對可能狀態之間嘅聯合概率分佈，佢就可以知道啲轉移概率嘅數值^[23]。

最大似然估計

内文：最大似然估計

喺統計模型上常用嘅最大似然估計（maximum likelihood estimation，MLE）都可以攞嚟由數據嗰度估計馬可夫鏈啲參數嘅數值。用一句嘢概括嘅話，最大似然估計所做嘅係搵出一柞參數數值，而呢柞參數數值係能夠令「得到手上呢柞數據」嘅概率最大化嘅^[25]。用數學啲嘅方法嚟表示嘅話，一排 ${\displaystyle N}$ 個狀態嘅集合 ${\displaystyle \{X_{1:T_{n}}^{(n)}\}}$，攞 ${\displaystyle t}$ 嚟表示序號（個狀態出現嘅時間點）嘅，要建立一個馬可夫鏈模型（搵出啲參數）畀佢嘅話，即係要設啲參數，令以下條式出嘅嗰個數值 ${\displaystyle \Pr(all)}$ 有咁大得咁大（可以參照返上高聯合概率分佈）^[26][27]：

${\displaystyle \Pr(all)=\prod _{n=1}^{N}\Pr(X_{1}^{(n)})\prod _{t=2}^{T_{N}}\Pr(X_{t}^{(n)}|X_{t-1}^{(n)})}$；

直白啲講，條式右手邊第一吓連乘表示乘嗮啲唔同序列嘅初始狀態嘅概率，第二吓連乘表示跟住條路線一路行到 ${\displaystyle T_{N}}$ 、一路乘嗮啲概率，所以成嚿嘢最後畀出嘅數值就反映到嗰成個概率，代表緊所建出嘅馬可夫鏈模型喺幾大程度上畀得返啲狀態序列係啱返啲真實數據嘅。考慮到同一款初始狀態可能會喺數據庫入面出現好多次（如果個案數成千上萬，即有好多份個案係由同一款初始狀態開始），同一種轉移又有可能出現好多次；係噉可以做合併，即係用對數處理條式並且攞次數項 ${\displaystyle L(k)}$、${\displaystyle N(i,j)}$ 嚟分別表示每一款初始狀態出現過幾多次、每一款狀態轉移又出現過幾多次，好似以下呢條式噉^[27]：

${\displaystyle \log \Pr(all)=\sum _{k=1}^{K}L(k)\log(\pi _{k})+\sum _{i=1}^{K}\sum _{j=1}^{K}N(i,j)\log(A_{ij})}$

當中 ${\displaystyle L(k)}$ 係某款初始狀態出現嘅次數，${\displaystyle N(i,j)}$ 係撞親某狀態 ${\displaystyle i}$ 前提下有後續狀態 ${\displaystyle j}$ 嘅次數。有咗條式之後，就可以用程式化嘅方法嚟逐步改變啲參數令 ${\displaystyle \log \Pr(all)}$ 有咁大得咁大，譬如藉助爬山演算法等數學最佳化技術^[27]。

進階類型

按時間特性

馬可夫鏈可以按時間嘅特性嚟分類。

離散時間

内文：離散時間馬可夫鏈

離散時間馬可夫鏈（discrete-time Markov chain）係最基本嗰種馬可夫鏈，指條鏈嘅時間係一個離散性變數：用日常用語講，「離散」即係話「時間點」呢個變數嘅每個可能數值之間都有啲窿窿罅罅喺度，是但攞一個可能嘅時間點數值 ${\displaystyle n}$ 嚟睇，${\displaystyle n}$ 同 ${\displaystyle n+1}$（或者 ${\displaystyle n}$ 同 ${\displaystyle n-1}$）之間並冇任何嘅可能時間點數值，個時間點數值淨係會一吓一吓噉由上一個數值跳去下一個數值；用集合論嘅語言嚟講嘅話，即係話包含可能時間點 ${\displaystyle n}$ 嗰個集合係一個可數集^[28][29]，

${\displaystyle \forall n,n\in \mathbb {N} }$

連續時間

内文：連續時間馬可夫鏈

連續時間馬可夫鏈（continuous-time Markov chain）將離散時間馬可夫鏈嘅時間變成一個連續性變數：用日常用語講，「連續」即係話「時間點」呢個變數嘅每個可能數值之間都冇窿罅，是但攞一個可能嘅時間點數值 ${\displaystyle n}$ 嚟睇，${\displaystyle n}$ 同 ${\displaystyle n+1}$（或者 ${\displaystyle n}$ 同 ${\displaystyle n-1}$）之間會有無限個可能嘅時間點數值，所以時間點呢個變數（最少理論上^{[註 6]}）可以小數點後有無限咁多個位都得^[30]。要數學性噉定義連續時間馬可夫鏈，可以用以下嘅做法（即係所謂嘅無窮小量定義；infinitesimal definition）^[31]：

• 設 ${\displaystyle X_{t}}$ 做一個隨機變數，表示條馬可夫鏈喺時間點 ${\displaystyle t}$ 嘅狀態；
• 假設到咗時間點 ${\displaystyle t}$，條鏈處於狀態 ${\displaystyle i}$；
• 想像有個正數 ${\displaystyle h}$，${\displaystyle X_{t}=i}$ 而 ${\displaystyle X_{t+h}=j}$，打前嗰啲時間點嘅狀態唔會影響跟住落嚟變咩狀態，而隨住 ${\displaystyle h\to 0}$（無窮小量），無論 ${\displaystyle t}$ 同 ${\displaystyle j}$ 係乜都好，以下嘅嘢都會成立：

  ${\displaystyle \Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)}$

• 當中 ${\displaystyle \delta _{ij}}$ 係卡羅內卡 δ（Kronecker delta；如果 ${\displaystyle i=j}$，${\displaystyle \delta _{ij}=1}$，否則 ${\displaystyle \delta _{ij}=0}$）；${\displaystyle q_{ij}}$ 反映由 ${\displaystyle i}$ 去 ${\displaystyle j}$ 嘅轉移發生得有幾快，${\displaystyle q_{ij}}$ 數值愈高就表示場轉移發生得愈快；${\displaystyle o}$ 係細 O 符號。

隱馬可夫模型

附圖 3

内文：隱馬可夫模型

隱馬可夫模型（hidden Markov model，HMM）係馬可夫鏈嘅一種，指條鏈將個系統想像成有一部份嘅狀態係所謂嘅隱藏狀態（hidden states）－顧名思義，隱藏狀態係研究者觀察唔到嘅，不過研究者有得靠觀察唔係隱藏嗰啲狀態嚟攞到有關隱藏狀態嘅資訊。定義上，設 ${\displaystyle X_{n}}$ 同 ${\displaystyle Y_{n}}$ 做兩個隨機過程，${\displaystyle n\geq 1}$，如果話 ${\displaystyle (X_{n},Y_{n})}$ 共同組成一條隱馬可夫鏈，即係話以下呢幾點成立（為咗簡單起見，當條鏈係離散時間嘅）^[32][33]：

• ${\displaystyle X_{n}}$ 係一個馬可夫過程（可以用馬可夫鏈模擬），不過啲狀態係不可知嘅；
• 無論 ${\displaystyle n}$ 係幾多（不過要符合 ${\displaystyle n\geq 1}$）都好，${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{1}=x_{1},\ldots ,X_{n}=x_{n}{\bigr )}=\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{n}=x_{n}{\bigr )}}$
  • 當中 ${\displaystyle A}$ 係可量集（指 ${\displaystyle A}$ 裏面嘅嘢都係量度得到嘅）。

舉個具體啲嘅例子說明，想像家陣有間房，房入面有三個罌，嗌呢三個罌做 ${\displaystyle X_{1}}$、${\displaystyle X_{2}}$ 同 ${\displaystyle X_{3}}$，每個罌都有波喺入面，啲波分 4 款，${\displaystyle y_{1},y_{2},y_{3},y_{4}}$，唔同款色水唔同，而三個罌彼此之間喺「入面唔同款嘅波之間嘅數量比例」上唔一樣；又想像間房入面有個人，喺每個時間點，佢都會由三個罌當中揀一個，然後由嗰個罌度抽一個波出嚟，再將個波（經門或者窗等）掟出嚟俾人睇，跟住再將個波擺返入去本來所屬嗰個罌度；研究者唔能夠直接睇到間房入面嘅事，但佢能夠睇到出嗰個波係邊個款－喺每個時間點 ${\displaystyle n}$，「揀咗邊個罌」係個隱藏狀態，但「出咗個乜款嘅波」係一個觀察得到嘅狀態，就好似附圖 3 噉樣。假想個研究者知每個罌入面唔同款嘅波之間嘅數量比例，佢會有能力由「出嗰個波嘅款」（唔完全準噉）估計「個波係由邊個罌嗰度抽出嚟」嘅－攞到有關隱藏狀態嘅資訊^[34]。

一個隱馬可夫模型嘅參數同一道理可以靠由過往數據嗰度做最大似然估計等嘅最佳化工序嚟得出。呢種模型喺好多領域都好有用，可以攞嚟模擬一啲唔係完全觀察到嘅現象，例如運算金融學呢個領域就會用到隱馬可夫模型（一個經濟體入面有好多資訊都係分析者冇得直接量度嘅）^[35]。

馬可夫決策過程

内文：馬可夫決策過程

馬可夫決策過程（Markov decision process）可以算係馬可夫鏈嘅一個擴張版，指條馬可夫鏈當中加咗決策（decision making）嘅機制：例如係以下呢幅圖當中嘅馬可夫決策過程噉；個過程模擬咗一隻簡單遊戲嘅虛擬世界，個虛擬世界有三個狀態（${\displaystyle S_{0}}$、${\displaystyle S_{1}}$ 同 ${\displaystyle S_{2}}$；例如一盤國際象棋棋盤可以有多個唔同嘅嘅樣），喺每一個狀態當中，玩家都有兩個可能嘅選擇（${\displaystyle a_{0}}$ 同 ${\displaystyle a_{1}}$；喺棋盤嘅每個可能狀態當中，玩家都有得揀行邊隻棋同點行）同埋相應嘅效益（可以想像成「行咗呢步會提高贏面提高幾多」），而每個選擇有若干概率會令到個世界變成另外一個狀態（由啲箭咀同箭咀側邊嘅數字表示）^[36][37]。

一盤國際象棋開局嗰陣嘅樣；國際象棋嘅棋盤可以有好多唔同款嘅狀態，而玩家嘅決策會改變盤棋嘅狀態。

如果要用程式語言嚟表達上述嘅馬可夫決策過程嘅話，設計者可以用好似以下噉嘅一個矩陣嚟表示唔同狀態之間嘅轉移概率，當中每個橫行表示「如果喺呢個狀態揀咗呢個選擇，會去另外一個狀態嘅概率」－喺狀態 ${\displaystyle S_{0}}$ 揀咗 ${\displaystyle a_{0}}$（${\displaystyle a_{0}{\text{ at }}S_{0}}$）嘅話，遊戲狀態會有 50% 機會變成 ${\displaystyle S_{0}}$、50% 機會變成 ${\displaystyle S_{2}}$... 如此類推^[38]：

${\displaystyle \mathbf {P} ={\begin{bmatrix}&(S_{0})&(S_{1})&(S_{2})\\(a_{0}{\text{ at }}S_{0})&0.5&0.0&0.5\\(a_{1}{\text{ at }}S_{0})&0.0&0.0&1.0\\(a_{0}{\text{ at }}S_{1})&0.7&0.1&0.2\\(a_{1}{\text{ at }}S_{1})&0.0&0.95&0.05\\(a_{0}{\text{ at }}S_{2})&0.4&0.0&0.6\\(a_{1}{\text{ at }}S_{2})&0.3&0.3&0.4\\\end{bmatrix}}}$

齋用數字（冇咁易睇）嘅話：

${\displaystyle \mathbf {P} ={\begin{bmatrix}0.5&0.0&0.5\\0.0&0.0&1.0\\0.7&0.1&0.2\\0.0&0.95&0.05\\0.4&0.0&0.6\\0.3&0.3&0.4\\\end{bmatrix}}}$

由國際象棋嘅例子可以睇得出，一隻隻遊戲可以抽象噉想像成馬可夫決策過程，而事實係，喺教人工智能玩遊戲嘅技術裏面成日都會用到馬可夫決策過程－研究者會教個人工智能程式由過往嘅數據（例如係俾個程式睇一大柞有關過去國際象棋對局嘅數據）估計個馬可夫決策過程嘅參數（參數包括啲轉移概率同埋「每款轉移會提升邊一方嘅贏面」呀噉），令個程式能夠好似有智能噉捉國際象棋同第啲棋類遊戲^[37]。

應用

有人試過用隨機漫步嚟模擬一個數值嘅上落，發覺得出嗰條線好似股價上落嘅線。

睇埋：統計學

有好多自然科學、社會科學同工程學上嘅研究都會用到馬可夫鏈嘅相關技術，將研究緊嘅系統想像成馬可夫鏈或者類似嘅抽象數學模型：

• 物理學：首先，熱力學同統計力學上都會用到馬可夫鏈模型，因為呢啲領域成日都要處理一啲隨機性而且狀態又會係噉變化嘅系統；簡單講，熱同能量嘅傳遞相當大程度上係受到粒子嗰啲隨機郁動主宰嘅^[39]。
• 化學：化學反應好多時都係會發生喺一個狀態（包括溫度同壓力等嘅特性）會係噉變化嘅系統，而呢啲狀態嘅特性都會影響化學反應嘅進行（例如好多化學反應喺溫度啱嗰陣都會加快），而且化學反應又會引致狀態變化（例如好多化學反應都會釋放熱）；因為噉，化學上嘅研究有陣時會將做緊化學反應嘅系統想像成一條條嘅馬可夫鏈^[40][41]。
• 生物學：一隻生物或者一隻生物嘅某啲部位可以想像成狀態會係噉變化嘅系統嚟模擬；包括親緣關係學、生物資訊科學、神經科學（神經系統嘅唔同部份狀態會係噉變化）^[42]同病毒學（受病毒感染嘅細胞狀態會慢慢變化）^[43]。
• 人工智能：馬古夫鏈喺人工智能上受到廣泛嘅採用；最基本上，人工智能做嘅係想機械展示出智能，而人工智能研究者成日會教電腦將思考緊嘅現象用馬可夫鏈嚟模擬（簡單講就攞數據，再叫電腦建立一條馬可夫鏈嚟預測目標嗰柞現象），令電腦做出好似有智能噉嘅行為^[37]。
• 經濟學同金融學：有好多同呢啲領域相關嘅現象都類似馬可夫鏈，例如有研究指，股價嘅上上落落可以大致上用隨機漫步嚟模擬（隨機漫步假說；random walk hypothesis）^[44][45]；除此之外，亦都有研究試過用馬可夫鏈嚟模擬商業週期（指經濟週期性噉好景同不景）^[46]。
• 遊戲：有好多遊戲都或多或少噉帶有隨機性，例如大富翁等嘅好多枱上遊戲都會涉及玩家用擲骰仔等嘅方法嚟決定遊戲跟住發生乜嘢事，所以遊戲嘅狀態（例如「每位玩家有幾多錢同企喺棋盤上面邊個位」呀噉）會有隨機性嘅變化；於是研究遊戲嘅人（可以睇遊戲設計等嘅領域）可以用馬可夫鏈嚟做模擬呢啲遊戲嘅數學模型^[47]。
• 運動：原則上，運動係遊戲嘅一種，都係涉及一班人跟住規則嚟交鋒；例如棒球就俾人指話可以想像成馬可夫鏈（每個狀態有「壘 A 有冇人」同「壘 B 有冇人」等嘅變數），而交戰雙方兩隊啲球員嘅實力－跑得有幾快或者擊球有幾準呀噉－會決定轉移概率^[48]。
• 音樂
• 資訊理論

... 等等。

註釋

1. 以下用到嗰啲數學符號，主要係嚟自概率論同埋集合論嘅。
2. 呢點令到用馬可夫鏈嚟模擬現實現象嗰陣慳返好多時間－要預測個系統下一刻嘅狀態嗰陣，淨係需要知個系統嘅現時狀態。
3. ${\displaystyle \prod }$ 係指連乘。
4. 有關向量同矩陣嘅計算要點樣做，可以睇吓線性代數方面嘅嘢。
5. 事實上，「由過往嘅數據嗰度建立能夠預測未來嘅模型」正正就係科學最緊要嘅目的之一。
6. 喺實際應用上，研究者用電腦計馬可夫鏈嘅數嗰陣，因為電腦記憶體實係有限嘅，所以電腦計數嗰時能夠記住嘅數「可能有幾多個位」都係有限嘅。

文獻

• Andrieu, C., De Freitas, N., Doucet, A., & Jordan, M. I. (2003). An introduction to MCMC for machine learning (PDF). Machine learning, 50(1), 5-43.
• Hamra, G., MacLehose, R., & Richardson, D. (2013). Markov chain Monte Carlo: an introduction for epidemiologists (PDF). International journal of epidemiology, 42(2), 627-634.
• Levy, R. (2009). The rise of Markov chain Monte Carlo estimation for psychometric modeling (PDF). Journal of Probability and Statistics, 2009.
• Privault, N. (2013). Understanding Markov Chains: Examples and Applications, Publisher Springer-Verlag Singapore, 357, 358.
• Sinharay, S. (2004). Experiences with Markov chain Monte Carlo convergence assessment in two psychometric examples (PDF). Journal of Educational and Behavioral Statistics, 29(4), 461-488.
• Van Ravenzwaaij, D., Cassey, P., & Brown, S. D. (2018). A simple introduction to Markov Chain Monte-Carlo sampling (PDF). Psychonomic bulletin & review, 25(1), 143-154.

睇埋

• 隨機過程
• 隨機漫步
• 隨機性
• 最佳化
• 逼近理論
• 動態系統
• 電腦模擬
• N-gram
• 瓣瓣掂玩遊戲
• 詞性標注

考

1. Samuel Karlin; Howard E. Taylor (2 December 2012). A First Course in Stochastic Processes. Academic Press. p. 47.
2. Satish L, Gururaj BI (April 2003). "Use of hidden Markov models for partial discharge pattern classification". IEEE Transactions on Dielectrics and Electrical Insulation.
3. Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268.
4. Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag.
5. Van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). "A simple introduction to Markov Chain Monte-Carlo sampling". Psychonomic Bulletin & Review. 25 (1): 143–154.
6. Rocca, Joseph and Rocca, Baptiste. (2019). Introduction to Markov chains. Towards Data Science.
7. Parzen, E. (2015). Stochastic Processes. Courier Dover Publications. p. 188.
8. Lamperti, J. (1977). Stochastic processes: a survey of the mathematical theory. Springer-Verlag. pp. 106-121.
9. Sheldon M. Ross (1996). Stochastic processes. Wiley. pp. 174 and 231.
10. Øksendal, B. K. (Bernt Karsten) (2003). Stochastic differential equations : an introduction with applications (6th ed.). Berlin: Springer.
11. Sheldon M. Ross (1996). Stochastic processes. Wiley. pp. 235 and 358.
12. Guttorp, Peter; Thorarinsdottir, Thordis L. (2012). "What Happened to Discrete Chaos, the Quenouille Process, and the Sharp Markov Property? Some History of Stochastic Point Processes". International Statistical Review. 80 (2): 253–268.
13. Charles Miller Grinstead; James Laurie Snell (1997). Introduction to Probability. American Mathematical Soc. pp. 464-466.
14. Hayes, B. (2013). First links in the Markov chain (PDF). American Scientist, 101(2), 252.
15. Spade, David A. (2020). Handbook of Statistics. North Holland. ISBN9780444642110.
16. Bishop, C. M. (2006). Pattern Recognition and Machine Learning (PDF). New York: Springer Science + Business Media, LLC.
17. Limiting distribution for a Markov chain (PDF). Columbia University.
18. Paige, C. C., Styan, G. P., & Wachter, P. G. (1975). Computation of the stationary distribution of a Markov chain. Journal of Statistical Computation and Simulation, 4(3), 173-186.
19. Kirkland, S. (2003). Conditioning properties of the stationary distribution for a Markov chain. The Electronic Journal of Linear Algebra, 10, 1-15.
20. Markov Chains - Stationary Distributions 互聯網檔案館嘅歸檔，歸檔日期2021年10月23號，.. Bioeng C141 - Statistics for Bioinformatics.
21. Andrieu, C., De Freitas, N., Doucet, A., & Jordan, M. I. (2003). An introduction to MCMC for machine learning (PDF). Machine learning, 50(1), 5-43.
22. Hamra, G., MacLehose, R., & Richardson, D. (2013). Markov chain Monte Carlo: an introduction for epidemiologists (PDF). International journal of epidemiology, 42(2), 627-634.
23. Gibbs Sampling. Towards Data Science.
24. Module 7: Introduction to Gibbs Sampling. (PDF)
25. Rossi, Richard J. (2018). Mathematical Statistics : An Introduction to Likelihood Based Inference. New York: John Wiley & Sons. p. 227.
26. Shalizi, Cosma (2009). "Note: Maximum Likelihood Estimation for Markov Chains" (PDF). Statistics Department Carnegie Mellon University.{{cite web}}: CS1 maint: url-status (link)
27. The path from Maximum Likelihood Estimation to Hidden Markov Models. Towards Data Science.
28. Asher Levin, David (2009). Markov chains and mixing times. p. 16.
29. Discrete-time Markov chains (PDF). Columbia University.
30. Continuous-Time Markov Chains (PDF). Columbia University.
31. Norris, J. R. (1997). "Continuous-time Markov chains I". Markov Chains. pp. 60-107.
32. Hidden Markov Models: Fundamentals and Applications, Part 1.
33. Hidden Markov Models: Fundamentals and Applications, Part 2.
34. Lawrence R. Rabiner (February 1989). "A tutorial on Hidden Markov Models and selected applications in speech recognition" (PDF). Proceedings of the IEEE. 77 (2): 257–286.
35. Petropoulos, A., Chatzis, S. P., & Xanthopoulos, S. (2016). A novel corporate credit rating system based on Student’st hidden Markov models. Expert Systems with Applications, 53, 87-105.
36. Hugh Brendan McMahan (2006), Robust Planning in Domains with Stochastic Outcomes, Adversaries, and Partial Observability, CMU-CS-06-166, pp. 3–4
37. Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag.
38. Getting Started with Markov Decision Processes: Reinforcement Learning. Data Science.
39. Andrae, B., Cremer, J., Reichenbach, T., & Frey, E. (2010). Entropy production of cyclic population dynamics (PDF). Physical review letters, 104(21), 218102.
40. Anderson, David F.; Kurtz, Thomas G. (2011), "Continuous Time Markov Chain Models for Chemical Reaction Networks", Design and Analysis of Biomolecular Circuits, Springer New York, pp. 3-42.
41. Du, Chao; Kou, S. C. (September 2012). "Correlation analysis of enzymatic reaction of a single protein molecule". The Annals of Applied Statistics. 6 (3): 950–976.
42. George, Dileep; Hawkins, Jeff (2009). Friston, Karl J. (ed.). "Towards a Mathematical Theory of Cortical Micro-circuits". PLOS Comput Biol. 5 (10): e1000532.
43. Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268.
44. Bachelier, Louis (1900). "Théorie de la spéculation". Annales Scientifiques de l'École Normale Supérieure. 3: 21–86.
45. Cootner, Paul H. (1964). The random character of stock market prices. MIT Press.
46. Hamilton, J. D. (1989). A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica: Journal of the econometric society, 357-384.
47. Osborne, J. A. (2003). Markov chains for the Risk board game revisited 互聯網檔案館嘅歸檔，歸檔日期2021年8月25號，. (PDF). Mathematics magazine, 76(2), 129-135.
48. Mark D. Pankin, BASEBALL AS A MARKOV CHAIN 互聯網檔案館嘅歸檔，歸檔日期2009年5月13號，..

拎

• Introduction to Markov chains. Towards Data Science.
• Gentle Introduction to Markov Chain. Machine Learning+.
• Gibbs Sampling. Towards Data Science.
• Techniques to Understand Computer Simulations: Markov Chain Analysis.
• Markov Chains chapter in American Mathematical Society's introductory probability book (PDF).
• A beautiful visual explanation of Markov Chains.
• Discrete-time Markov chains (PDF). Columbia University.
• Continuous-Time Markov Chains (PDF). Columbia University.