馬爾可夫鏈

在人類發展的歷史上，馬爾可夫鏈是第一個從理論上被提出並加以研究的隨機過程模型。 ^[40] 

馬爾可夫鏈的提出來自俄國數學家安德雷·馬爾可夫（Андрей Андреевич Марков）。為了擴大概率論極限定理的應用範圍，1906年，馬爾可夫在論文《大數定律關於相依變量的擴展》中第一次提到這種如同鎖鏈般環環相扣的隨機變量序列，其特點是：當一些隨機變量依次被觀測時，隨機變量的分佈僅僅依賴於前一個被觀測的隨機變量，而不依賴於更前面的隨機變量，這就是被後人稱作馬爾可夫鏈的著名概率模型。 ^[41] 

馬爾可夫在1906-1907年間發表的研究中為了證明隨機變量間的獨立性不是弱大數定律（weak law of large numbers）和中心極限定理（central limit theorem）成立的必要條件，構造了一個按條件概率相互依賴的隨機過程，並證明其在一定條件下收斂於一組向量，該隨機過程被後世稱為馬爾可夫鏈 ^{[1]  [5-6]}  。

在馬爾可夫鏈被提出之後，保羅·埃倫費斯特（Paul Ehrenfest）和Tatiana Afanasyeva在1907年使用馬爾可夫鏈建立了Ehrenfest擴散模型（Ehrenfest model of diffusion） ^[7]  。1912年亨利·龐加萊（Jules Henri Poincaré）研究了有限羣上的馬爾可夫鏈並得到了龐加萊不等式（Poincaré inequality） ^[8-9]  。

1931年，安德雷·柯爾莫哥洛夫（Андрей Николаевич Колмогоров）在對擴散問題的研究中將馬爾可夫鏈推廣至連續指數集得到了連續時間馬爾可夫鏈，並推出了其聯合分佈函數的計算公式 ^[10]  。獨立於柯爾莫哥洛夫，1926年，Sydney Chapman在研究布朗運動時也得到了該計算公式，即後來的Chapman-Kolmogorov等式 ^[10]  。

1953年，Nicholas Metropolis等通過構建馬爾可夫鏈完成了對流體目標分佈函數的隨機模擬 ^[11]  ，該方法在1970年由Wilfred K. Hastings進一步完善，並發展為現今的梅特羅波利斯-黑斯廷斯算法（Metropolis-Hastings algorithm） ^[12]  。

1957年，Richard Bellman通過離散隨機最優控制模型首次提出了馬爾可夫決策過程（Markov Decision Processes, MDP） ^[13]  。

1959-1962，前蘇聯數學家Eugene Borisovich Dynkin完善了柯爾莫哥洛夫的理論並通過Dynkin公式（Dynkin formula）將平穩馬爾可夫過程與鞅過程（martingale process）相聯繫 ^[14-15]  。

此後以馬爾可夫鏈為基礎，更復雜的馬爾可夫模型（例如隱馬爾可夫模型 ^[16]  和馬爾可夫隨機場 ^[17]  ）被相繼提出，並在模式識別等實際問題中得到應用了 ^[18]  。

馬爾可夫鏈是一組具有馬爾可夫性質的離散隨機變量的集合。具體地，對概率空間

內以一維可數集為指標集（index set） 的隨機變量集合

，若隨機變量的取值都在可數集內：

，且隨機變量的條件概率滿足如下關係 ^[2]  ：

則

被稱為馬爾可夫鏈，可數集

被稱為狀態空間（state space），馬爾可夫鏈在狀態空間內的取值稱為狀態 ^[2]  。這裏定義的馬爾可夫鏈是離散時間馬爾可夫鏈（Discrete-Time MC, DTMC），其具有連續指數集的情形雖然被稱為連續時間馬爾可夫鏈（Continuous-Time MC, CTMC），但在本質上是馬爾可夫過程（Markov process） ^[19]  。常見地，馬爾可夫鏈的指數集被稱為“步”或“時間步（time-step）” ^[2]  。

上式在定義馬爾可夫鏈的同時定義了馬爾可夫性質，該性質也被稱為“無記憶性（memorylessness）”，即t+1步的隨機變量在給定第t步隨機變量後與其餘的隨機變量條件獨立（conditionally independent）：

