馬可夫鏈

維基百科,自由的百科全書
前往: 導覽搜尋
一個具有兩個轉換狀態的馬可夫鏈.

馬可夫鏈英語Markov chain),又稱離散時間馬可夫鏈(discrete-time Markov chain,縮寫為 DTMC),是馬可夫過程中的一個特例,為具備馬可夫性質與離散時間狀態隨機過程。該過程中,在給定當前知識或信息的情況下,只有當前的狀態用來預測將來,過去(即當前以前的歷史狀態)對於預測將來(即當前以後的未來狀態)是無關的。因俄羅斯數學家安德烈·馬可夫得名。

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

歷史[編輯]

馬可夫在1906年首先做出了這類過程。而將此一般化到可數無限狀態空間是由柯爾莫果洛夫在1936年給出的。馬可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學重要課題是相聯繫的,但馬可夫尋求的似乎不僅於數學動機,名義上是對於縱屬事件大數法則的擴張。

定義[編輯]

馬可夫鏈是隨機變數X_1,   X_2,   X_3...的一個數列。這些變數的範圍,即他們所有可能取值的集合,被稱為「狀態空間」,而X_n的值則是在時間n的狀態。如果X_{n+1}對於過去狀態的條件機率分布僅是X_n的一個函數,則

 P(X_{n+1}=x|X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x|X_n). \,

這裡x為過程中的某個狀態。上面這個恆等式可以被看作是馬可夫性質

性質[編輯]

可還原性[編輯]

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

 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的條件分布函數的特徵方程

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

重現性[編輯]

各態歷遍性[編輯]

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

律動性[編輯]

平穩狀態分析和極限分布[編輯]

可反轉馬可夫鏈[編輯]

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


\begin{align}
\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{align}

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

\pi_i p_{ij} = \pi_j p_{ji}.\,

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

這個條件也被稱為細緻平衡 (detailed balance)條件。

對於所有的i求和:

\sum_i \pi_i p_{ij} = \pi_j\,

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

有限狀態空間中的馬可夫鏈[編輯]

如果狀態空間是有限的,則轉移機率分布可以表示為一個具有(i,j)元素的矩陣,稱之為「轉移矩陣」:

P_{ij} = P(X_{n+1}=j\mid X_n=i) \,

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

平穩分布是一個滿足以下方程的向量

 \pi^*\mathbf{P} = \pi^*.

在此情況下,穩態分布\pi^* 是一個對應於特徵根為1的、該轉移矩陣的特徵向量。

如果轉移矩陣\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被熟知為伯努利過程

科學應用[編輯]

統計[編輯]

馬可夫鏈通常用來建模排隊理論統計學中的建模,還可作為信號模型用於熵編碼技術,如算術編碼(著名的LZMA數據壓縮演算法就使用了馬可夫鏈與類似於算術編碼的區間編碼)。

生物[編輯]

馬可夫鏈也有眾多的生物學應用,特別是增殖過程,可以幫助模擬生物增殖過程的建模。隱蔽馬可夫模型還被用於生物信息學,用以編碼區域或基因預測。

地理[編輯]

馬可夫鏈最近的應用是在地理統計學(geostatistics)中。其中,馬可夫鏈用在基於觀察數據的二到3D離散變數的隨機模擬。這一應用類似於「克里金」地理統計學(Kriging geostatistics),被稱為是「馬可夫鏈地理統計學」。這一馬可夫鏈地理統計學方法仍在發展過程中。

網際網路應用[編輯]

谷歌(Google)所使用的網頁排序演算法(PageRank)就是由馬可夫鏈定義的。馬可夫模型也被應用於分析用戶瀏覽網頁的行為。一階或者二階的馬可夫模型可以用於對一個用戶從某一網路連結轉移到另一連結的行為進行建模,然後這些模型可以用於對用戶之後的瀏覽行為進行預測。

馬可夫模仿文本生成器[編輯]

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

(隱藏式)隱馬可夫模型[編輯]

參看[編輯]

參考文獻[編輯]

  • 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 0-89871-296-3. (See Chapter 7.)
  • J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.

外部連結[編輯]