馬可夫鏈

係概率論同統計學等領域上常用嘅一種隨機模型，個名嚟自創始呢個概念嘅 19 世紀俄羅斯數學家安德里·馬可夫。簡單講，一條馬可夫鏈會將分析緊嘅系統想像成一嚿帶有隨機性嘅數學物體，即係會將研究緊嘅系統諗做由以下呢兩樣嘢構成：
若干個可能嘅狀態，
每個可能狀態  都會褦住柞數  嚟表示「世界由  呢個狀態變成另一個狀態嘅機會率」，
例如幅附圖 1 入面嗰條簡單嘅馬可夫鏈就係噉：條鏈有  同  兩個可能狀態；如果家陣世界嘅狀態係 ，下一刻狀態變成  嘅機率係 70% / 0.7，狀態繼續維持係  嘅機率係 30% / 0.3；如果家陣世界嘅狀態係 ，下一刻狀態變成  嘅機率係 40% / 0.4，狀態繼續係  嘅機率係 60% / 0.6。除此之外，馬可夫鏈仲可以按好多特性分做進階嘅類別，例如隱馬可夫模型就係一種特殊嘅馬可夫鏈，指條鏈當中有一部份嘅狀態係研究者觀察唔到嘅，研究者要齋靠觀察淨低嗰啲－觀察得到嘅－狀態嚟對啲隱藏狀態作出判斷。

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

定義 

喺定義上，一條基本嘅馬可夫鏈係具有以下呢三大特性嘅隨機過程：
有若干個可能狀態。技術性啲噉講，即係話狀態  嘅可能數值組成  噉嘅一個狀態空間－
呢個狀態空間係一個可數集，，而且
條馬可夫鏈仲要有個概率分佈表示每個狀態有幾大概率會係初始狀態， 。
有若干條規則指明狀態之間嘅轉移概率；通常嚟講，馬可夫鏈啲狀態轉移會由時間決定，所以轉移概率可以寫做  噉嘅樣，當中  係指時間點，即係：

用日常用語講嘅話，上面呢條式嘅意思如下： 嘅數值反映「如果已知呢一刻時間嘅狀態係 ，噉下一刻時間嘅狀態係 」嘅概率。
滿足到馬可夫性質，噉講意思即係話個系統冇「記憶」呢種功能，「下一刻狀態會變乜」完全淨係取決於而家呢刻嘅狀態，而家呢刻打前嗰啲時間點嘅狀態唔會影響下一刻嘅狀態係乜。技術啲噉講嘅話，馬可夫性質可以用以下噉嘅形式表達：

當中  意係話「無論  處於邊個可能數值都好，條式都會成立」。
一條馬可夫鏈可以用最少兩種方法嚟表示：一方面，馬可夫鏈可以畫做好似附圖 1 噉嘅有向圖，即係話幅圖有若干個頂點，頂點之間有啲箭咀表示頂點之間可以點樣變化，而每個箭咀都褦住個喺 0 同 1 之間嘅數，表示個箭咀指定嘅嗰種狀態轉移發生嘅概率，當中可以有頂點係有箭咀指住自己嘅，表示嗰啲頂點有可能轉移返去自己嗰度；另一方面，馬可夫鏈又可以寫做好似附圖 2 噉嘅轉移矩陣，即係話畫返個  嘅矩陣  俾條  鏈，當中  係啲可能狀態嘅數量，矩陣打戙行表示「而家啲狀態」，打橫行表示「跟住落嚟啲狀態」，而啲矩陣嘅每個元素都係一個 。技術性啲噉講，將馬可夫鏈寫做矩陣令到研究者有得用線性代數嚟做馬可夫鏈相關嘅運算。

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

特性 

馬可夫鏈可以具有以下呢啲數學特性：
聯合概率分佈：攞一條馬可夫鏈，有  個觀察到嘅值，條鏈啲狀態嘅聯合概率分佈可以表示成：

用日常用語講嘅話，想像家陣時間消逝，個系統經歷咗一連串  個狀態位，每個位嘅狀態係 。係噉「會出一串噉嘅狀態」嘅概率，等如初始個狀態嘅概率一路乘上啲條件轉移概率；每轉一吓乘一次，所以連乘  咁多次。
不可約性：簡單噉講，即係話每個狀態都有可能喺有限步數內轉移去任何一個其他可能狀態嗰度。定義上，不可約性即係話想像有條鏈 ，
，
有個概率  俾某條轉移路徑由  去  嘅。 