^[2]  。在此基礎上，馬爾可夫鏈具有強馬爾可夫性（strong Markov property），即對任意的停時（ stopping time），馬爾可夫鏈在停時前後的狀態相互獨立 ^[1]  。

馬爾科夫鏈的一個常見例子是簡化的股票漲跌模型：若一天中某股票上漲，則第二天該股票有概率p開始下跌，1-p繼續上漲；若一天中該股票下跌，則明天該股票有概率q開始上漲，1-q繼續下跌。該股票的漲跌情況是一個馬爾可夫鏈，且定義中各個概念在例子中有如下對應：

n-階馬爾可夫鏈擁有n階的記憶性，可視為馬爾可夫鏈的推廣。類比馬爾可夫鏈的定義，n-階馬爾可夫鏈滿足如下條件：

按上式，傳統的馬爾可夫鏈可以認為是1-階馬爾可夫鏈 ^[20]  。由馬爾可夫性質可得，將多個馬爾可夫鏈作為組元可以得到n-階的馬爾可夫鏈。

馬爾可夫鏈中隨機變量的狀態隨時間步的變化被稱為演變（evolution）或轉移（transition）。這裏介紹描述馬爾可夫鏈結構的兩種途徑，即轉移矩陣和轉移圖，並定義了馬爾可夫鏈在轉移過程中表現出的性質。

馬爾可夫鏈中隨機變量間的條件概率可定義為如下形式的（單步）轉移概率和n-步轉移概率 ^[2]  ：

式中下標

表示第n步的轉移。由馬爾可夫性質可知，在給定初始概率

後，轉移概率的連續乘法可以表示馬爾可夫鏈的有限維分佈（finite-dimensional distribution） ^[2]  ：

式中的

為樣本軌道（sample path），即馬爾可夫鏈每步的取值 ^[2]  。對n-步轉移概率，由Chapman–Kolmogorov等式可知，其值為所有樣本軌道的總和 ^[2]  ：

上式表明，馬爾可夫鏈直接演變n步等價於其先演變n-k步，再演變k步（k處於該馬爾可夫鏈的狀態空間內）。n-步轉移概率與初始概率的乘積被稱為該狀態的絕對概率。

若一個馬爾可夫鏈的狀態空間是有限的，則可在單步演變中將所有狀態的轉移概率按矩陣排列，得到轉移矩陣 ^[2]  ：

馬爾可夫鏈的轉移矩陣是右隨機矩陣（right stochastic matrix），矩陣的第

行表示

時

取所有可能狀態的概率（離散分佈），因此馬爾可夫鏈完全決定轉移矩陣，轉移矩陣也完全決定馬爾可夫鏈 ^[21]  。由概率分佈的性質可得，轉移矩陣是一個正定矩陣，且每行元素之和等於1：

按相同的方式也可定義n-步轉移矩陣：

，由n-步轉移概率的性質（Chapman–Kolmogorov等式）可知，n-步轉移矩陣是其之前所有轉移矩陣的連續矩陣乘法：

^[2]  。

馬爾可夫鏈的演變可以按圖（graph）結構，表示為轉移圖（transition graph），圖中的每條邊都被賦予一個轉移概率。通過轉移圖可引入“可達”和“連通”的概念：

若對馬爾可夫鏈中的狀態

有：

，即採樣路徑上的所有轉移概率不為0，則狀態

是狀態

的可達狀態，在轉移圖中表示為有向連接：

。如果

互為可達狀態，則二者是連通的，在轉移圖中形成閉合迴路，記為

^[1]  。由定義，可達與連通可以是間接的，即不必在單個時間步完成。

連通是一組等價關係，因此可以構建等價類（equivalence classes），在馬爾可夫鏈中，包含儘可能多狀態的等價類被稱為連通類（communicating class） ^[1]  。

給定狀態空間的一個子集，若馬爾可夫鏈進入該子集後無法離開：

，則該子集是閉合的，稱為閉合集，一個閉合集外部的所有狀態都不是其可達狀態。若閉合集中只有一個狀態，則該狀態是吸收態，在轉移圖中是一個概率為1的自環。一個閉合集可以包括一個或多個連通類。

