馬爾可夫鏈的提出來(lái)自俄國(guó)數(shù)學(xué)家安德雷·馬爾可夫（Андрей Андреевич Марков）。馬爾可夫在1906-1907年間發(fā)表的研究中為了證明隨機(jī)變量間的獨(dú)立性不是弱大數(shù)定律（weak law of large numbers）和中心極限定理（central limit theorem）成立的必要條件，構(gòu)造了一個(gè)按條件概率相互依賴(lài)的隨機(jī)過(guò)程，并證明其在一定條件下收斂于一組向量，該隨機(jī)過(guò)程被后世稱(chēng)為馬爾可夫鏈     。

在馬爾可夫鏈被提出之后，Tatiana Afanasyeva和保羅·埃倫費(fèi)斯特（Paul Ehrenfest）在1907年使用馬爾可夫鏈建立了Ehrenfest擴(kuò)散模型（Ehrenfest model of diffusion）   。1912年亨利·龐加萊（Jules Henri Poincaré）研究了有限群上的馬爾可夫鏈并得到了龐加萊不等式（Poincaré inequality）   。

1931年，安德雷·柯?tīng)柲缏宸?/a>（Андрей Николаевич Колмогоров）在對(duì)擴(kuò)散問(wèn)題的研究中將馬爾可夫鏈推廣至連續(xù)指數(shù)集得到了連續(xù)時(shí)間馬爾可夫鏈，并推出了其聯(lián)合分布函數(shù)的計(jì)算公式   。獨(dú)立于柯?tīng)柲缏宸颍?926年，Sydney Chapman在研究布朗運(yùn)動(dòng)時(shí)也得到了該計(jì)算公式，即后來(lái)的Chapman-Kolmogorov等式   。二十世紀(jì)50年代，前蘇聯(lián)數(shù)學(xué)家Eugene Borisovich Dynkin完善了柯?tīng)柲缏宸虻睦碚摬⑼ㄟ^(guò)Dynkin公式（Dynkin formula）將平穩(wěn)馬爾可夫過(guò)程與鞅過(guò)程（martingale process）相聯(lián)系   。此后以馬爾可夫鏈和馬爾可夫過(guò)程為基礎(chǔ)，各類(lèi)馬爾可夫模型被相繼提出并在實(shí)際問(wèn)題中得到應(yīng)用了     。

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈?zhǔn)且唤M具有馬爾可夫性質(zhì)的離散隨機(jī)變量的集合。具體地，對(duì)概率空間 內(nèi)以一維可數(shù)集為指數(shù)集（index set） 的隨機(jī)變量集合 ，若隨機(jī)變量的取值都在可數(shù)集內(nèi)： ，且隨機(jī)變量的條件概率滿足如下關(guān)系   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

則 被稱(chēng)為馬爾可夫鏈，可數(shù)集 被稱(chēng)為狀態(tài)空間（state space），馬爾可夫鏈在狀態(tài)空間內(nèi)的取值稱(chēng)為狀態(tài)   。這里定義的馬爾可夫鏈?zhǔn)请x散時(shí)間馬爾可夫鏈（Discrete-Time MC, DTMC），其具有連續(xù)指數(shù)集的情形雖然被稱(chēng)為連續(xù)時(shí)間馬爾可夫鏈（Continuous-Time MC, CTMC），但在本質(zhì)上是馬爾可夫過(guò)程（Markov process）   。常見(jiàn)地，馬爾可夫鏈的指數(shù)集被稱(chēng)為“步”或“時(shí)間步（time-step）”   。

馬爾可夫鏈

上式在定義馬爾可夫鏈的同時(shí)定義了馬爾可夫性質(zhì)，該性質(zhì)也被稱(chēng)為“無(wú)記憶性（memorylessness）”，即下一步的隨機(jī)變量 在給定其當(dāng)前步隨機(jī)變量 后與其余的隨機(jī)變量條件獨(dú)立（conditionally independent）：   。在此基礎(chǔ)上，馬爾可夫鏈具有強(qiáng)馬爾可夫性（strong Markov property），即對(duì)任意的停時(shí)（ stopping time），馬爾可夫鏈在停時(shí)前后的狀態(tài)相互獨(dú)立   。

n-階馬爾可夫鏈（n-order Markov chain）

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

馬爾可夫鏈

按上式，傳統(tǒng)的馬爾可夫鏈可以認(rèn)為是1-階馬爾可夫鏈   。由馬爾可夫性質(zhì)可得，將多個(gè)馬爾可夫鏈作為組元可以得到n-階的馬爾可夫鏈。