週期：想像有條馬可夫鏈其中有個狀態 ，如果話「 嘅週期係  咁多」，意思即係話一旦離開咗 ，要返去  需要經過嘅時間長度  實會係  嘅倍數；如果 ，噉狀態  就算係冇週期性嘅。
... 等等。

即逝常返 

即逝性同常返性係用嚟描述馬可夫鏈嘅狀態嘅兩個特性。家吓設返回時間 ， 表示「離開咗狀態  之後，最少需要幾耐時間先會返返  狀態」；攞式嚟表示即係：

即逝性同常返性嘅定義如下：
如果有個狀態 ，一旦離開咗個狀態，就有機會永遠都唔再返去嗰個狀態嘅－，噉呢個狀態就算係即逝嘅；
相反嚟講，如果有個狀態係一旦離開咗最後實會返去一次嘅－，就算平均嚟睇係要無限時間都好，噉呢個狀態都算係常返嘅。
常返性又有得再細分做正常返同零常返：設平均返回時間 ，對於狀態  嚟講： 
，即係個平均返回時間  係一個有限值，噉個狀態  係「正常返嘅」；
，即係個平均返回時間  係無限大，噉個狀態  係「零常返嘅」。
呢兩個特性亦都可以攞嚟形容一條馬可夫鏈：若果有條馬可夫鏈啲狀態冚唪唥都係常返嘅，噉條鏈就可以叫做常返嘅鏈；同一道理，如果條鏈啲狀態冚唪唥都係正常返嘅，噉條鏈可以叫做正常返嘅鏈。

靜止分佈 

靜止分佈係馬可夫鏈研究上嘅一個重要概念：假想有個概率分佈  基於狀態空間 －簡單講嘅話，即係  表示緊「响每個時間點 ，每個狀態有幾大概率係條鏈身處嘅狀態」；如果話  係一個靜止分佈，意思即係話以下條式成立：
，
簡化噉講嘅話，
 係指「而家呢個時間點處於  嘅概率」；
 係指「跟住嗰個時間點處於  嘅概率」；
喺呢種情況下，條馬可夫鏈會「靜止」－雖然狀態係有可能變化，但成條鏈都唔會隨時間而演變，無論時間過咗幾耐，每個可能狀態成為條鏈嘅現時狀態嘅概率都唔會變。

向量表示
如果用向量同矩陣嚟想像嘅話，一個靜止分佈會係一個向量 ，而以下呢條式成立：

當中  係條馬可夫鏈嘅轉移矩陣。想像家陣有條三個狀態嘅馬可夫鏈，設個向量  做一個分佈嚟表達條鏈嘅狀態，又設時間點  而條鏈家陣處於第一個狀態，，跟住再計

例如設

噉  得出嘅新向量如下：

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

呢個向量就反映咗條馬可夫鏈嘅靜止分佈。可建立方法 

馬可夫鏈喺科學上相當有用：想像有位科學家，佢將研究緊嘅系統抽象化噉諗做一條馬可夫鏈；喺呢個過程當中，研究者會用演算法嚟建立一條馬可夫鏈，由過往嘅數據嗰度估計出「個系統有邊啲狀態」同埋「每對狀態之間嘅轉移概率係幾多」等嘅參數。如果最後得出嗰條馬可夫鏈有返咁上下準確－柞轉移概率有返咁上下準，條鏈就算係大致噉模擬緊個系統，於是嗰位科學家第時就可以攞條馬可夫鏈嚟預計嗰個系統嘅行為，包括係答以下呢啲問題：
有一串特定嘅狀態串連，呢串狀態串連發生嘅概率係幾多？
攞其中一個狀態，個系統保持喺呢個狀態度嘅概率係幾多？
攞其中一個狀態，個系統預期會維持喺呢個狀態幾耐？
... 等等。

蒙地卡羅方法 