這裏通過一個轉移圖的例子對上述概念進行舉例説明 ^[1]  ：

由定義可知，該轉移圖包含了三個連通類：

、三個閉合集：

和一個吸收態，即狀態6。注意到，在上述轉移圖中，馬爾可夫鏈從任意狀態出發最終都會進入吸收態，這類馬爾可夫鏈被稱為吸收馬爾可夫鏈（absorbing Markov chain） ^[22]  。

這裏對馬爾可夫鏈的4個性質：不可約性、常返性、週期性和遍歷性進行定義。與馬爾可夫性質不同，這些性質不是馬爾可夫鏈必然擁有的性質，而是其在轉移過程中對其狀態表現出的性質。上述性質都是排他的，即不具有可約性的馬爾可夫鏈必然是不可約的，以此類推。

如果一個馬爾可夫鏈的狀態空間僅有一個連通類，即狀態空間的全體成員，則該馬爾可夫鏈是不可約的，否則馬爾可夫鏈具有可約性（reducibility） ^[23]  。馬爾可夫鏈的不可約性意味着在其演變過程中，隨機變量可以在任意狀態間轉移 ^[1]  。

若馬爾可夫鏈在到達一個狀態後，在演變中能反覆回到該狀態，則該狀態是常返狀態，或該馬爾可夫鏈具有（局部）常返性，反之則具有瞬變性（transience）的。正式地，對狀態空間中的某個狀態，馬爾可夫鏈對一給定狀態的返回時間（return time）是其所有可能返回時間的下確界（infimum） ^[1]  ：

若

，則該狀態不存在瞬變性或常返性；若

，則該狀態的瞬變性和常返性的判斷準則如下 ^[1]  ：

在時間步趨於無窮時，常返狀態的返回概率（return probability）的和，即總訪問次數的期望也趨於無窮：

此外，若狀態

具有常返性，則可計算其平均返回時間（mean recurrence time） ^[1]  ：

若平均返回時間

，該狀態是“正常返的（positive recurrent）”，否則為“零常返的（null recurrent）” ^[1]  。若一個狀態是零常返的，那意味着馬爾可夫鏈兩次訪問該狀態的時間間隔的期望是正無窮 ^[24]  。

由上述瞬變性和常返性的定義可有如下推論：

一個正常返的馬爾可夫鏈可能具有周期性，即在其演變中，馬爾可夫鏈能夠按大於1的週期常返其狀態。正式地，給定具有正常返的狀態

，其返回週期按如下方式計算 ^[1]  ：

式中

表示取集合元素的最大公約數。舉例説明，若在轉移圖中，一個馬爾可夫鏈返回某狀態需要的步數為

，則其週期是3，即返回該狀態所需的最小步數。若按上式計算得到

，該狀態具有周期性，若

，該狀態具有非週期性（aperiodicity） ^[1]  。由週期性的定義可有如下推論：

若馬爾可夫鏈的一個狀態是正常返的和非週期的，則該狀態具有遍歷性 ^[1]  。若一個馬爾可夫鏈是不可還原的，且有某個狀態是遍歷的，則該馬爾可夫鏈的所有狀態都是遍歷的，被稱為遍歷鏈。由上述定義，遍歷性有如下推論：

遍歷鏈是非週期的平穩馬爾可夫鏈，有長時間尺度下的穩態行為，因此是被廣泛研究和應用的馬爾可夫鏈 ^{[1]  [2]}  。

這裏介紹馬爾可夫鏈的長時間尺度行為的描述，即平穩分佈和極限分佈，並定義平穩馬爾可夫鏈。

平穩分佈（stationary distribution）

給定一個馬爾可夫鏈，若在其狀態空間存在概率分佈

，且該分佈滿足以下條件：

則

是該馬爾可夫鏈的平穩分佈。式中

是轉移矩陣和轉移概率，等價符號右側的線性方程組被稱為平衡方程（balance equation）。進一步地，若馬爾可夫鏈的平穩分佈存在，且其初始分佈是平穩分佈，則該馬爾可夫鏈處於穩態（steady state） ^[1]  。從幾何觀點，考慮馬爾可夫鏈的平穩分佈有

，因此該分佈的支撐集是一個正單純形（standard simplex）。