轉(zhuǎn)移理論

馬爾可夫鏈中隨機(jī)變量的狀態(tài)隨時(shí)間步的變化被稱(chēng)為演變（evolution）或轉(zhuǎn)移（transition）。這里介紹描述馬爾可夫鏈結(jié)構(gòu)的兩種途徑，即轉(zhuǎn)移矩陣和轉(zhuǎn)移圖，并定義了馬爾可夫鏈在轉(zhuǎn)移過(guò)程中表現(xiàn)出的性質(zhì)。

轉(zhuǎn)移概率 （transition probability）與轉(zhuǎn)移矩陣（transition matrix）

馬爾可夫鏈中隨機(jī)變量間的條件概率可定義為如下形式的（單步）轉(zhuǎn)移概率和n-步轉(zhuǎn)移概率   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

式中下標(biāo) 表示第n步的轉(zhuǎn)移。由馬爾可夫性質(zhì)可知，在給定初始概率 后，轉(zhuǎn)移概率的連續(xù)乘法可以表示馬爾可夫鏈的有限維分布（finite-dimensional distribution）   ：

馬爾可夫鏈

馬爾可夫鏈

式中的 為樣本軌道（sample path），即馬爾可夫鏈每步的取值   。對(duì)n-步轉(zhuǎn)移概率，由Chapman–Kolmogorov等式可知，其值為所有樣本軌道的總和   ：

馬爾可夫鏈

上式表明，馬爾可夫鏈直接演變n步等價(jià)于其先演變n-k步，再演變k步（k處于該馬爾可夫鏈的狀態(tài)空間內(nèi)）。n-步轉(zhuǎn)移概率與初始概率的乘積被稱(chēng)為該狀態(tài)的絕對(duì)概率。

若一個(gè)馬爾可夫鏈的狀態(tài)空間是有限的，則可在單步演變中將所有狀態(tài)的轉(zhuǎn)移概率按矩陣排列，得到轉(zhuǎn)移矩陣   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈的轉(zhuǎn)移矩陣是右隨機(jī)矩陣（right stochastic matrix），矩陣的第 行表示 時(shí) 取所有可能狀態(tài)的概率（離散分布），因此馬爾可夫鏈完全決定轉(zhuǎn)移矩陣，轉(zhuǎn)移矩陣也完全決定馬爾可夫鏈   。由概率分布的性質(zhì)可得，轉(zhuǎn)移矩陣是一個(gè)正定矩陣，且每行元素之和等于1： 。

馬爾可夫鏈

馬爾可夫鏈

按相同的方式也可定義n-步轉(zhuǎn)移矩陣： ，由n-步轉(zhuǎn)移概率的性質(zhì)（Chapman–Kolmogorov等式）可知，n-步轉(zhuǎn)移矩陣是其之前所有轉(zhuǎn)移矩陣的連續(xù)矩陣乘法：   。

轉(zhuǎn)移圖（transition graph）

1. 可達(dá)（accessible）與連通（communicate）

馬爾可夫鏈的演變可以按圖（graph）結(jié)構(gòu)，表示為轉(zhuǎn)移圖（transition graph），圖中的每條邊都被賦予一個(gè)轉(zhuǎn)移概率。通過(guò)轉(zhuǎn)移圖可引入“可達(dá)”和“連通”的概念：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

若對(duì)馬爾可夫鏈中的狀態(tài) 有： ，即采樣路徑上的所有轉(zhuǎn)移概率不為0，則狀態(tài) 是狀態(tài) 的可達(dá)狀態(tài)，在轉(zhuǎn)移圖中表示為有向連接： 。如果 互為可達(dá)狀態(tài)，則二者是連通的，在轉(zhuǎn)移圖中形成閉合回路，記為   。由定義，可達(dá)與連通可以是間接的，即不必在單個(gè)時(shí)間步完成。

連通是一組等價(jià)關(guān)系，因此可以構(gòu)建等價(jià)類(lèi)（equivalence classes），在馬爾可夫鏈中，包含盡可能多狀態(tài)的等價(jià)類(lèi)被稱(chēng)為連通類(lèi)（communicating class）   。

2. 閉合集（closed set）與吸收態(tài)（absorbing state）

馬爾可夫鏈