馬可夫鏈蒙地卡羅係一系列統計學上成日用嘅演算法，建基於蒙地卡羅方法，做到由數據嗰度建立一條馬可夫鏈嚟表達一個系統嘅狀態，跟手再靠用條馬可夫鏈做模擬嚟搵出想要嘅概率分佈。當中吉布斯抽樣係最基本嗰種馬可夫鏈蒙地卡羅做法。吉布斯抽樣最簡單嗰個版本如下：
想像家陣有一個聯合概率分佈，，反映緊一對變數之間嘅概率分佈，研究者唔知呢個聯合概率分佈係乜樣；
研究者用  同  呢兩個條件概率數值嚟計數－喺實際應用上，呢啲條件概率數值可以輕易噉由數據嗰度計到出嚟。用虛擬碼寫出嚟嘅話，吉布斯抽樣做嘅嘢係噉嘅：
  初始化
  迴圈，for j = 1, 2, 3... do
    抽樣計 
    抽樣計 
  end for    
搵到嗮每對可能狀態之間嘅 同 之後，就可以估計到嗰兩個變數之間嘅聯合概率分佈；
當個研究者搵到嗮每對可能狀態之間嘅聯合概率分佈，佢就可以知道啲轉移概率嘅數值。

最大似然估計 

喺統計模型上常用嘅最大似然估計都可以攞嚟由數據嗰度估計馬可夫鏈啲參數嘅數值。用一句嘢概括嘅話，最大似然估計所做嘅係搵出一柞參數數值，而呢柞參數數值係能夠令「得到手上呢柞數據」嘅概率最大化嘅。用數學啲嘅方法嚟表示嘅話，一排  個狀態嘅集合 ，攞  嚟表示序號嘅，要建立一個馬可夫鏈模型畀佢嘅話，即係要設啲參數，令以下條式出嘅嗰個數值  有咁大得咁大：

；

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

當中  係某款初始狀態出現嘅次數， 係撞親某狀態  前提下有後續狀態  嘅次數。有咗條式之後，就可以用程式化嘅方法嚟逐步改變啲參數令  有咁大得咁大，譬如藉助爬山演算法等數學最佳化技術。

進階類型

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

離散時間 

離散時間馬可夫鏈係最基本嗰種馬可夫鏈，指條鏈嘅時間係一個離散性變數：用日常用語講，「離散」即係話「時間點」呢個變數嘅每個可能數值之間都有啲窿窿罅罅喺度，是但攞一個可能嘅時間點數值  嚟睇， 同 之間並冇任何嘅可能時間點數值，個時間點數值淨係會一吓一吓噉由上一個數值跳去下一個數值；用集合論嘅語言嚟講嘅話，即係話包含可能時間點  嗰個集合係一個可數集，

連續時間 

連續時間馬可夫鏈將離散時間馬可夫鏈嘅時間變成一個連續性變數：用日常用語講，「連續」即係話「時間點」呢個變數嘅每個可能數值之間都冇窿罅，是但攞一個可能嘅時間點數值  嚟睇， 同 之間會有無限個可能嘅時間點數值，所以時間點呢個變數可以小數點後有無限咁多個位都得。要數學性噉定義連續時間馬可夫鏈，可以用以下嘅做法：
設  做一個隨機變數，表示條馬可夫鏈喺時間點  嘅狀態；
假設到咗時間點 ，條鏈處於狀態 ；
想像有個正數 ， 而 ，打前嗰啲時間點嘅狀態唔會影響跟住落嚟變咩狀態，而隨住 ，無論  同  係乜都好，以下嘅嘢都會成立：

當中  係卡羅內卡 δ； 反映由  去  嘅轉移發生得有幾快， 數值愈高就表示場轉移發生得愈快； 係細 O 符號。

隱馬可夫模型 

隱馬可夫模型係馬可夫鏈嘅一種，指條鏈將個系統想像成有一部份嘅狀態係所謂嘅隱藏狀態－顧名思義，隱藏狀態係研究者觀察唔到嘅，不過研究者有得靠觀察唔係隱藏嗰啲狀態嚟攞到有關隱藏狀態嘅資訊。定義上，設  同  做兩個隨機過程，，如果話  共同組成一條隱馬可夫鏈，即係話以下呢幾點成立：
 係一個馬可夫過程，不過啲狀態係不可知嘅；
