馬爾可夫鏈

此條目介紹的是離散時間馬爾可夫鏈。關於連續時間馬爾可夫鏈，請見「連續時間馬爾可夫鏈」。

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

一個具有兩個轉換狀態的馬爾可夫鏈.

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

介紹

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

形式化定義

馬爾可夫鏈是滿足馬爾可夫性質的隨機變量序列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)$無意義。

變種

• 連續時間馬爾可夫過程具有連續索引。
• 時齊馬爾可夫鏈（或靜態馬爾可夫鏈）是對於所有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}\,$

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

伯努利方案

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

一般的狀態空間

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

應用

物理

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

語音識別

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

互聯網應用

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

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

經濟和金融

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

生物數學

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

音樂

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

馬爾可夫文本生成器

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

信息論

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

歷史

俄國數學家安德雷·安德耶維齊·馬爾可夫.

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

隱馬可夫模型

• 語音辨識

參看

• 馬爾可夫性質
• 隱馬爾可夫模型
• 量子馬爾可夫鏈
• 馬爾科夫蒙特卡洛

參考文獻

來源

• 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.
• 有關馬爾可夫鏈的資源列表 （頁面存檔備份，存於網際網路檔案館）