給定狀態(tài)空間的一個(gè)子集，若馬爾可夫鏈進(jìn)入該子集后無(wú)法離開(kāi)： ，則該子集是閉合的，稱(chēng)為閉合集，一個(gè)閉合集外部的所有狀態(tài)都不是其可達(dá)狀態(tài)。若閉合集中只有一個(gè)狀態(tài)，則該狀態(tài)是吸收態(tài)，在轉(zhuǎn)移圖中是一個(gè)概率為1的自環(huán)。一個(gè)閉合集可以包括一個(gè)或多個(gè)連通類(lèi)。

3. 轉(zhuǎn)移圖的例子

這里通過(guò)一個(gè)轉(zhuǎn)移圖的例子對(duì)上述概念進(jìn)行舉例說(shuō)明   ：

轉(zhuǎn)移圖的例子

馬爾可夫鏈

馬爾可夫鏈

由定義可知，該轉(zhuǎn)移圖包含了三個(gè)連通類(lèi)： 、三個(gè)閉合集： 和一個(gè)吸收態(tài)，即狀態(tài)6。注意到，在上述轉(zhuǎn)移圖中，馬爾可夫鏈從任意狀態(tài)出發(fā)最終都會(huì)進(jìn)入吸收態(tài)，這類(lèi)馬爾可夫鏈被稱(chēng)為吸收馬爾可夫鏈（absorbing Markov chain）   。

性質(zhì)

周期為3的不可約馬爾可夫鏈

這里對(duì)馬爾可夫鏈的4個(gè)性質(zhì)：不可約性、重現(xiàn)性、周期性和遍歷性進(jìn)行定義。與馬爾可夫性質(zhì)不同，這些性質(zhì)不是馬爾可夫鏈必然擁有的性質(zhì)，而是其在轉(zhuǎn)移過(guò)程中對(duì)其狀態(tài)表現(xiàn)出的性質(zhì)。上述性質(zhì)都是排他的，即不具有可約性的馬爾可夫鏈必然是不可約的，以此類(lèi)推。

不可約性（irreducibility）

如果一個(gè)馬爾可夫鏈的狀態(tài)空間僅有一個(gè)連通類(lèi)，即狀態(tài)空間的全體成員，則該馬爾可夫鏈?zhǔn)遣豢杉s的，否則馬爾可夫鏈具有可約性（reducibility）   。馬爾可夫鏈的不可約性意味著在其演變過(guò)程中，隨機(jī)變量可以在任意狀態(tài)間轉(zhuǎn)移   。

重現(xiàn)性（recurrence）

若馬爾可夫鏈在到達(dá)一個(gè)狀態(tài)后，在演變中能反復(fù)回到該狀態(tài)，則該狀態(tài)具有重現(xiàn)性，或該馬爾可夫鏈具有（局部）重現(xiàn)性，反之則具有瞬變性（transience）的。正式地，對(duì)狀態(tài)空間中的某個(gè)狀態(tài)，馬爾可夫鏈對(duì)一給定狀態(tài)的返回時(shí)間（return time）是其所有可能返回時(shí)間的下確界（infimum）   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

若 ，則該狀態(tài)不存在瞬變性或重現(xiàn)性的；若 ，則該狀態(tài)的瞬變性和重現(xiàn)性的判斷準(zhǔn)則如下   ：

馬爾可夫鏈

在時(shí)間步趨于無(wú)窮時(shí)，可重現(xiàn)狀態(tài)的返回概率（return probability）的和，即總訪問(wèn)次數(shù)的期望也趨于無(wú)窮：

馬爾可夫鏈

馬爾可夫鏈

此外，若狀態(tài) 具有重現(xiàn)性，則可計(jì)算其平均重現(xiàn)時(shí)間（mean recurrence time）   ：

馬爾可夫鏈

馬爾可夫鏈

若平均重現(xiàn)時(shí)間 ，該狀態(tài)是“正重現(xiàn)的（positive recurrent）”，否則為“零重現(xiàn)的（null recurrent）”   。若一個(gè)狀態(tài)是零重現(xiàn)的，那意味著馬爾可夫鏈兩次訪問(wèn)該狀態(tài)的時(shí)間間隔的期望是正無(wú)窮   。

由上述瞬變性和重現(xiàn)性的定義可有如下推論：

推論：對(duì)有限個(gè)狀態(tài)的馬爾可夫鏈，其至少有一個(gè)狀態(tài)是可重現(xiàn)的，且所有可重現(xiàn)狀態(tài)都是正可重現(xiàn)的 。

推論：若有限個(gè)狀態(tài)的馬爾可夫鏈?zhǔn)遣豢杉s的，則其所有狀態(tài)是正重現(xiàn)的。

