馬爾可夫鏈

馬爾可夫鏈（英語：Markov chain），又稱離散時間馬可夫鏈（discrete-time Markov chain，縮寫為DTMC^[1]），因俄國數學家安德烈·馬爾可夫得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備「無記憶」的性質：下一狀態的概率分布只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定類型的「無記憶性」稱作馬可夫性質。馬爾科夫鏈作為實際過程的統計模型具有許多應用。

在馬爾可夫鏈的每一步，系統根據概率分布，可以從一個狀態變到另一個狀態，也可以保持當前狀態。狀態的改變叫做轉移，與不同的狀態改變相關的概率叫做轉移概率。隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裡移動到每一個點的概率都是相同的（無論之前漫步路徑是如何的）。

介紹

馬爾可夫鏈是離散狀態、離散時間的馬爾可夫過程。

形式化定義

馬爾可夫鏈是滿足馬爾可夫性質的隨機變量序列X₁, X₂, X₃, ...，即給出當前狀態，將來狀態和過去狀態是相互獨立的。從形式上看，

如果兩邊的條件分布有定義（即如果

\Pr(X_{1}=x_{1},...,X_{n}=x_{n})>0

），則

\Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n})

。

X_i的可能值構成的可數集S叫做該鏈的「狀態空間」。

通常用一系列有向圖來描述馬爾可夫鏈，其中圖n的邊用從時刻n的狀態到時刻n+1的狀態的概率 $\Pr(X_{n+1}=x\mid X_{n}=x_{n})$ 來標記。也可以用從時刻n到時刻n+1的轉移矩陣表示同樣的信息。但是，馬氏鏈常常被假定為時齊的（見下文的變種），在這種情況下，圖和矩陣與n無關，因此也不表現為序列。

這些描述強調了馬爾可夫鏈與初始分布 $\Pr(X_{1}=x_{1})$ 無關這一結構。當時齊的時候，可以認為馬氏鏈是分配從一個頂點或狀態跳變到相鄰一個的概率的狀態機。可以把機器狀態的概率 $\Pr(X_{n}=x|X_{1}=x_{1})$ 作為僅有元素 $x_{1}$ 的狀態空間為輸入的機器的統計行為分析，或作為初始分布為 $\Pr(X_{1}=y)=[x_{1}=y]$ 狀態為輸入的機器行為，其中 $[P]$ 是艾佛森括號。

一些狀態序列可能會有零概率的事件，對應多連通分量的圖，而我們禁止轉移概率為0的邊。例如，若a到b的概率非零，但a到x位於圖的不同連通分量，那麼 $\Pr(X_{n+1}=b|X_{n}=a)$ 有意義，而 $\Pr(X_{n+1}=b|X_{1}=x,...,X_{n}=a)$ 無意義。

變種

連續時間馬爾可夫過程（英語：Continuous-time Markov process）具有連續索引。
時齊馬爾可夫鏈（或靜態馬爾可夫鏈）是對於所有n

\Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)\,

的過程。轉移概率與n無關。

m階馬爾可夫鏈（或記憶為m的馬爾可夫鏈），其中m有限，為滿足

{\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}

的過程。換句話說，未來狀態取決於其前m個狀態。It is possible to construct a chain（Y_n）from (X_n) which has the 'classical' Markov property by taking as state space the ordered m-tuples of X values, ie. Y_n =(X_n, X_n−1, ..., X_n−m+1)。

瞬態演變

用n步從狀態i到狀態j的概率為

p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,

而單步轉移是

p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,

對於一個時齊馬爾可夫鏈來說：

p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)\,

而

p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i).\,

n步轉移概率滿足查普曼-科爾莫戈羅夫等式，對任意k使得0 < k < n，

p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}

其中S為此馬爾可夫鏈的狀態空間。

邊緣分布Pr(X_n = x)為第n次狀態的分布。初始分布為Pr(X₀ = x)。用一步轉移把過程演變描述為

\Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r)

。

注意：上標（n）是索引而非指數。

性質

可還原性

馬爾可夫鏈是由一個條件分布來表示的

P(X_{n+1}|X_{n})\,

這被稱為是隨機過程中的「轉移概率」。這有時也被稱作是「一步轉移概率」。二、三，以及更多步的轉移概率可以導自一步轉移概率和馬爾可夫性質：

P(X_{n+2}|X_{n})=\int P(X_{n+2},X_{n+1}|X_{n})\,dX_{n+1}=\int P(X_{n+2}|X_{n+1})\,P(X_{n+1}|X_{n})\,dX_{n+1}