對不可約的馬爾可夫鏈，當且僅當其存在唯一平穩分佈，即平衡方程

在正單純形上有唯一解時，該馬爾可夫鏈是正常返的，且平穩分佈有如下表示 ^{[1]  [23]}  ：

上述結論被稱為平穩分佈準則（stationary distribution criterion） ^[1]  。對不可約和常返的馬爾可夫鏈，求解平衡方程可得到除尺度外唯一的特徵向量，即不變測度（invariant measure），若該馬爾可夫鏈是正常返的，則其平穩分佈是求解平衡方程時得到的，特徵值為1時的特徵向量，即歸一化後的不變測度 ^[2]  ，因此馬爾可夫鏈存在平穩分佈的充要條件是其存在正常返狀態。此外通過舉例可知，若一個馬爾可夫鏈包含多個由正常返狀態組成的連通類（由性質可知它們都是閉合集，所以該馬爾可夫鏈不是正常返的），則每個連通類都擁有一個平穩分佈，且演變得到的穩態取決於初始分佈。

若一個馬爾可夫鏈的狀態空間存在概率分佈

並滿足如下關係：

則該分佈是馬爾可夫鏈的極限分佈。注意到極限分佈的定義與初始分佈無關，即對任意的初始分佈，當時間步趨於無窮時，隨機變量的概率分佈趨於極限分佈 ^[2]  。按定義，極限分佈一定是平穩分佈，但反之不成立，例如週期性的馬爾可夫鏈可能具有平穩分佈，但週期性馬爾可夫鏈不收斂於任何分佈，其平穩分佈不是極限分佈 ^[25]  。

兩個獨立的非週期平穩馬爾可夫鏈，即遍歷鏈如果有相同的轉移矩陣，那麼當時間步趨於無窮時，兩者極限分佈間的差異趨於0。按隨機過程中的耦合（coupling）理論，該結論的表述為：對狀態空間相同的遍歷鏈

，給定任意初始分佈後有 ^[2]  ：

式中

表示上確界（supremum）。考慮平穩分佈的性質，該結論有推論：對遍歷鏈

，當時間步趨於無窮時，其極限分佈趨於平穩分佈 ^[2]  ：

該結論有時被稱為馬爾可夫鏈的極限定理（limit theorem of Markov chain），表明若馬爾可夫鏈是遍歷的，則其極限分佈是平穩分佈。對一個不可約和非週期的馬爾可夫鏈，其是遍歷鏈等價於其極限分佈存在，也等價於其平穩分佈存在 ^{[2]  [26]}  。

若一個馬爾可夫鏈為遍歷鏈，則由遍歷定理，其對某一狀態的訪問次數與時間步的比值，在時間步趨於無窮時趨近於平均返回時間的倒數，即該狀態的平穩分佈或極限分佈 ^[1]  ：

遍歷定理的證明依賴於強大數定律（Strong Law of Large Numbers, SLLN），表明遍歷鏈無論初始分佈如何，在經過足夠長的演變後，對其中一個隨機變量進行多次觀測（極限定理）和對多個隨機變量進行一次觀測（上式左側）都可以得到極限分佈的近似 ^[1]  。由於遍歷鏈滿足極限定理和遍歷定理，因此MCMC通過構建遍歷鏈以確保其在迭代中收斂於平穩分佈 ^[27]  。

若一個馬爾可夫鏈擁有唯一的平穩分佈且極限分佈收斂於平穩分佈，則按定義等價於，該馬爾可夫鏈是平穩馬爾可夫鏈 ^[2]  。平穩馬爾可夫鏈是嚴格平穩隨機過程，其演變與時間順序無關 ^[2]  ：

由極限定理可知，遍歷鏈是平穩馬爾可夫鏈。此外由上述定義，平穩馬爾可夫鏈的轉移矩陣是常數矩陣，n-步轉移矩陣則是該常數矩陣的n次冪 ^[21]  。平穩馬爾可夫鏈也被稱為齊次馬爾可夫鏈（time-homogeneous Markov chain）與之對應的，若馬爾可夫鏈不滿足上述條件，則被稱為非平穩馬爾可夫鏈（non-stationary Markvo chain）或非齊次馬爾可夫鏈（time-inhomogeneous Markov chain） ^[28]  。