推論：若狀態(tài)A是可重現(xiàn)的，且狀態(tài)B是A的可達(dá)狀態(tài)，則A與B是連通的，且B是可重現(xiàn)的 。

推論：若狀態(tài)B是A的可達(dá)狀態(tài)，且狀態(tài)B是吸收態(tài)，則B是可重現(xiàn)狀態(tài)，A是瞬變狀態(tài)。

推論：由正可重現(xiàn)狀態(tài)組成的集合是閉合集，但閉合集中的狀態(tài)未必是可重現(xiàn)狀態(tài) 。

推論：對(duì)有限個(gè)狀態(tài)的馬爾可夫鏈，其至少有一個(gè)狀態(tài)是可重現(xiàn)的，且所有可重現(xiàn)狀態(tài)都是正可重現(xiàn)的 。

推論：若有限個(gè)狀態(tài)的馬爾可夫鏈?zhǔn)遣豢杉s的，則其所有狀態(tài)是正重現(xiàn)的。

推論：若狀態(tài)A是可重現(xiàn)的，且狀態(tài)B是A的可達(dá)狀態(tài)，則A與B是連通的，且B是可重現(xiàn)的 。

推論：若狀態(tài)B是A的可達(dá)狀態(tài)，且狀態(tài)B是吸收態(tài)，則B是可重現(xiàn)狀態(tài)，A是瞬變狀態(tài)。

推論：由正可重現(xiàn)狀態(tài)組成的集合是閉合集，但閉合集中的狀態(tài)未必是可重現(xiàn)狀態(tài) 。

周期性（periodicity）

馬爾可夫鏈

一個(gè)正重現(xiàn)的馬爾可夫鏈可能具有周期性，即在其演變中，馬爾可夫鏈能夠按大于1的周期重現(xiàn)其狀態(tài)。正式地，給定具有正重現(xiàn)性的狀態(tài) ，其重現(xiàn)周期按如下方式計(jì)算   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

式中 表示取集合元素的最大公約數(shù)。舉例說(shuō)明，若在轉(zhuǎn)移圖中，一個(gè)馬爾可夫鏈重現(xiàn)某狀態(tài)需要的步數(shù)為 ，則其周期是3，即重現(xiàn)該狀態(tài)所需的最小步數(shù)。若按上式計(jì)算得到，該狀態(tài)具有周期性，若，該狀態(tài)具有非周期性（aperiodicity）   。由周期性的定義可有如下推論：

推論：吸收態(tài)是非周期性狀態(tài)。

推論：若狀態(tài)A與狀態(tài)B連通，則A與B周期相同 。

推論：若不可約的馬爾可夫鏈有周期性狀態(tài)A，則該馬爾可夫鏈的所有狀態(tài)為周期性狀態(tài) 。

推論：吸收態(tài)是非周期性狀態(tài)。

推論：若狀態(tài)A與狀態(tài)B連通，則A與B周期相同 。

推論：若不可約的馬爾可夫鏈有周期性狀態(tài)A，則該馬爾可夫鏈的所有狀態(tài)為周期性狀態(tài) 。

遍歷性（ergodicity）

若馬爾可夫鏈的一個(gè)狀態(tài)是正重現(xiàn)的和非周期的，則該狀態(tài)具有遍歷性   。若一個(gè)馬爾可夫鏈?zhǔn)遣豢蛇€原的，且有某個(gè)狀態(tài)是遍歷的，則該馬爾可夫鏈的所有狀態(tài)都是遍歷的，被稱(chēng)為遍歷鏈。由上述定義，遍歷性有如下推論：

推論：若狀態(tài)A是吸收態(tài)，且A是狀態(tài)B的可達(dá)狀態(tài)，則A是遍歷的，B不是遍歷的。

推論：若多個(gè)狀態(tài)的馬爾可夫鏈包含吸收態(tài)，則該馬爾可夫鏈不是遍歷鏈。

推論：若多個(gè)狀態(tài)的馬爾可夫鏈形成有向無(wú)環(huán)圖，或單個(gè)閉環(huán)，則該馬爾可夫鏈不是遍歷鏈。

推論：若狀態(tài)A是吸收態(tài)，且A是狀態(tài)B的可達(dá)狀態(tài)，則A是遍歷的，B不是遍歷的。

推論：若多個(gè)狀態(tài)的馬爾可夫鏈包含吸收態(tài)，則該馬爾可夫鏈不是遍歷鏈。

推論：若多個(gè)狀態(tài)的馬爾可夫鏈形成有向無(wú)環(huán)圖，或單個(gè)閉環(huán)，則該馬爾可夫鏈不是遍歷鏈。