同樣，

P(X_{n+3}|X_{n})=\int P(X_{n+3}|X_{n+2})\int P(X_{n+2}|X_{n+1})\,P(X_{n+1}|X_{n})\,dX_{n+1}\,dX_{n+2}

這些式子可以通過乘以轉移概率並求 $k-1$ 次積分來一般化到任意的將來時間 $n+k$ 。

周期性

邊緣分布 $P(X_{n})$ 是在時間為 $n$ 時的狀態的分布。初始分布為 $P(X_{0})$ 。該過程的變化可以用以下的一個時間步幅來描述：

P(X_{n+1})=\int P(X_{n+1}|X_{n})\,P(X_{n})\,dX_{n}

這是Frobenius-Perron equation的一個版本。這時可能存在一個或多個狀態分布 $\pi$ 滿足

\pi (X)=\int P(X|Y)\,\pi (Y)\,dY

其中 $Y$ 只是為了便於對變量積分的一個名義。這樣的分布 $\pi$ 被稱作是「平穩分布」（Stationary Distribution）或者「穩態分布」（Steady-state Distribution）。一個平穩分布是一個對應於特徵值為 $1$ 的條件分布函數的特徵方程。

平穩分布是否存在，以及如果存在是否唯一，這是由過程的特定性質決定的。「不可約」是指每一個狀態都可來自任意的其它狀態。當存在至少一個狀態經過一個固定的時間段後連續返回，則這個過程被稱為是「周期的」。

重現性

各態歷遍性

具有重現性而不具有周期性叫做遍歷的。重現性包括局部重現性。

律動性

平穩狀態分析和極限分布

平穩狀態分析和時齊馬爾可夫鏈

有限狀態空間

若狀態空間是有限的，則轉移概率分布可以矩陣表示，該矩陣稱為轉移矩陣，記為P。其中處於 $(i,j)$ 的元素等於

p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i).\,

由於P的每一行各元素之和為1，且P中所有的元素都是非負的，因此P是一個右隨機矩陣。

穩定分布與特徵向量和單純形的關係

穩定分布π是一個（行）向量，它的元素都非負且和為1，不隨施加P操作而改變，定義為

\pi \mathbf {P} =\pi .\,

通過將這個定義與特徵向量進行比較，我們看到，這兩個概念是相關的，並且

\pi ={\frac {e}{\sum _{i}{e_{i}}}}

是由（ $\textstyle \sum _{i}\pi _{i}=1$ ）歸一化的轉移矩陣P的左特徵向量 e的倍數，其特徵值為1。如果有多個單位特徵向量那麼相應穩態的加權和也是穩態。但對於馬爾可夫鏈來說，我們更關心的是作為一些對初始分布的序列分布的極限的穩態。

穩定分布 $\textstyle \pi _{i}$ 的值與狀態空間P有關，它的特徵向量保留各自的相對比例。因為π的成分為正且滿足約束條件 $\textstyle \sum _{i}1\cdot \pi _{i}=1$ ，我們發現π與一個成分全為1的向量的點積是統一的，、π位於一個單純形上。

有限狀態空間內的時齊馬爾可夫鏈

對於一個離散狀態空間， $k$ 步轉移概率的積分即為求和，可以對轉移矩陣求 $k$ 次冪來求得。就是說，如果 $\mathbf {P}$ 是一步轉移矩陣， $\mathbf {P} ^{k}$ 就是 $k$ 步轉移後的轉移矩陣。

如果轉移矩陣 $\mathbf {P}$ 不可約，並且是非周期的，則 $\mathbf {P} ^{k}$ 收斂到一個每一列都是不同的平穩分布 $\pi ^{*}$ ，並且，

\lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\pi ^{*}

,

獨立於初始分布 $\pi$ 。這是由Perron-Frobenius theorem所指出的。

正的轉移矩陣（即矩陣的每一個元素都是正的）是不可約和非周期的。矩陣被稱為是一個隨機矩陣，當且僅當這是某個馬爾可夫鏈中轉移概率的矩陣。

注意：在上面的定式化中，元素 $(i,j)$ 是由j轉移到i的概率。有時候一個由元素 $(i,j)$ 給出的等價的定式化等於由i轉移到j的概率。在此情況下，轉移矩陣僅是這裡所給出的轉移矩陣的轉置。另外，一個系統的平穩分布是由該轉移矩陣（每列的和為1）的右特徵向量給出的，而不是左特徵向量。