無論  係幾多都好，
當中  係可量集。
舉個具體啲嘅例子說明，想像家陣有間房，房入面有三個罌，嗌呢三個罌做 、 同 ，每個罌都有波喺入面，啲波分 4 款，，唔同款色水唔同，而三個罌彼此之間喺「入面唔同款嘅波之間嘅數量比例」上唔一樣；又想像間房入面有個人，喺每個時間點，佢都會由三個罌當中揀一個，然後由嗰個罌度抽一個波出嚟，再將個波掟出嚟俾人睇，跟住再將個波擺返入去本來所屬嗰個罌度；研究者唔能夠直接睇到間房入面嘅事，但佢能夠睇到出嗰個波係邊個款－喺每個時間點 ，「揀咗邊個罌」係個隱藏狀態，但「出咗個乜款嘅波」係一個觀察得到嘅狀態，就好似附圖 3 噉樣。假想個研究者知每個罌入面唔同款嘅波之間嘅數量比例，佢會有能力由「出嗰個波嘅款」估計「個波係由邊個罌嗰度抽出嚟」嘅－攞到有關隱藏狀態嘅資訊。

一個隱馬可夫模型嘅參數同一道理可以靠由過往數據嗰度做最大似然估計等嘅最佳化工序嚟得出。呢種模型喺好多領域都好有用，可以攞嚟模擬一啲唔係完全觀察到嘅現象，例如運算金融學呢個領域就會用到隱馬可夫模型。

馬可夫決策過程 

馬可夫決策過程可以算係馬可夫鏈嘅一個擴張版，指條馬可夫鏈當中加咗決策嘅機制：例如係以下呢幅圖當中嘅馬可夫決策過程噉；個過程模擬咗一隻簡單遊戲嘅虛擬世界，個虛擬世界有三個狀態，喺每一個狀態當中，玩家都有兩個可能嘅選擇同埋相應嘅效益，而每個選擇有若干概率會令到個世界變成另外一個狀態。

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

齋用數字嘅話：

由國際象棋嘅例子可以睇得出，一隻隻遊戲可以抽象噉想像成馬可夫決策過程，而事實係，喺教人工智能玩遊戲嘅技術裏面成日都會用到馬可夫決策過程－研究者會教個人工智能程式由過往嘅數據估計個馬可夫決策過程嘅參數，令個程式能夠好似有智能噉捉國際象棋同第啲棋類遊戲。

應用 

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

物理學：首先，熱力學同統計力學上都會用到馬可夫鏈模型，因為呢啲領域成日都要處理一啲隨機性而且狀態又會係噉變化嘅系統；簡單講，熱同能量嘅傳遞相當大程度上係受到粒子嗰啲隨機郁動主宰嘅。
化學：化學反應好多時都係會發生喺一個狀態會係噉變化嘅系統，而呢啲狀態嘅特性都會影響化學反應嘅進行，而且化學反應又會引致狀態變化；因為噉，化學上嘅研究有陣時會將做緊化學反應嘅系統想像成一條條嘅馬可夫鏈。
生物學：一隻生物或者一隻生物嘅某啲部位可以想像成狀態會係噉變化嘅系統嚟模擬；包括親緣關係學、生物資訊科學、神經科學同病毒學。
人工智能：馬古夫鏈喺人工智能上受到廣泛嘅採用；最基本上，人工智能做嘅係想機械展示出智能，而人工智能研究者成日會教電腦將思考緊嘅現象用馬可夫鏈嚟模擬，令電腦做出好似有智能噉嘅行為。
經濟學同金融學：有好多同呢啲領域相關嘅現象都類似馬可夫鏈，例如有研究指，股價嘅上上落落可以大致上用隨機漫步嚟模擬；除此之外，亦都有研究試過用馬可夫鏈嚟模擬商業週期。
遊戲：有好多遊戲都或多或少噉帶有隨機性，例如大富翁等嘅好多枱上遊戲都會涉及玩家用擲骰仔等嘅方法嚟決定遊戲跟住發生乜嘢事，所以遊戲嘅狀態會有隨機性嘅變化；於是研究遊戲嘅人可以用馬可夫鏈嚟做模擬呢啲遊戲嘅數學模型。
運動：原則上，運動係遊戲嘅一種，都係涉及一班人跟住規則嚟交鋒；例如棒球就俾人指話可以想像成馬可夫鏈，而交戰雙方兩隊啲球員嘅實力－跑得有幾快或者擊球有幾準呀噉－會決定轉移概率。
音樂
資訊理論
... 等等。

文獻 

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
瓣瓣掂玩遊戲
詞性標注

考

拎 

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.

或然率論
機械學習