遍歷鏈?zhǔn)欠侵芷诘钠椒€(wěn)馬爾可夫鏈，有長(zhǎng)時(shí)間尺度下的穩(wěn)態(tài)行為，因此是被廣泛研究和應(yīng)用的馬爾可夫鏈     。

穩(wěn)態(tài)分析

這里介紹馬爾可夫鏈的長(zhǎng)時(shí)間尺度行為的描述，即平穩(wěn)分布和極限分布，并定義平穩(wěn)馬爾可夫鏈。

平穩(wěn)分布（stationary distribution）

馬爾可夫鏈

給定一個(gè)馬爾可夫鏈，若在其狀態(tài)空間存在概率分布 ，且該分布滿足以下條件：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

則 是該馬爾可夫鏈的平穩(wěn)分布。式中 是轉(zhuǎn)移矩陣和轉(zhuǎn)移概率，等價(jià)符號(hào)右側(cè)的線性方程組被稱(chēng)為平衡方程（balance equation）。進(jìn)一步地，若馬爾可夫鏈的平穩(wěn)分布存在，且其初始分布是平穩(wěn)分布，則該馬爾可夫鏈處于穩(wěn)態(tài)（steady state）   。從幾何觀點(diǎn)，考慮馬爾可夫鏈的平穩(wěn)分布有 ，因此該分布的支撐集是一個(gè)正單純形（standard simplex）。

馬爾可夫鏈

對(duì)不可約的馬爾可夫鏈，當(dāng)且僅當(dāng)其存在唯一平穩(wěn)分布，即平衡方程在正單純形上有唯一解時(shí)，該馬爾可夫鏈?zhǔn)钦噩F(xiàn)的，且平穩(wěn)分布有如下表示     ：

馬爾可夫鏈

上述結(jié)論被稱(chēng)為平穩(wěn)分布準(zhǔn)則（stationary distribution criterion）   。對(duì)不可約和可重現(xiàn)的馬爾可夫鏈，可證明其存在除尺度外唯一的不變測(cè)度（invariant measure），若該馬爾可夫鏈?zhǔn)钦噩F(xiàn)的，則不變測(cè)度的尺度可以歸一化并得到平穩(wěn)分布   ，因此馬爾可夫鏈存在平穩(wěn)分布的充要條件是其存在正重現(xiàn)狀態(tài)。此外通過(guò)舉例可知，若一個(gè)馬爾可夫鏈包含多個(gè)由正重現(xiàn)狀態(tài)組成的連通類(lèi)（由性質(zhì)可知它們都是閉合集，所以該馬爾可夫鏈不是正重現(xiàn)的），則每個(gè)連通類(lèi)都擁有一個(gè)平穩(wěn)分布，且演變得到的穩(wěn)態(tài)取決于初始分布。

極限分布 （limiting distribution）

馬爾可夫鏈

馬爾可夫鏈

若一個(gè)馬爾可夫鏈的狀態(tài)空間存在概率分布

1. 極限定理（limiting theorem）

兩個(gè)獨(dú)立的非周期平穩(wěn)馬爾可夫鏈，即遍歷鏈如果有相同的轉(zhuǎn)移矩陣，那么當(dāng)時(shí)間步趨于無(wú)窮時(shí)，兩者極限分布間的差異趨于0。按隨機(jī)過(guò)程中的耦合（coupling）理論，該結(jié)論的表述為：對(duì)狀態(tài)空間相同的遍歷鏈 ，給定任意初始分布后有   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

式中 表示上確界（supremum）?？紤]平穩(wěn)分布的性質(zhì)，該結(jié)論有推論：對(duì)遍歷鏈 ，當(dāng)時(shí)間步趨于無(wú)窮時(shí)，其極限分布趨于平穩(wěn)分布   ：

馬爾可夫鏈

該結(jié)論有時(shí)被稱(chēng)為馬爾可夫鏈的極限定理（limit theorem of Markov chain），表明若馬爾可夫鏈?zhǔn)潜闅v的，則其極限分布是平穩(wěn)分布。對(duì)一個(gè)不可約和非周期的馬爾可夫鏈，其是遍歷鏈等價(jià)于其極限分布存在，也等價(jià)于其平穩(wěn)分布存在     。

2. 遍歷定理（ergodic theorem）

