-
馬爾可夫鏈
鎖定
馬爾可夫鏈(Markov Chain, MC)是概率論和數理統計中具有馬爾可夫性質(Markov property)且存在於離散的指數集(index set)和狀態空間(state space)內的隨機過程(stochastic process)
[1-2]
。適用於連續指數集的馬爾可夫鏈被稱為馬爾可夫過程(Markov process),但有時也被視為馬爾可夫鏈的子集,即連續時間馬爾可夫鏈(Continuous-Time MC, CTMC),與離散時間馬爾可夫鏈(Discrete-Time MC, DTMC)相對應,因此馬爾可夫鏈是一個較為寬泛的概念
[2]
。
馬爾可夫鏈可通過轉移矩陣和轉移圖定義,除馬爾可夫性外,馬爾可夫鏈可能具有不可約性、常返性、週期性和遍歷性。一個不可約和正常返的馬爾可夫鏈是嚴格平穩的馬爾可夫鏈,擁有唯一的平穩分佈。遍歷馬爾可夫鏈(ergodic MC)的極限分佈收斂於其平穩分佈
[1]
。
馬爾可夫鏈可被應用於蒙特卡羅方法中,形成馬爾可夫鏈蒙特卡羅(Markov Chain Monte Carlo, MCMC)
[2-3]
,也被用於動力系統、化學反應、排隊論、市場行為和信息檢索的數學建模。此外作為結構最簡單的馬爾可夫模型(Markov model),一些機器學習算法,例如隱馬爾可夫模型(Hidden Markov Model, HMM)、馬爾可夫隨機場(Markov Random Field, MRF)和馬爾可夫決策過程(Markov decision process, MDP)以馬爾可夫鏈為理論基礎
[4]
。
馬爾可夫鏈的命名來自俄國數學家安德雷·馬爾可夫(Андрей Андреевич Марков)以紀念其首次提出馬爾可夫鏈和對其收斂性質所做的研究
[5]
。
馬爾可夫鏈歷史
馬爾可夫鏈的提出來自俄國數學家安德雷·馬爾可夫(Андрей Андреевич Марков)。為了擴大概率論極限定理的應用範圍,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]
。
馬爾可夫鏈定義
馬爾可夫鏈是一組具有馬爾可夫性質的離散隨機變量的集合。具體地,對概率空間
內以一維可數集為指標集(index set) 的隨機變量集合
,若隨機變量的取值都在可數集內:
,且隨機變量的條件概率滿足如下關係
[2]
:
上式在定義馬爾可夫鏈的同時定義了馬爾可夫性質,該性質也被稱為“無記憶性(memorylessness)”,即t+1步的隨機變量在給定第t步隨機變量後與其餘的隨機變量條件獨立(conditionally independent):
[2]
。在此基礎上,馬爾可夫鏈具有強馬爾可夫性(strong Markov property),即對任意的停時( stopping time),馬爾可夫鏈在停時前後的狀態相互獨立
[1]
。
解釋性例子
馬爾科夫鏈的一個常見例子是簡化的股票漲跌模型:若一天中某股票上漲,則第二天該股票有概率p開始下跌,1-p繼續上漲;若一天中該股票下跌,則明天該股票有概率q開始上漲,1-q繼續下跌。該股票的漲跌情況是一個馬爾可夫鏈,且定義中各個概念在例子中有如下對應:
- 隨機變量:第t天該股票的狀態;狀態空間:“上漲”和“下跌”;指數集:天數。
- 條件概率關係:按定義,即便已知該股票的所有歷史狀態,其在某天的漲跌也僅與前一天的狀態有關。
- 無記憶性:該股票當天的表現僅與前一天有關,與其他歷史狀態無關(定義條件概率關係的同時定義了無記憶性)。
- 停時前後狀態相互獨立:取出該股票的漲跌記錄,然後從中截取一段,我們無法知道截取的是哪一段,因為截取點,即停時t前後的記錄(t-1和t+1)沒有依賴關係。
n-階馬爾可夫鏈(n-order Markov chain)
n-階馬爾可夫鏈擁有n階的記憶性,可視為馬爾可夫鏈的推廣。類比馬爾可夫鏈的定義,n-階馬爾可夫鏈滿足如下條件:
馬爾可夫鏈理論與性質
馬爾可夫鏈轉移理論
馬爾可夫鏈中隨機變量的狀態隨時間步的變化被稱為演變(evolution)或轉移(transition)。這裏介紹描述馬爾可夫鏈結構的兩種途徑,即轉移矩陣和轉移圖,並定義了馬爾可夫鏈在轉移過程中表現出的性質。
轉移概率(transition probability)與轉移矩陣(transition matrix)
主詞條:轉移矩陣
上式表明,馬爾可夫鏈直接演變n步等價於其先演變n-k步,再演變k步(k處於該馬爾可夫鏈的狀態空間內)。n-步轉移概率與初始概率的乘積被稱為該狀態的絕對概率。
轉移圖(transition graph)
1. 可達(accessible)與連通(communicate)
馬爾可夫鏈的演變可以按圖(graph)結構,表示為轉移圖(transition graph),圖中的每條邊都被賦予一個轉移概率。通過轉移圖可引入“可達”和“連通”的概念:
若對馬爾可夫鏈中的狀態
有:
,即採樣路徑上的所有轉移概率不為0,則狀態
是狀態
的可達狀態,在轉移圖中表示為有向連接:
。如果
互為可達狀態,則二者是連通的,在轉移圖中形成閉合迴路,記為
[1]
。由定義,可達與連通可以是間接的,即不必在單個時間步完成。
2. 閉合集(closed set)與吸收態(absorbing state)
給定狀態空間的一個子集,若馬爾可夫鏈進入該子集後無法離開:
,則該子集是閉合的,稱為閉合集,一個閉合集外部的所有狀態都不是其可達狀態。若閉合集中只有一個狀態,則該狀態是吸收態,在轉移圖中是一個概率為1的自環。一個閉合集可以包括一個或多個連通類。
3. 轉移圖的例子
由定義可知,該轉移圖包含了三個連通類:
、三個閉合集:
和一個吸收態,即狀態6。注意到,在上述轉移圖中,馬爾可夫鏈從任意狀態出發最終都會進入吸收態,這類馬爾可夫鏈被稱為吸收馬爾可夫鏈(absorbing Markov chain)
[22]
。
馬爾可夫鏈性質
這裏對馬爾可夫鏈的4個性質:不可約性、常返性、週期性和遍歷性進行定義。與馬爾可夫性質不同,這些性質不是馬爾可夫鏈必然擁有的性質,而是其在轉移過程中對其狀態表現出的性質。上述性質都是排他的,即不具有可約性的馬爾可夫鏈必然是不可約的,以此類推。
不可約性(irreducibility)
如果一個馬爾可夫鏈的狀態空間僅有一個連通類,即狀態空間的全體成員,則該馬爾可夫鏈是不可約的,否則馬爾可夫鏈具有可約性(reducibility)
[23]
。馬爾可夫鏈的不可約性意味着在其演變過程中,隨機變量可以在任意狀態間轉移
[1]
。
常返性(recurrence)
若馬爾可夫鏈在到達一個狀態後,在演變中能反覆回到該狀態,則該狀態是常返狀態,或該馬爾可夫鏈具有(局部)常返性,反之則具有瞬變性(transience)的。正式地,對狀態空間中的某個狀態,馬爾可夫鏈對一給定狀態的返回時間(return time)是其所有可能返回時間的下確界(infimum)
[1]
:
由上述瞬變性和常返性的定義可有如下推論:
- 推論:若有限個狀態的馬爾可夫鏈是不可約的,則其所有狀態是正常返的。
- 推論:若狀態A是可常返的,且狀態B是A的可達狀態,則A與B是連通的,且B是常返的。
- 推論:若狀態B是A的可達狀態,且狀態B是吸收態,則B是常返狀態,A是瞬變狀態。
- 推論:由正常返狀態組成的集合是閉合集,但閉合集中的狀態未必是常返狀態。
週期性(periodicity)
- 推論:吸收態是非週期性狀態。
遍歷性(ergodicity)
若馬爾可夫鏈的一個狀態是正常返的和非週期的,則該狀態具有遍歷性
[1]
。若一個馬爾可夫鏈是不可還原的,且有某個狀態是遍歷的,則該馬爾可夫鏈的所有狀態都是遍歷的,被稱為遍歷鏈。由上述定義,遍歷性有如下推論:
- 推論:若狀態A是吸收態,且A是狀態B的可達狀態,則A是遍歷的,B不是遍歷的。
- 推論:若多個狀態的馬爾可夫鏈包含吸收態,則該馬爾可夫鏈不是遍歷鏈。
- 推論:若多個狀態的馬爾可夫鍊形成有向無環圖,或單個閉環,則該馬爾可夫鏈不是遍歷鏈。
馬爾可夫鏈穩態分析
這裏介紹馬爾可夫鏈的長時間尺度行為的描述,即平穩分佈和極限分佈,並定義平穩馬爾可夫鏈。
平穩分佈(stationary distribution)
給定一個馬爾可夫鏈,若在其狀態空間存在概率分佈
,且該分佈滿足以下條件:
極限分佈(limiting distribution)
若一個馬爾可夫鏈的狀態空間存在概率分佈
並滿足如下關係:
1. 極限定理(limiting theorem)
兩個獨立的非週期平穩馬爾可夫鏈,即遍歷鏈如果有相同的轉移矩陣,那麼當時間步趨於無窮時,兩者極限分佈間的差異趨於0。按隨機過程中的耦合(coupling)理論,該結論的表述為:對狀態空間相同的遍歷鏈
,給定任意初始分佈後有
[2]
:
2. 遍歷定理(ergodic theorem)
平穩馬爾可夫鏈(stationary Markov chain)
馬爾可夫鏈特例
伯努利過程(Bernoulli process)
主詞條:伯努利過程
伯努利過程也被稱為二項馬可夫鏈(Binomial Markov chain),其建立過程如下:給定一系列相互獨立的“標識”,每個標識都是二項的,按概率
取正和負。令正隨機過程
表示n個標識中有k個正標識的概率,則其是一個伯努利過程,其中的隨機變量服從二項分佈(binomial distribution)
[2]
:
賭徒破產問題(gambler's ruin)
參見:賭徒輸光定理
隨機遊走(random walk)
主詞條:隨機遊走
馬爾可夫鏈推廣
馬爾可夫過程(Markov process)
主詞條:馬爾可夫過程
馬爾可夫過程也被稱為連續時間馬爾可夫鏈,是馬爾可夫鏈或離散時間馬爾可夫鏈的推廣,其狀態空間是可數集,但一維指數集不再有可數集的限制,可以表示連續時間。馬爾可夫過程與馬爾可夫鏈的性質是可以類比的,其馬爾可夫性質通常有如下表示
[2]
:
馬爾可夫模型(Markov model)
主詞條:馬爾可夫模型
馬爾可夫鏈或馬爾可夫過程不是唯一以馬爾可夫性質為基礎建立的隨機過程,事實上,隱馬爾可夫模型、馬爾可夫決策過程、馬爾可夫隨機場等隨機過程/隨機模型都具有馬爾可夫性質並被統稱為馬爾可夫模型。這裏對馬爾可夫模型的其它成員做簡要介紹:
1. 隱馬爾可夫模型(Hidden Markov Model, HMM)
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]
。
3. 馬爾可夫隨機場(Markov Random Field, MRF)
MRF是馬爾可夫鏈由一維指數集向高維空間的推廣。MRF的馬爾可夫性質表現為其任意一個隨機變量的狀態僅由其所有鄰接隨機變量的狀態決定。 類比馬爾可夫鏈中的有限維分佈,MRF中隨機變量的聯合概率分佈是所有包含該隨機變量的團(cliques)的乘積。MRF最常見的例子是伊辛模型(Ising model)
[17]
[31]
。
哈里斯鏈(Harris chain)
馬爾可夫鏈應用
馬爾可夫鏈MCMC
構建以採樣分佈為極限分佈的馬爾可夫鏈是馬爾可夫鏈蒙特卡羅(Markov Chain Monte Carlo, MCMC)的核心步驟,MCMC通過在馬爾可夫鏈上不斷迭代時間步以得到近似服從採樣分佈的隨機數,並使用這些隨機數逼近求解目標對採樣分佈的數學期望
[2]
[3]
:
馬爾可夫鏈其它
在物理學和化學中,馬爾可夫鏈和馬爾可夫過程被用於對動力系統進行建模,形成了馬爾可夫動力學(Markov dynamics)
[34-35]
。 在排隊論(queueing theory)中,馬爾可夫鏈是排隊過程的基本模型
[36]
。在信號處理方面,馬爾可夫鏈是一些序列數據壓縮算法,例如Ziv-Lempel編碼的數學模型
[37-38]
,在金融領域,馬爾可夫鏈模型被用於預測企業產品的市場佔有率
[39]
。
隨着馬爾可夫鏈的逐步深人研究,它在經濟學、生物學、物理學、化學、軍事學 天文學等領域都引起了連鎖反應,衍生出一系列新課題、新理論和新學科。馬爾可夫鏈具有豐富的數學理論,與其他數學學科相互滲透;而它又與自然科學、技術科學、管理科學、經濟科學以至人文科學有廣泛的交叉應用。很多問題都可建立馬爾可夫過程概率模型,運用概率論及隨機過程的理論及方法進行研究,而它們又不斷地衍生出新的研究課題。這種交互作用促進了當代概率論的飛速發展。而當前馬爾可夫鏈的理論研究,正方興未艾。
[40]
- 參考資料
-
- 1. Brémaud, P..Markov chains: Gibbs fields, Monte Carlo simulation, and queues (Vol. 31) :Springer Science & Business Media,1999:Chapter 2-4, pp.53-156
- 2. Serfozo, R..Basics of applied stochastic processes. :Springer Science & Business Media.,2009:pp.1-99, 241-242
- 3. Brooks, S., Gelman, A., Jones, G. and Meng, X.L. eds..Handbook of markov chain Monte Carlo:Chapman & Hall/CRC press,2011:pp.1-8
- 4. Brown, K., Markov model fundamentals. In Markov modeling for reliability .MathPages.2017[引用日期2018-12-30]
- 5. Gagniuc, P.A..Markov Chains: From Theory to Implementation and Experimentation:John Wiley & Sons,2017:pp.1-32
- 6. Hayes, B., 2013. First links in the Markov chain. American Scientist, 101(2), p.252.
- 7. Takács, L., 1979. On an urn problem of Paul and Tatiana Ehrenfest. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 86, No. 1, pp. 127-130). Cambridge University Press.
- 8. Poincaré, H., 1912. Sur un théoreme de géométrie. Rendiconti del Circolo Matematico di Palermo (1884-1940), 33(1), pp.375-407.
- 9. Ledoux, M., Poincaré inequalities in probability and geometric analysis .Institut de Mathématiques de Toulouse.2016[引用日期2018-12-30]
- 10. Kendall, D.G., Batchelor, G.K., Bingham, N.H., Hayman, W.K., Hyland, J.M.E., Lorentz, G.G., Moffatt, H.K., Parry, W., Razborov, A.A., Robinson, C.A. and Whittle, P., 1990. Andrei Nikolaevich Kolmogorov (1903–1987). Bulletin of the London Mathematical Society, 22(1), pp.31-100.
- 11. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E., 1953. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), pp.1087-1092.
- 12. Hastings, W.K., 1970. Monte Carlo sampling methods using Markov chains and their applications.
- 13. Bellman, R., 1957. A Markovian decision process. Journal of mathematics and mechanics, pp.679-684.
- 14. Cramér, H., 1976. A century with probability theory: Some personal recollections. The annals of probability, 4(4), pp.509-546.
- 15. Brasche, J. and Demuth, M., 2005. Dynkin's formula and large coupling convergence. Journal of Functional Analysis, 219(1), pp.34-69.
- 16. Baum, L.E. and Petrie, T., 1966. Statistical inference for probabilistic functions of finite state Markov chains. The annals of mathematical statistics, 37(6), pp.1554-1563.
- 17. Kindermann, R., 1980. Markov random fields and their applications. American mathematical society.
- 18. Rabiner, L.R. and Juang, B.H., 1986. An introduction to hidden Markov models. IEEE ASSP Magazine (IEEE Signal Processing Magazine), 3(1), pp.4-16.
- 19. Adan, I., Markov chains and Markov processes. In Course QUE: Queueing Theory .Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven.2003[引用日期2018-12-27]
- 20. Snavely, N., CS1114: Markov chains. .Computer Science, Cornell University.2009[引用日期2018-12-25]
- 21. Shahshahani, M.M., Markov chain. In Statistics 217/218. Introduction to stochastic processes .Stanford University.2003[引用日期2018-12-24]
- 22. Durand, D., Lecture Notes: Markov chains. In Computational Genomics and Molecular Biology .School of Computer Science, Carnegie Mellon University.2014[引用日期2018-12-25]
- 23. Sigman, K., Limiting distribution for a Markov chain. In Stochastic modeling I .Columbia University.2009[引用日期2018-12-27]
- 24. Levéque, O., Lecture notes on Markov chains .Hamilton Institute, National University of Ireland Maynooth.2011[引用日期2018-12-25]
- 25. Pinsky, M. and Karlin, S..An introduction to stochastic modeling:Academic press,2010:Chapter 4, pp.199-264
- 26. Nielsen, B.F., Discrete time Markov chains, limiting distribution and classification. In 02407 stochastic processes .Department of Mathematics and Computer Science, Technical University of Denmark.2018[引用日期2018-12-28]
- 27. Asmussen, S. and Glynn, P.W., 2011. A new proof of convergence of MCMC via the ergodic theorem. Statistics & Probability Letters, 81(10), pp.1482-1485.
- 28. Huang, Cheng-Chi, 1977. Non-homogeneous Markov chains and their applications. Doctor of Philosophy Thesis. Iowa State University. Retrospective Theses and Dissertations. 7614.
- 29. Polykovskiy, D. and Novikov, A., Bayesian Methods for Machine Learning .Coursera and National Research University Higher School of Economics.2017[引用日期2018-12-28]
- 30. 邱錫鵬 著,神經網絡與深度學習,第14章 深度強化學習 .Github Inc..2018-6-15[引用日期2018-12-30]
- 31. Vidakovic, B., Markov Random Fields. In Bayesion Statistics for Engineers .H. Milton Stewart School of Industrial and Systems Engineering (ISyE), Georgia Institute of Technology[引用日期2018-12-30]
- 32. Baxendale, P., 2011. TE Harris's contributions to recurrent Markov processes and stochastic flows. The Annals of Probability, pp.417-428.
- 33. Polykovskiy, D. and Novikov, A., Bayesian Methods for Machine Learning .Coursera and National Research University Higher School of Economics.2017[引用日期2018-12-30]
- 34. Lecomte, V., Appert-Rolland, C. and Van Wijland, F., 2007. Thermodynamic formalism for systems with Markov dynamics. Journal of statistical physics, 127(1), pp.51-106.
- 35. Anderson, D.F. and Kurtz, T.G., 2011. Continuous time Markov chain models for chemical reaction networks. In Design and analysis of biomolecular circuits (pp. 3-42). Springer, New York, NY.
- 36. Constantin, H., Markov chain and queueing theory. In VIGRE program .Department of Mathematics, University of Chicago.2011[引用日期2018-12-30]
- 37. Ziv, J. and Lempel, A., 1977. A universal algorithm for sequential data compression. IEEE Transactions on information theory, 23(3), pp.337-343.
- 38. Cormack, G.V. and Horspool, R.N.S., 1987. Data compression using dynamic Markov modelling. The Computer Journal, 30(6), pp.541-550.
- 39. 唐小我, 曾勇, 曹長修. 市場預測中馬爾科夫鏈轉移概率的估計[J]. 電子科技大學學報, 1994(6):643-648.
- 40. 李自玲.基於馬爾可夫鏈的歷史和現狀的研究[J].商業經濟,2017,0(3):132-133
- 41. 張玉爽,李佳珍,張婷,姜楠.基於馬爾可夫鏈的應用系統可用性預測[J].計算機應用文摘,2023,39(12):284-286
- 收起