馬爾可夫鏈檢視原始碼討論檢視歷史
| 馬爾可夫鏈 |
|
中文名: 馬爾可夫鏈 外文名: Markov chain 類 型: 隨機過程 提出者: Andrey A. Markov 提出時間: 1906年 學 科: 統計學 應 用: 數值模擬，機器學習 |
馬爾可夫鏈（Markov Chain, MC）是概率論和數理統計中具有馬爾可夫性質（Markov property）且存在於離散的指數集（index set）和狀態空間（state space）內的隨機過程（stochastic process）。適用於連續指數集的馬爾可夫鏈被稱為馬爾可夫過程（Markov process），但有時也被視為馬爾可夫鏈的子集，即連續時間馬爾可夫鏈（Continuous-Time MC, CTMC），與離散時間馬爾可夫鏈（Discrete-Time MC, DTMC）相對應，因此馬爾可夫鏈是一個較為寬泛的概念。 馬爾可夫鏈可通過轉移矩陣和轉移圖定義，除馬爾可夫性外，馬爾可夫鏈可能具有不可約性、常返性、周期性和遍歷性。一個不可約和正常返的馬爾可夫鏈是嚴格平穩的馬爾可夫鏈，擁有唯一的平穩分布。遍歷馬爾可夫鏈（ergodic MC）的極限分布收斂於其平穩分布。 馬爾可夫鏈可被應用於蒙特卡羅方法中，形成馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo, MCMC） ，也被用於動力系統、化學反應、排隊論、市場行為和信息檢索的數學建模。此外作為結構最簡單的馬爾可夫模型（Markov model），一些機器學習算法，例如隱馬爾可夫模型（Hidden Markov Model, HMM）、馬爾可夫隨機場（Markov Random Field, MRF）和馬爾可夫決策過程（Markov decision process, MDP）以馬爾可夫鏈為理論基礎。 馬爾可夫鏈的命名來自俄國數學家安德雷·馬爾可夫（Андрей Андреевич Марков）以紀念其首次提出馬爾可夫鏈和對其收斂性質所做的研究。[1]
歷史
馬爾可夫鏈的提出來自俄國數學家安德雷·馬爾可夫（Андрей Андреевич Марков）。馬爾可夫在1906-1907年間發表的研究中為了證明隨機變量間的獨立性不是弱大數定律（weak law of large numbers）和中心極限定理（central limit theorem）成立的必要條件，構造了一個按條件概率相互依賴的隨機過程，並證明其在一定條件下收斂於一組向量，該隨機過程被後世稱為馬爾可夫鏈。 在馬爾可夫鏈被提出之後，保羅·埃倫費斯特（Paul Ehrenfest）和Tatiana Afanasyeva在1907年使用馬爾可夫鏈建立了Ehrenfest擴散模型（Ehrenfest model of diffusion）。1912年亨利·龐加萊（Jules Henri Poincaré）研究了有限群上的馬爾可夫鏈並得到了龐加萊不等式（Poincaré inequality）。 1931年，安德雷·柯爾莫哥洛夫（Андрей Николаевич Колмогоров）在對擴散問題的研究中將馬爾可夫鏈推廣至連續指數集得到了連續時間馬爾可夫鏈，並推出了其聯合分布函數的計算公式。獨立於柯爾莫哥洛夫，1926年，Sydney Chapman在研究布朗運動時也得到了該計算公式，即後來的Chapman-Kolmogorov等式。 1953年，Nicholas Metropolis等通過構建馬爾可夫鏈完成了對流體目標分布函數的隨機模擬 ，該方法在1970年由Wilfred K. Hastings進一步完善，並發展為現今的梅特羅波利斯-黑斯廷斯算法（Metropolis-Hastings algorithm）。 1957年，Richard Bellman通過離散隨機最優控制模型首次提出了馬爾可夫決策過程（Markov Decision Processes, MDP）。 1959-1962，前蘇聯數學家Eugene Borisovich Dynkin完善了柯爾莫哥洛夫的理論並通過Dynkin公式（Dynkin formula）將平穩馬爾可夫過程與鞅過程（martingale process）相聯繫。 此後以馬爾可夫鏈為基礎，更複雜的馬爾可夫模型（例如隱馬爾可夫模型 和馬爾可夫隨機場 ）被相繼提出，並在模式識別等實際問題中得到應用了。
定義
馬爾可夫鏈是一組具有馬爾可夫性質的離散隨機變量的集合。具體地，對概率空間 ，且隨機變量的條件概率滿足如下關係 ：
被称为状态空间（state space），马尔可夫链在状态空间内的取值称为状态。这里定义的马尔可夫链是离散时间马尔可夫链（Discrete-Time MC, DTMC），其具有连续指数集的情形虽然被称为连续时间马尔可夫链（Continuous-Time MC, CTMC），但在本质上是马尔可夫过程（Markov process）。常见地，马尔可夫链的指数集被称为“步”或“时间步（time-step）”。
上式在定義馬爾可夫鏈的同時定義了馬爾可夫性質，該性質也被稱為「無記憶性（memorylessness）」，即t+1步的隨機變量在給定第t步隨機變量後與其餘的隨機變量條件獨立（conditionally independent）：。在此基礎上，馬爾可夫鏈具有強馬爾可夫性（strong Markov property），即對任意的停時（ stopping time），馬爾可夫鏈在停時前後的狀態相互獨立。 解釋性例子 馬爾科夫鏈的一個常見例子是簡化的股票漲跌模型：若一天中某股票上漲，則明天該股票有概率p開始下跌，1-p繼續上漲；若一天中該股票下跌，則明天該股票有概率q開始上漲，1-q繼續下跌。該股票的漲跌情況是一個馬爾可夫鏈，且定義中各個概念在例子中有如下對應： 隨機變量：第t天該股票的狀態；狀態空間：「上漲」和「下跌」；指數集：天數。 條件概率關係：按定義，即便已知該股票的所有歷史狀態，其在某天的漲跌也僅與前一天的狀態有關。 無記憶性：該股票當天的表現僅與前一天有關，與其他歷史狀態無關（定義條件概率關係的同時定義了無記憶性）。 停時前後狀態相互獨立：取出該股票的漲跌記錄，然後從中截取一段，我們無法知道截取的是哪一段，因為截取點，即停時t前後的記錄（t-1和t+1）沒有依賴關係。 n-階馬爾可夫鏈（n-order Markov chain） n-階馬爾可夫鏈擁有n階的記憶性，可視為馬爾可夫鏈的推廣。類比馬爾可夫鏈的定義，n-階馬爾可夫鏈滿足如下條件： 按上式，傳統的馬爾可夫鏈可以認為是1-階馬爾可夫鏈。由馬爾可夫性質可得，將多個馬爾可夫鏈作為組元可以得到n-階的馬爾可夫鏈。 馬爾可夫鏈中隨機變量的狀態隨時間步的變化被稱為演變（evolution）或轉移（transition）。這裡介紹描述馬爾可夫鏈結構的兩種途徑，即轉移矩陣和轉移圖，並定義了馬爾可夫鏈在轉移過程中表現出的性質。 轉移概率（transition probability）與轉移矩陣（transition matrix） 主詞條：轉移矩陣 馬爾可夫鏈中隨機變量間的條件概率可定義為如下形式的（單步）轉移概率和n-步轉移概率 ：
后，转移概率的连续乘法可以表示马尔可夫链的有限维分布（finite-dimensional distribution）
：
为样本轨道（sample path），即马尔可夫链每步的取值。对n-步转移概率，由Chapman–Kolmogorov等式可知，其值为所有样本轨道的总和
： 上式表明，馬爾可夫鏈直接演變n步等價於其先演變n-k步，再演變k步（k處於該馬爾可夫鏈的狀態空間內）。n-步轉移概率與初始概率的乘積被稱為該狀態的絕對概率。 若一個馬爾可夫鏈的狀態空間是有限的，則可在單步演變中將所有狀態的轉移概率按矩陣排列，得到轉移矩陣 ：。 轉移圖（transition graph） 1. 可達（accessible）與連通（communicate） 馬爾可夫鏈的演變可以按圖（graph）結構，表示為轉移圖（transition graph），圖中的每條邊都被賦予一個轉移概率。通過轉移圖可引入「可達」和「連通」的概念： 若對馬爾可夫鏈中的狀態。由定義，可達與連通可以是間接的，即不必在單個時間步完成。 連通是一組等價關係，因此可以構建等價類（equivalence classes），在馬爾可夫鏈中，包含儘可能多狀態的等價類被稱為連通類（communicating class）。 2. 閉合集（closed set）與吸收態（absorbing state） 給定狀態空間的一個子集，若馬爾可夫鏈進入該子集後無法離開：
，则该子集是闭合的，称为闭合集，一个闭合集外部的所有状态都不是其可达状态。若闭合集中只有一个状态，则该状态是吸收态，在转移图中是一个概率为1的自环。一个闭合集可以包括一个或多个连通类。
3. 轉移圖的例子 這裡通過一個轉移圖的例子對上述概念進行舉例說明 ： 由定義可知，該轉移圖包含了三個連通類： 和一個吸收態，即狀態6。注意到，在上述轉移圖中，馬爾可夫鏈從任意狀態出發最終都會進入吸收態，這類馬爾可夫鏈被稱為吸收馬爾可夫鏈（absorbing Markov chain）。
性質
這裡對馬爾可夫鏈的4個性質：不可約性、常返性、周期性和遍歷性進行定義。與馬爾可夫性質不同，這些性質不是馬爾可夫鏈必然擁有的性質，而是其在轉移過程中對其狀態表現出的性質。上述性質都是排他的，即不具有可約性的馬爾可夫鏈必然是不可約的，以此類推。 不可約性（irreducibility） 如果一個馬爾可夫鏈的狀態空間僅有一個連通類，即狀態空間的全體成員，則該馬爾可夫鏈是不可約的，否則馬爾可夫鏈具有可約性（reducibility）。馬爾可夫鏈的不可約性意味着在其演變過程中，隨機變量可以在任意狀態間轉移。 常返性（recurrence） 若馬爾可夫鏈在到達一個狀態後，在演變中能反覆回到該狀態，則該狀態是常返狀態，或該馬爾可夫鏈具有（局部）常返性，反之則具有瞬變性（transience）的。正式地，對狀態空間中的某個狀態，馬爾可夫鏈對一給定狀態的返回時間（return time）是其所有可能返回時間的下確界（infimum） ：
，则该状态的瞬变性和常返性的判断准则如下
：
在时间步趋于无穷时，常返状态的返回概率（return probability）的和，即总访问次数的期望也趋于无穷： 具有常返性，则可计算其平均返回时间（mean recurrence time）
：
，该状态是“正常返的（positive recurrent）”，否则为“零常返的（null recurrent）”。若一个状态是零常返的，那意味着马尔可夫链两次访问该状态的时间间隔的期望是正无穷。
由上述瞬變性和常返性的定義可有如下推論： 推論：對有限個狀態的馬爾可夫鏈，其至少有一個常返狀態，且所有常返狀態都是正常返的。 推論：若有限個狀態的馬爾可夫鏈是不可約的，則其所有狀態是正常返的。 推論：若狀態A是可常返的，且狀態B是A的可達狀態，則A與B是連通的，且B是常返的。 推論：若狀態B是A的可達狀態，且狀態B是吸收態，則B是常返狀態，A是瞬變狀態。 推論：由正常返狀態組成的集合是閉合集，但閉合集中的狀態未必是常返狀態。 周期性（periodicity） 一個正常返的馬爾可夫鏈可能具有周期性，即在其演變中，馬爾可夫鏈能夠按大於1的周期常返其狀態。正式地，給定具有正常返的狀態
，其返回周期按如下方式计算
： ，該狀態具有非周期性（aperiodicity）。由周期性的定義可有如下推論： 推論：吸收態是非周期性狀態。 推論：若狀態A與狀態B連通，則A與B周期相同。 推論：若不可約的馬爾可夫鏈有周期性狀態A，則該馬爾可夫鏈的所有狀態為周期性狀態。 遍歷性（ergodicity） 若馬爾可夫鏈的一個狀態是正常返的和非周期的，則該狀態具有遍歷性。若一個馬爾可夫鏈是不可還原的，且有某個狀態是遍歷的，則該馬爾可夫鏈的所有狀態都是遍歷的，被稱為遍歷鏈。由上述定義，遍歷性有如下推論： 推論：若狀態A是吸收態，且A是狀態B的可達狀態，則A是遍歷的，B不是遍歷的。 推論：若多個狀態的馬爾可夫鏈包含吸收態，則該馬爾可夫鏈不是遍歷鏈。 推論：若多個狀態的馬爾可夫鏈形成有向無環圖，或單個閉環，則該馬爾可夫鏈不是遍歷鏈。 遍歷鏈是非周期的平穩馬爾可夫鏈，有長時間尺度下的穩態行為，因此是被廣泛研究和應用的馬爾可夫鏈。
穩態分析
這裡介紹馬爾可夫鏈的長時間尺度行為的描述，即平穩分布和極限分布，並定義平穩馬爾可夫鏈。 平穩分布（stationary distribution） 給定一個馬爾可夫鏈，若在其狀態空間存在概率分布
，且该分布满足以下条件： ，因此该分布的支撑集是一个正单纯形（standard simplex）。
對不可約的馬爾可夫鏈，當且僅當其存在唯一平穩分布，即平衡方程 ：
上述结论被称为平稳分布准则（stationary distribution criterion）。对不可约和常返的马尔可夫链，求解平衡方程可得到除尺度外唯一的特征向量，即不变测度（invariant measure），若该马尔可夫链是正常返的，则其平稳分布是求解平衡方程时得到的，特征值为1时的特征向量，即归一化后的不变测度
，因此馬爾可夫鏈存在平穩分布的充要條件是其存在正常返狀態。此外通過舉例可知，若一個馬爾可夫鏈包含多個由正常返狀態組成的連通類（由性質可知它們都是閉合集，所以該馬爾可夫鏈不是正常返的），則每個連通類都擁有一個平穩分布，且演變得到的穩態取決於初始分布。 極限分布（limiting distribution） 若一個馬爾可夫鏈的狀態空間存在概率分布 並滿足如下關係：
则该分布是马尔可夫链的极限分布。注意到极限分布的定义与初始分布无关，即对任意的初始分布，当时间步趋于无穷时，随机变量的概率分布趋于极限分布。按定义，极限分布一定是平稳分布，但反之不成立，例如周期性的马尔可夫链可能具有平稳分布，但周期性马尔可夫链不收敛于任何分布，其平稳分布不是极限分布。
1. 極限定理（limiting theorem） 兩個獨立的非周期平穩馬爾可夫鏈，即遍歷鏈如果有相同的轉移矩陣，那麼當時間步趨於無窮時，兩者極限分布間的差異趨於0。按隨機過程中的耦合（coupling）理論，該結論的表述為：對狀態空間相同的遍歷鏈
，给定任意初始分布后有
：
，当时间步趋于无穷时，其极限分布趋于平稳分布
：。 2. 遍歷定理（ergodic theorem） 若一個馬爾可夫鏈為遍歷鏈，則由遍歷定理，其對某一狀態的訪問次數與時間步的比值，在時間步趨於無窮時趨近於平均返回時間的倒數，即該狀態的平穩分布或極限分布 ：
遍历定理的证明依赖于强大数定律（Strong Law of Large Numbers, SLLN），表明遍历链无论初始分布如何，在经过足够长的演变后，对其中一个随机变量进行多次观测（极限定理）和对多个随机变量进行一次观测（上式左侧）都可以得到极限分布的近似。由于遍历链满足极限定理和遍历定理，因此MCMC通过构建遍历链以确保其在迭代中收敛于平稳分布。
平穩馬爾可夫鏈（stationary Markov chain） 若一個馬爾可夫鏈擁有唯一的平穩分布且極限分布收斂於平穩分布，則按定義等價於，該馬爾可夫鏈是平穩馬爾可夫鏈。平穩馬爾可夫鏈是嚴格平穩隨機過程，其演變與時間順序無關 ： 由極限定理可知，遍歷鏈是平穩馬爾可夫鏈。此外由上述定義，平穩馬爾可夫鏈的轉移矩陣是常數矩陣，n-步轉移矩陣則是該常數矩陣的n次冪。平穩馬爾可夫鏈也被稱為齊次馬爾可夫鏈（time-homogeneous Markov chain）與之對應的，若馬爾可夫鏈不滿足上述條件，則被稱為非平穩馬爾可夫鏈（non-stationary Markvo chain）或非齊次馬爾可夫鏈（time-inhomogeneous Markov chain）。 若平穩馬爾可夫鏈對其任意兩個狀態滿足細緻平衡（detailed balance）條件，則其具有可逆性，被稱為可逆馬爾可夫鏈（reversible Markov chain） ： 馬爾可夫鏈的可逆性是更嚴格的不可約性，即其不僅可以在任意狀態間轉移，且向各狀態轉移的概率是相等的，因此可逆馬爾可夫鏈是平穩馬爾可夫鏈的充分非必要條件。在馬爾可夫鏈蒙特卡羅（Markvo chain Monte Carlo, MCMC） 中，構建滿足細緻平衡條件的可逆馬爾可夫鏈，是確保其以採樣分布為平穩分布的方法。
特例
伯努利過程（Bernoulli process） 主詞條：伯努利過程 伯努利過程也被稱為二項馬可夫鏈（Binomial Markov chain），其建立過程如下：給定一系列相互獨立的「標識」，每個標識都是二項的，按概率 表示n個標識中有k個正標識的概率，則其是一個伯努利過程，其中的隨機變量服從二項分布（binomial distribution） ：
由建立过程可知，增加的新标识中正标识的概率与先前正标识的数量无关，具有马尔可夫性质，因此伯努利过程是一个马尔可夫链。
賭徒破產問題（gambler's ruin） 參見：賭徒輸光定理 假設賭徒持有有限個籌碼在賭場下注，每次下注以概率
赢或输一个筹码，若赌徒不断下注，则其持有的筹码总数是一个马尔可夫链，且有如下转移矩阵
：
时，该马尔可夫链必然进入吸收态，即赌徒无论持有多少筹码，随着赌注的进行最终都会输光。
隨機遊走（random walk） 主詞條：隨機遊走 定義一系列獨立同分布（independent identically distributed, iid）的整數隨機變量
，并定义如下随机过程
： 則隨機過程 是步長。由於步長是iid的，因此當前步與先前步相互獨立，該隨機過程是馬爾可夫鏈。伯努利過程和賭徒破產問題都是隨機遊走的特例。 由上述隨機遊走的例子可知，馬爾可夫鏈有一般性的構建方法，具體地，若狀態空間 有滿足形式 ： 區間內服從iid均勻分布的隨機變量（隨機數）進行數值模擬。
推廣
馬爾可夫過程（Markov process） 主詞條：馬爾可夫過程 馬爾可夫過程也被稱為連續時間馬爾可夫鏈，是馬爾可夫鏈或離散時間馬爾可夫鏈的推廣，其狀態空間是可數集，但一維指數集不再有可數集的限制，可以表示連續時間。馬爾可夫過程與馬爾可夫鏈的性質是可以類比的，其馬爾可夫性質通常有如下表示 ：
由于马尔可夫过程的状态空间是可数集，在连续时间下其样本轨道几乎必然（a.s.）是右连续的片段函数，因此马尔可夫过程可以表示为跳跃过程（jump process）并与马尔可夫链相联系
：
在有限个时间片段下的局部嵌入过程（locally embedded process）。
馬爾可夫模型（Markov model） 主詞條：馬爾可夫模型 馬爾可夫鏈或馬爾可夫過程不是唯一以馬爾可夫性質為基礎建立的隨機過程，事實上，隱馬爾可夫模型、馬爾可夫決策過程、馬爾可夫隨機場等隨機過程/隨機模型都具有馬爾可夫性質並被統稱為馬爾可夫模型。這裡對馬爾可夫模型的其它成員做簡要介紹： 1. 隱馬爾可夫模型（Hidden Markov Model, HMM） HMM是一個狀態空間不完全可見，即包含隱藏狀態（hidden status）的馬爾可夫鏈，HMM中可見的部分被稱為輸出狀態（emission state），與隱藏狀態有關，但不足以形成完全的對應關係。以語音識別（speech recognition）為例，需要識別的語句是不可見的隱藏狀態，接收的語音或音頻是和語句有關的輸出狀態，此時HMM常見的應用是基於馬爾可夫性質從語音輸入推出其對應的語句，即從輸出狀態反解隱藏狀態。 2. 馬爾可夫決策過程（Markov decision process, MDP）： MDP是在狀態空間的基礎上引入了「動作」的馬爾可夫鏈，即馬爾可夫鏈的轉移概率不僅與當前狀態有關，也與當前動作有關。MDP包含一組交互對象，即智能體（agent）和環境，並定義了5個模型要素：狀態（state）、動作（action）、策略（policy）、獎勵（reward）和回報（return），其中策略是狀態到動作的映射，回報是獎勵隨時間步的折現或積累。在MDP的演化中，智能體對環境的初始狀態進行感知，按策略實施動作，環境受動作影響進入新的狀態並反饋給智能體一個獎勵。智能體接收「獎勵」並採取新的策略，與環境持續交互。MDP是強化學習（reinforcement learning）的數學模型之一，被用於模擬智能體可實現的隨機性策略與回報。MDP的推廣之一是部分可觀察馬爾可夫決策過程（partially observable Markov decision process, POMDP），即考慮了HMM中隱藏狀態和輸出狀態的MDP。 3. 馬爾可夫隨機場（Markov Random Field, MRF） MRF是馬爾可夫鏈由一維指數集向高維空間的推廣。MRF的馬爾可夫性質表現為其任意一個隨機變量的狀態僅由其所有鄰接隨機變量的狀態決定。 類比馬爾可夫鏈中的有限維分布，MRF中隨機變量的聯合概率分布是所有包含該隨機變量的團（cliques）的乘積。MRF最常見的例子是伊辛模型（Ising model）。 哈里斯鏈（Harris chain） 哈里斯鏈是馬爾可夫鏈從可數狀態空間向連續狀態空間的推廣，給定可測空間，該馬爾可夫鏈滿足 ： 是可測空間的σ-有限測度（σ-finite measure）。 構建以採樣分布為極限分布的馬爾可夫鏈是馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo, MCMC）的核心步驟，MCMC通過在馬爾可夫鏈上不斷迭代時間步以得到近似服從採樣分布的隨機數，並使用這些隨機數逼近求解目標對採樣分布的數學期望 ：
马尔可夫链的极限分布性质决定了MCMC是无偏估计（unbiased estimation），即采样数趋于无穷时会得到求解目标数学期望的真实值，这将MCMC与其替代方法，例如变分贝叶斯估计（variational Bayesian inference）相区分，后者计算量通常小于MCMC但无法确保得到无偏估计。
其它
在物理學和化學中，馬爾可夫鏈和馬爾可夫過程被用於對動力系統進行建模，形成了馬爾可夫動力學（Markov dynamics）。 在排隊論（queueing theory）中，馬爾可夫鏈是排隊過程的基本模型。在信號處理方面，馬爾可夫鏈是一些序列數據壓縮算法，例如Ziv-Lempel編碼的數學模型 ，在金融領域，馬爾可夫鏈模型被用於預測企業產品的市場占有率。