若一個(gè)馬爾可夫鏈為遍歷鏈，則由遍歷定理，其對(duì)某一狀態(tài)的訪問(wèn)次數(shù)與時(shí)間步的比值，在時(shí)間步趨于無(wú)窮時(shí)趨近于平均重現(xiàn)時(shí)間的倒數(shù)，即該狀態(tài)的平穩(wěn)分布或極限分布   ：

馬爾可夫鏈

遍歷定理的證明依賴(lài)于強(qiáng)大數(shù)定律（Strong Law of Large Numbers, SLLN），表明遍歷鏈無(wú)論初始分布如何，在經(jīng)過(guò)足夠長(zhǎng)的演變后，對(duì)其中一個(gè)隨機(jī)變量進(jìn)行多次觀測(cè)（極限定理）和對(duì)多個(gè)隨機(jī)變量進(jìn)行一次觀測(cè)（上式左側(cè)）都可以得到極限分布的近似   。由于遍歷鏈滿足極限定理和遍歷定理，因此MCMC通過(guò)構(gòu)建遍歷鏈以確保其在迭代中收斂于平穩(wěn)分布   。

平穩(wěn)馬爾可夫鏈（stationary Markov chain）

若一個(gè)馬爾可夫鏈擁有唯一的平穩(wěn)分布且極限分布收斂于平穩(wěn)分布，則按定義等價(jià)于，該馬爾可夫鏈?zhǔn)瞧椒€(wěn)馬爾可夫鏈   。平穩(wěn)馬爾可夫鏈?zhǔn)菄?yán)格平穩(wěn)隨機(jī)過(guò)程，其演變與時(shí)間順序無(wú)關(guān)   ：

馬爾可夫鏈

由極限定理可知，遍歷鏈?zhǔn)瞧椒€(wěn)馬爾可夫鏈。此外由上述定義，平穩(wěn)馬爾可夫鏈的轉(zhuǎn)移矩陣是常數(shù)矩陣，n-步轉(zhuǎn)移矩陣則是該常數(shù)矩陣的n次冪   。平穩(wěn)馬爾可夫鏈也被稱(chēng)為齊次馬爾可夫鏈（time-homogeneous Markov chain）與之對(duì)應(yīng)的，若馬爾可夫鏈不滿足上述條件，則被稱(chēng)為非平穩(wěn)馬爾可夫鏈（non-stationary Markvo chain）或非齊次馬爾可夫鏈（time-inhomogeneous Markov chain）   。

一個(gè)平穩(wěn)馬爾可夫鏈也是可逆馬爾可夫鏈 （reversible Markov chain），即其平穩(wěn)分布對(duì)任意兩個(gè)狀態(tài)滿足細(xì)致平衡（detailed balance）條件   ：

馬爾可夫鏈

上述結(jié)論也可表述為平穩(wěn)馬爾可夫鏈與可逆馬爾可夫鏈互為充要條件。在馬爾可夫鏈蒙特卡羅（Markvo chain Monte Carlo, MCMC） 中，構(gòu)建滿足細(xì)致平衡條件的可逆馬爾可夫鏈，是確保其以采樣分布為平穩(wěn)分布的方法   。

伯努利過(guò)程 （Bernoulli process）

馬爾可夫鏈

馬爾可夫鏈

伯努利過(guò)程也被稱(chēng)為二項(xiàng)馬可夫鏈（Binomial Markov chain），其建立過(guò)程如下：給定一系列相互獨(dú)立的“標(biāo)識(shí)”，每個(gè)標(biāo)識(shí)都是二項(xiàng)的，按概率 取正和負(fù)。令正隨機(jī)過(guò)程 表示n個(gè)標(biāo)識(shí)中有k個(gè)正標(biāo)識(shí)的概率，則其是一個(gè)伯努利過(guò)程，其中的隨機(jī)變量服從二項(xiàng)分布（binomialdistribution）   ：

由建立過(guò)程可知，增加的新標(biāo)識(shí)中正標(biāo)識(shí)的概率與先前正標(biāo)識(shí)的數(shù)量無(wú)關(guān)，具有馬爾可夫性質(zhì)，因此伯努利過(guò)程是一個(gè)馬爾可夫鏈   。

賭徒破產(chǎn)問(wèn)題（gambler's ruin）

馬爾可夫鏈

假設(shè)賭徒持有有限個(gè)籌碼在賭場(chǎng)下注，每次下注以概率 贏或輸一個(gè)籌碼，若賭徒不斷下注，則其持有的籌碼總數(shù)是一個(gè)馬爾可夫鏈，且有如下轉(zhuǎn)移矩陣   ：

馬爾可夫鏈

馬爾可夫鏈