轉移概率獨立於過去的特殊況為熟知的Bernoulli scheme。僅有兩個可能狀態的Bernoulli scheme被熟知為伯努利過程

趨向穩定分布的收斂速度

可反轉馬爾可夫鏈

可反轉馬爾可夫鏈類似於應用貝葉斯定理來反轉一個條件概率：

{\begin{aligned}\Pr(X_{n}=i\mid X_{n+1}=j)&={\frac {\Pr(X_{n}=i,X_{n+1}=j)}{\Pr(X_{n+1}=j)}}\\&={\frac {\Pr(X_{n}=i)\Pr(X_{n+1}=j\mid X_{n}=i)}{\Pr(X_{n+1}=j)}}.\end{aligned}}

以上就是反轉的馬爾可夫鏈。因而，如果存在一個π，使得：

\pi _{i}p_{ij}=\pi _{j}p_{ji}.\,

那麼這個馬爾可夫鏈就是可反轉的。

這個條件也被稱為細緻平衡（detailed balance）條件。

對於所有的i求和：

\sum _{i}\pi _{i}p_{ij}=\pi _{j}\,

所以，對於可反轉馬爾可夫鏈，π總是一個平穩分布。

伯努利方案

伯努利方案是馬爾可夫鏈的一種特殊情形，其轉移概率矩陣有相同的行，即下一狀態均勻獨立於當前狀態（除了獨立於過往狀態以外）。僅有兩個可能狀態的伯努利方案是伯努利過程。

一般的狀態空間

對於一般狀態空間上的馬爾可夫鏈的概述，詳見文章狀態空間可測的馬爾可夫鏈。

Harris鏈

局部交互的馬爾可夫鏈

應用

物理

馬爾可夫系統廣泛出現在熱力學和統計力學中，

化學

測試

語音識別

隱馬爾科夫模型是大多數現代自動語音識別系統的基礎。

資訊科學

排隊理論

互聯網應用

谷歌所使用的網頁排序算法（PageRank）就是由馬爾可夫鏈定義的。如果 $N$ 是已知的網頁數量，一個頁面 $i$ 有 $k_{i}$ 個鏈接到這個頁面，那麼它到鏈接頁面的轉換概率為 ${\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}$ ，到未鏈接頁面的概率為 ${\frac {1-\alpha }{N}}$ ，參數 $\alpha$ 的取值大約為0.85。

馬爾可夫模型也被應用於分析用戶瀏覽網頁的行為。一階或者二階的馬爾可夫模型可以用於對一個用戶從某一網絡鏈接轉移到另一鏈接的行為進行建模，然後這些模型可以用於對用戶之後的瀏覽行為進行預測。

統計

經濟和金融

馬爾科夫鏈可以應用於金融與經濟中一系列現象的建模，包括資產價值與市場衝擊。1974年Prasad等人第一次應用馬爾科夫鏈於金融模型^[2]，另一個是James D. Hamilton 1989年應用的機制轉換模型^[3]，其中馬爾科夫鏈用來對高GDP增長速度時期與低GDP增長速度時期（換言之，經濟擴張與緊縮）的轉換進行建模^[3]。

社會科學

生物數學

馬爾可夫鏈也有眾多的生物學應用，特別是增殖過程，可以幫助模擬生物增殖過程的建模。隱蔽馬爾可夫模型還被用於生物信息學，用以編碼區域或基因預測（見哈代-溫伯格定律。）

遺傳學

遊戲

音樂

馬爾可夫鏈也被用於算法作曲，例如在Csound 、 Max和SuperCollider等軟件中。在一階鏈中，該系統的狀態是音符或音高，再構建每個音符的轉移概率，完成轉移矩陣。算法根據轉移矩陣生成音符的輸出，該值可以是MIDI音符值、音高或其他量。

棒球

馬爾可夫文本生成器

馬爾可夫過程，能為給定樣品文本，生成粗略，但看似真實的文本：他們被用於眾多供消遣的「模仿生成器」軟件。馬爾可夫鏈還被用於譜曲。

信息論

用於計算馬爾可夫信源的極限熵

歷史

馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數無限狀態空間是由俄國數學家柯爾莫果洛夫（俄語：Андре́й Никола́евич Колмого́ров）在1936年給出的。馬爾可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學重要課題是相聯繫的，但馬爾可夫尋求的似乎不僅於數學動機，名義上是對於縱屬事件大數法則的擴張。

隱馬可夫模型

語音辨識

參看

參考文獻

引用