若平穩馬爾可夫鏈對其任意兩個狀態滿足細緻平衡（detailed balance）條件，則其具有可逆性，被稱為可逆馬爾可夫鏈（reversible Markov chain） ^[29]  ：

馬爾可夫鏈的可逆性是更嚴格的不可約性，即其不僅可以在任意狀態間轉移，且向各狀態轉移的概率是相等的，因此可逆馬爾可夫鏈是平穩馬爾可夫鏈的充分非必要條件。在馬爾可夫鏈蒙特卡羅（Markvo chain Monte Carlo, MCMC） 中，構建滿足細緻平衡條件的可逆馬爾可夫鏈，是確保其以採樣分佈為平穩分佈的方法 ^[29]  。

伯努利過程也被稱為二項馬可夫鏈（Binomial Markov chain），其建立過程如下：給定一系列相互獨立的“標識”，每個標識都是二項的，按概率

取正和負。令正隨機過程

表示n個標識中有k個正標識的概率，則其是一個伯努利過程，其中的隨機變量服從二項分佈（binomial distribution） ^[2]  ：

由建立過程可知，增加的新標識中正標識的概率與先前正標識的數量無關，具有馬爾可夫性質，因此伯努利過程是一個馬爾可夫鏈 ^[2]  。

假設賭徒持有有限個籌碼在賭場下注，每次下注以概率

贏或輸一個籌碼，若賭徒不斷下注，則其持有的籌碼總數是一個馬爾可夫鏈，且有如下轉移矩陣 ^[2]  ：

賭徒輸光籌碼是吸收態，由一步分析（one-step analysis）可知，當

時，該馬爾可夫鏈必然進入吸收態，即賭徒無論持有多少籌碼，隨着賭注的進行最終都會輸光。

定義一系列獨立同分布（independent identically distributed, iid）的整數隨機變量

，並定義如下隨機過程 ^[2]  ：

則隨機過程

是整數集內的隨機遊走，而

是步長。由於步長是iid的，因此當前步與先前步相互獨立，該隨機過程是馬爾可夫鏈 ^[2]  。伯努利過程和賭徒破產問題都是隨機遊走的特例 ^[2]  。

由上述隨機遊走的例子可知，馬爾可夫鏈有一般性的構建方法，具體地，若狀態空間

內的隨機過程

有滿足形式 ^[2]  ：

其中，

，

為空間

的iid隨機變量且獨立於

，則隨機過程

是馬爾可夫鏈，其一步轉移概率為：

^[2]  。該結論表明，馬爾可夫鏈可以由

區間內服從iid均勻分佈的隨機變量（隨機數）進行數值模擬 ^[2]  。

馬爾可夫過程也被稱為連續時間馬爾可夫鏈，是馬爾可夫鏈或離散時間馬爾可夫鏈的推廣，其狀態空間是可數集，但一維指數集不再有可數集的限制，可以表示連續時間。馬爾可夫過程與馬爾可夫鏈的性質是可以類比的，其馬爾可夫性質通常有如下表示 ^[2]  ：

由於馬爾可夫過程的狀態空間是可數集，在連續時間下其樣本軌道幾乎必然（a.s.）是右連續的片段函數，因此馬爾可夫過程可以表示為跳躍過程（jump process）並與馬爾可夫鏈相聯繫 ^[2]  ：

式中

是某個狀態的滯留時間（sojourn time），

是順序的指數集成員（時間片段）。滿足上述關係的馬爾可夫鏈

和滯留時間

是跳躍過程

在有限個時間片段下的局部嵌入過程（locally embedded process） ^[2]  。

馬爾可夫模型（Markov model）

馬爾可夫鏈或馬爾可夫過程不是唯一以馬爾可夫性質為基礎建立的隨機過程，事實上，隱馬爾可夫模型、馬爾可夫決策過程、馬爾可夫隨機場等隨機過程/隨機模型都具有馬爾可夫性質並被統稱為馬爾可夫模型。這裏對馬爾可夫模型的其它成員做簡要介紹：