賭徒輸光籌碼是吸收態(tài)，由一步分析（one-step analysis）可知，當(dāng) 時(shí)，該馬爾可夫鏈必然進(jìn)入吸收態(tài)，即賭徒無(wú)論持有多少籌碼，隨著賭注的進(jìn)行最終都會(huì)輸光。

隨機(jī)游走 （random walk）

馬爾可夫鏈

定義一系列獨(dú)立同分布（independent identically distributed, iid）的整數(shù)隨機(jī)變量 ，并定義如下隨機(jī)過(guò)程   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

則隨機(jī)過(guò)程 是整數(shù)集內(nèi)的隨機(jī)游走，而 是步長(zhǎng)。由于步長(zhǎng)是iid的，因此當(dāng)前步與先前步相互獨(dú)立，該隨機(jī)過(guò)程是馬爾可夫鏈   。伯努利過(guò)程和賭徒破產(chǎn)問(wèn)題都是隨機(jī)游走的特例   。

馬爾可夫鏈

馬爾可夫鏈

由上述隨機(jī)游走的例子可知，馬爾可夫鏈有一般性的構(gòu)建方法，具體地，若狀態(tài)空間 內(nèi)的隨機(jī)過(guò)程 有滿足形式   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

其中， ， 為空間 的iid隨機(jī)變量且獨(dú)立于 ，則隨機(jī)過(guò)程 是馬爾可夫鏈，其一步轉(zhuǎn)移概率為：   。該結(jié)論表明，馬爾可夫鏈可以由區(qū)間內(nèi)服從iid均勻分布的隨機(jī)變量（隨機(jī)數(shù)）進(jìn)行數(shù)值模擬   。

馬爾可夫過(guò)程（Markov process）

馬爾可夫過(guò)程也被稱(chēng)為連續(xù)時(shí)間馬爾可夫鏈，是馬爾可夫鏈或離散時(shí)間馬爾可夫鏈的推廣，其狀態(tài)空間是可數(shù)集，但一維指數(shù)集不再有可數(shù)集的限制，可以表示連續(xù)時(shí)間。馬爾可夫過(guò)程與馬爾可夫鏈的性質(zhì)是可以類(lèi)比的，其馬爾可夫性質(zhì)通常有如下表示   ：

馬爾可夫鏈

由于馬爾可夫過(guò)程的狀態(tài)空間是可數(shù)集，在連續(xù)時(shí)間下其樣本軌道幾乎必然（a.s.）是右連續(xù)的片段函數(shù)，因此馬爾可夫過(guò)程可以表示為跳躍過(guò)程（jump process）并與馬爾可夫鏈相聯(lián)系   ：

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

式中 是某個(gè)狀態(tài)的滯留時(shí)間（sojourn time）， 是順序的指數(shù)集成員（時(shí)間片段）。滿足上述關(guān)系的馬爾可夫鏈 和滯留時(shí)間 是跳躍過(guò)程 在有限個(gè)時(shí)間片段下的局部嵌入過(guò)程（locally embedded process）   。

馬爾可夫模型（Markov model）

馬爾可夫鏈或馬爾可夫過(guò)程不是唯一以馬爾可夫性質(zhì)為基礎(chǔ)建立的隨機(jī)過(guò)程，事實(shí)上，隱馬爾可夫模型、馬爾可夫決策過(guò)程、馬爾可夫隨機(jī)場(chǎng)等隨機(jī)過(guò)程/隨機(jī)模型都具有馬爾可夫性質(zhì)并被統(tǒng)稱(chēng)為馬爾可夫模型。這里對(duì)馬爾可夫模型的其它成員做簡(jiǎn)要介紹：

1. 隱馬爾可夫模型（Hidden Markov Model, HMM）

HMM是一個(gè)狀態(tài)空間不完全可見(jiàn)，即包含隱藏狀態(tài)（hidden status）的馬爾可夫鏈，HMM中可見(jiàn)的部分被稱(chēng)為輸出狀態(tài)（emission state），與隱藏狀態(tài)有關(guān)，但不足以形成完全的對(duì)應(yīng)關(guān)系。以語(yǔ)音識(shí)別（speech recognition）為例，需要識(shí)別的語(yǔ)句是不可見(jiàn)的隱藏狀態(tài)，接收的語(yǔ)音或音頻是和語(yǔ)句有關(guān)的輸出狀態(tài)，此時(shí)HMM常見(jiàn)的應(yīng)用是基于馬爾可夫性質(zhì)從語(yǔ)音輸入推出其對(duì)應(yīng)的語(yǔ)句，即從輸出狀態(tài)反解隱藏狀態(tài)   。

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