^ Norris, James R. Markov chains. Cambridge University Press. 1998 [2015-03-19]. （原始內容存檔於2021-05-06）.
^ Prasad, NR; RC Ender; ST Reilly; G Nesgos. Allocation of resources on a minimized cost basis. 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes. 1974, 13: 402–3. doi:10.1109/CDC.1974.270470. （原始內容存檔於2015-02-12）.
^ ^3.0 ^3.1 Hamilton, James . A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica (Econometrica, Vol. 57, No. 2). 1989, 57 (2): 357–84. JSTOR 1912559. doi:10.2307/1912559.

來源

A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135-156, 1906.
A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 978-0-89871-296-4. （See Chapter 7.）
J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 978-0-471-52369-7.

外部連結

免費的《概率論入門》書中有關馬爾可夫鏈的章節（頁面存檔備份，存於網際網路檔案館）
世界上最大的矩陣計算（Google's PageRank as the stationary distribution of a random walk through the Web.） （頁面存檔備份，存於網際網路檔案館）
Disassociated Press in Emacs approximates a Markov process
[1] Markov chains used to produce semi-coherent English.
有關馬爾可夫鏈的資源列表（頁面存檔備份，存於網際網路檔案館）

[1] Norris, James R. Markov chains. Cambridge University Press. 1998 [2015-03-19]. （原始內容存檔於2021-05-06）.

[2] Prasad, NR; RC Ender; ST Reilly; G Nesgos. Allocation of resources on a minimized cost basis. 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes. 1974, 13: 402–3. doi:10.1109/CDC.1974.270470. （原始內容存檔於2015-02-12）.