HMM是一個狀態空間不完全可見，即包含隱藏狀態（hidden status）的馬爾可夫鏈，HMM中可見的部分被稱為輸出狀態（emission state），與隱藏狀態有關，但不足以形成完全的對應關係。以語音識別（speech recognition）為例，需要識別的語句是不可見的隱藏狀態，接收的語音或音頻是和語句有關的輸出狀態，此時HMM常見的應用是基於馬爾可夫性質從語音輸入推出其對應的語句，即從輸出狀態反解隱藏狀態 ^{[16]  [18]}  。

2. 馬爾可夫決策過程（Markov decision process, MDP）：

MDP是在狀態空間的基礎上引入了“動作”的馬爾可夫鏈，即馬爾可夫鏈的轉移概率不僅與當前狀態有關，也與當前動作有關。MDP包含一組交互對象，即智能體（agent）和環境，並定義了5個模型要素：狀態（state）、動作（action）、策略（policy）、獎勵（reward）和回報（return），其中策略是狀態到動作的映射，回報是獎勵隨時間步的折現或積累。在MDP的演化中，智能體對環境的初始狀態進行感知，按策略實施動作，環境受動作影響進入新的狀態並反饋給智能體一個獎勵。智能體接收“獎勵”並採取新的策略，與環境持續交互。MDP是強化學習（reinforcement learning）的數學模型之一，被用於模擬智能體可實現的隨機性策略與回報 ^[30]  。MDP的推廣之一是部分可觀察馬爾可夫決策過程（partially observable Markov decision process, POMDP），即考慮了HMM中隱藏狀態和輸出狀態的MDP ^[30]  。

MRF是馬爾可夫鏈由一維指數集向高維空間的推廣。MRF的馬爾可夫性質表現為其任意一個隨機變量的狀態僅由其所有鄰接隨機變量的狀態決定。 類比馬爾可夫鏈中的有限維分佈，MRF中隨機變量的聯合概率分佈是所有包含該隨機變量的團（cliques）的乘積。MRF最常見的例子是伊辛模型（Ising model） ^{[17]  [31]}  。

哈里斯鏈是馬爾可夫鏈從可數狀態空間向連續狀態空間的推廣，給定可測空間

上的平穩馬爾可夫鏈

，若對可測空間的任意子集

和子集的返回時間

，該馬爾可夫鏈滿足 ^[32]  ：

則該馬爾可夫鏈是哈里斯鏈，式中的

是可測空間的σ-有限測度（σ-finite measure） ^[32]  。

構建以採樣分佈為極限分佈的馬爾可夫鏈是馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo, MCMC）的核心步驟，MCMC通過在馬爾可夫鏈上不斷迭代時間步以得到近似服從採樣分佈的隨機數，並使用這些隨機數逼近求解目標對採樣分佈的數學期望 ^{[2]  [3]}  ：

馬爾可夫鏈的極限分佈性質決定了MCMC是無偏估計（unbiased estimation），即採樣數趨於無窮時會得到求解目標數學期望的真實值，這將MCMC與其替代方法，例如變分貝葉斯估計（variational Bayesian inference）相區分，後者計算量通常小於MCMC但無法確保得到無偏估計 ^[33]  。

在物理學和化學中，馬爾可夫鏈和馬爾可夫過程被用於對動力系統進行建模，形成了馬爾可夫動力學（Markov dynamics） ^[34-35]  。 在排隊論（queueing theory）中，馬爾可夫鏈是排隊過程的基本模型 ^[36]  。在信號處理方面，馬爾可夫鏈是一些序列數據壓縮算法，例如Ziv-Lempel編碼的數學模型 ^[37-38]  ，在金融領域，馬爾可夫鏈模型被用於預測企業產品的市場佔有率 ^[39]  。

隨着馬爾可夫鏈的逐步深人研究，它在經濟學、生物學、物理學、化學、軍事學 天文學等領域都引起了連鎖反應，衍生出一系列新課題、新理論和新學科。馬爾可夫鏈具有豐富的數學理論，與其他數學學科相互滲透；而它又與自然科學、技術科學、管理科學、經濟科學以至人文科學有廣泛的交叉應用。很多問題都可建立馬爾可夫過程概率模型，運用概率論及隨機過程的理論及方法進行研究，而它們又不斷地衍生出新的研究課題。這種交互作用促進了當代概率論的飛速發展。而當前馬爾可夫鏈的理論研究，正方興未艾。 ^[40]