MDP是在狀態(tài)空間的基礎(chǔ)上引入了“動(dòng)作”的馬爾可夫鏈，即馬爾可夫鏈的轉(zhuǎn)移概率不僅與當(dāng)前狀態(tài)有關(guān)，也與當(dāng)前動(dòng)作有關(guān)。MDP的一個(gè)例子是下棋，智能體對(duì)下一步棋的決策取決于當(dāng)前的盤(pán)面和對(duì)手當(dāng)前的動(dòng)作，其中決策（policy）是狀態(tài)到動(dòng)作的映射。MDP是強(qiáng)化學(xué)習(xí)（reinforcement learning）方法的重要實(shí)現(xiàn)，被用于計(jì)算決策所得到的“回報(bào)”，即值函數(shù)（value function）。深度強(qiáng)化學(xué)習(xí)是使用深度學(xué)習(xí)（deep learning）方法求解值函數(shù)極大值所對(duì)應(yīng)決策的優(yōu)化過(guò)程   。MDP的推廣之一是部分可觀察馬爾可夫決策過(guò)程（partially observable Markov decision process, POMDP），即考慮了HMM中隱藏狀態(tài)和輸出狀態(tài)的MDP。

3. 馬爾可夫隨機(jī)場(chǎng)（Markov Random Field, MRF）

MRF是馬爾可夫鏈由一維指數(shù)集向高維空間的推廣。MRF的馬爾可夫性質(zhì)表現(xiàn)為其任意一個(gè)隨機(jī)變量的狀態(tài)僅由其所有鄰接隨機(jī)變量的狀態(tài)決定。 類(lèi)比馬爾可夫鏈中的有限維分布，MRF中隨機(jī)變量的聯(lián)合概率分布是所有包含該隨機(jī)變量的團(tuán)（cliques）的乘積。MRF最常見(jiàn)的例子是伊辛模型（Ising model）     。

哈里斯鏈（Harris chain）

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

馬爾可夫鏈

哈里斯鏈?zhǔn)邱R爾可夫鏈從可數(shù)狀態(tài)空間向連續(xù)狀態(tài)空間的推廣，給定可測(cè)空間上的平穩(wěn)馬爾可夫鏈，若對(duì)可測(cè)空間的任意子集和子集的返回時(shí)間，該馬爾可夫鏈滿足   ：

馬爾可夫鏈

馬爾可夫鏈

則該馬爾可夫鏈?zhǔn)枪锼箍芍噩F(xiàn)（Harris recurrent）的，被稱(chēng)為哈里斯鏈，式中的是可測(cè)空間的σ-有限測(cè)度（σ-finite measure）   。

MCMC

構(gòu)建以采樣分布為極限分布的馬爾可夫鏈?zhǔn)邱R爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo, MCMC）的核心步驟，MCMC通過(guò)在馬爾可夫鏈上運(yùn)行大量的時(shí)間步得到近似服從采樣分布的隨機(jī)數(shù)，并使用這些隨機(jī)數(shù)逼近求解目標(biāo)對(duì)采樣分布的數(shù)學(xué)期望     ：

馬爾可夫鏈

馬爾可夫鏈的極限分布性質(zhì)決定了MCMC是無(wú)偏估計(jì)（unbiased estimation），即采樣數(shù)趨于無(wú)窮時(shí)會(huì)得到求解目標(biāo)數(shù)學(xué)期望的真實(shí)值，這將MCMC與其替代方法，例如變分貝葉斯估計(jì)（variational Bayesian inference）相區(qū)分，后者計(jì)算量通常小于MCMC但無(wú)法得到無(wú)偏估計(jì)   。

其它

在物理學(xué)和化學(xué)中，馬爾可夫鏈和馬爾可夫過(guò)程被用于對(duì)動(dòng)力系統(tǒng)進(jìn)行建模，形成了馬爾可夫動(dòng)力學(xué)（Markov dynamics）   。 在排隊(duì)論（queueing theory）中，馬爾可夫鏈?zhǔn)桥抨?duì)過(guò)程的基本模型   。在信號(hào)處理方面，馬爾可夫鏈?zhǔn)且恍┬蛄袛?shù)據(jù)壓縮算法，例如Ziv-Lempel編碼的數(shù)學(xué)模型   ，在金融領(lǐng)域，馬爾可夫鏈模型被用于預(yù)測(cè)企業(yè)產(chǎn)品的市場(chǎng)占有率   。