[#1-3] 3.0 ^3.1 Hamilton, James . A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica (Econometrica, Vol. 57, No. 2). 1989, 57 (2): 357–84. JSTOR 1912559. doi:10.2307/1912559.

[1]

[2]

[3]

閱論編概率論：隨機過程
離散時間（英語：Discrete-time stochastic process）	伯努利過程分支過程中餐館過程高爾頓-沃特森過程（英語：Galton–Watson process）獨立同分布馬爾可夫鏈莫蘭過程（英語：Moran process）隨機漫步循環擦除隨機遊走（英語：Loop-erased）自避行走
連續時間	貝塞爾過程出生-死亡過程維納過程/布朗運動布朗橋 Excursion（英語：Brownian excursion）分數布朗運動（英語：Fractional Brownian motion）幾何布朗運動 Meander（英語：Brownian meander）柯西過程（英語：Cauchy process） Contact process（英語：Contact process (mathematics)） Cox process（英語：科克斯过程） Diffusion process（英語：Diffusion process） Empirical process（英語：Empirical process）費勒過程（英語：Feller process）弗萊明-維奧過程（英語：Fleming–Viot process）伽馬過程（英語：Gamma process）亨特過程（英語：Hunt process） Interacting particle system（英語：Interacting particle system）s 伊藤積分伊藤過程跳躍擴散（英語：Jump diffusion）跳躍過程萊維過程 Local time（英語：Local time (mathematics)）馬爾可夫加過程（英語：Markov additive process）麥基恩-弗拉索夫過程（英語：McKean–Vlasov process）奧恩斯坦-烏倫貝克過程泊松過程複合泊松過程（英語：Compound Poisson process）非齊次泊松過程泊松點過程施拉姆-勒夫納演進半鞅 Sigma-martingale（英語：Sigma-martingale） Stable process（英語：Stable process） Superprocess（英語：Superprocess） Telegraph process（英語：Telegraph process） Variance gamma process（英語：Variance gamma process）維納過程 Wiener sausage（英語：Wiener sausage）
離散時間與連續時間	分支過程高斯過程隱馬爾可夫模型（HMM）馬可夫過程鞅鞅差序列（英語：Martingale difference sequence）局部鞅（英語：Local martingale） Sub- Super-（英語：Super-） Random dynamical system（英語：Random dynamical system） Regenerative process（英語：Regenerative process） Renewal process（英語：Renewal process）白雜訊
場及其它	狄利克雷過程（英語：Dirichlet process）高斯隨機場（英語：Gaussian random field）吉布斯測度（英語：Gibbs measure）霍普菲爾德神經網絡易辛模型馬爾可夫網絡滲流理論皮特曼-約爾過程（英語：Pitman–Yor process）點過程 Cox（英語：Point process#Cox point process）泊松過程玻茨模型隨機場隨機圖
時間序列模型	ARCH模型 ARIMA模型自我迴歸模型 ARMA模型廣義ARCH模型移動平均模型
金融模型	布萊克-德爾曼-托伊模型（英語：Black–Derman–Toy model）布萊克-卡拉辛斯基模型（英語：Black–Karasinski model）布萊克-舒爾斯模型陳模型 Constant elasticity of variance (CEV)（英語：Constant elasticity of variance model）科克斯-英格索爾-羅斯模型 (CIR)（英語：Cox–Ingersoll–Ross model） Garman–Kohlhagen（英語：Garman–Kohlhagen model） HJM框架赫斯頓模型（英語：Heston model） Ho–Lee（英語：Ho–Lee model）赫爾-懷特模型 LIBOR市場模型（英語：LIBOR market model） SABR volatility（英語：SABR volatility model）瓦西塞克模型（英語：Vasicek model）
精算學	Bühlmann（英語：Bühlmann model） Cramér–Lundberg（英語：Cramér–Lundberg model） Risk process（英語：Risk process） Sparre–Anderson（英語：Sparre–Anderson model）
等候理論	Bulk（英語：Bulk queue） Fluid（英語：Fluid queue） Generalized queueing network（英語：G-network） M/G/1（英語：M/G/1 queue） M/M/1 M/M/c（英語：M/M/c queue）
性質	右連左極函數 Continuous（英語：Continuous stochastic process） Continuous paths（英語：Sample-continuous process）遍歷性 Exchangeable（英語：Exchangeable random variables） Feller-continuous（英語：Feller-continuous process） Gauss–Markov（英語：Gauss–Markov process）馬爾可夫性質 Mixing（英語：Mixing (mathematics)） Piecewise deterministic（英語：Piecewise deterministic Markov process）可預測過程循序可測過程 Self-similar（英語：Self-similar process）平穩過程 Time-reversible（英語：Time reversibility）
極限定理	中心極限定理 Donsker's theorem（英語：Donsker's theorem） Doob's martingale convergence theorems（英語：Doob's martingale convergence theorems）遍歷理論 Fisher–Tippett–Gnedenko theorem（英語：Fisher–Tippett–Gnedenko theorem） Large deviation principle（英語：Large deviation principle）大數法則重對數律 Maximal ergodic theorem（英語：Maximal ergodic theorem） Sanov's theorem（英語：Sanov's theorem）
不等式	Burkholder–Davis–Gundy（英語：Burkholder–Davis–Gundy inequalities） Doob's martingale（英語：Doob's martingale inequality） Kunita–Watanabe（英語：Kunita–Watanabe inequality）
工具	Cameron–Martin formula（英語：Cameron–Martin formula）隨機變量的收斂 Doléans-Dade exponential（英語：Doléans-Dade exponential） Doob decomposition theorem（英語：Doob decomposition theorem） Doob–Meyer decomposition theorem（英語：Doob–Meyer decomposition theorem） Doob's optional stopping theorem（英語：Doob's optional stopping theorem） Dynkin's formula（英語：Dynkin's formula）費曼-卡茨公式右連左極函數 Girsanov theorem（英語：Girsanov theorem） Infinitesimal generator（英語：Infinitesimal generator (stochastic processes)）伊藤積分伊藤引理 Kolmogorov continuity theorem（英語：Kolmogorov continuity theorem） Kolmogorov extension theorem（英語：Kolmogorov extension theorem） Lévy–Prokhorov metric（英語：Lévy–Prokhorov metric） Malliavin calculus（英語：Malliavin calculus） Martingale representation theorem（英語：Martingale representation theorem） Optional stopping theorem（英語：Optional stopping theorem） Prohorov theorem（英語：Prohorov theorem）二次變差 Reflection principle（英語：Reflection principle (Wiener process)） Skorokhod integral（英語：Skorokhod integral） Skorokhod's representation theorem（英語：Skorokhod's representation theorem）右連左極函數 Snell envelope（英語：Snell envelope）隨機微分方程 Tanaka（英語：Tanaka equation）停時隨機積分 Uniform integrability（英語：Uniform integrability） Usual hypotheses（英語：Usual hypotheses）維納空間 Classical（英語：Classical Wiener space） Abstract 漂移項
相關領域	精算學計量經濟學遍歷理論極值理論（EVT） Large deviations theory（英語：Large deviations theory）數理金融學數理統計學概率論等候理論 Renewal theory（英語：Renewal theory） Ruin theory（英語：Ruin theory）統計學隨機分析時間序列分析機器學習
分類

權威控制資料庫
國際	FAST
各地	西班牙法國 BnF data 德國以色列美國
其他	現代烏克蘭百科全書