馬爾可夫鏈

馬爾可夫鏈，因俄國數學家安德烈·馬爾可夫得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備“無記憶”的性質：下一狀態的機率分佈只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定型別的“無記憶性”稱作馬可夫性質。馬爾科夫鏈作為實際過程的統計模型具有許多應用。在馬爾可夫鏈的每一步，系統根據機率分佈，可以從一個狀態變到另一個狀態，也可以保持當前狀態。狀態的改變叫做轉移，與不同的狀態改變相關的機率叫做轉移機率。隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裡移動到每一個點的機率都是相同的。介紹.馬爾可夫鏈是離散狀態、離散時間的馬爾可夫過程。形式化定義.馬爾可夫鏈是滿足馬爾可夫性質的隨機變數序列"X"1, "X"2, "X"3, ...，即給出當前狀態，將來狀態和過去狀態是相互獨立的。從形式上看，如果兩邊的條件分佈有定義，則formula_2。"X""i"的可能值構成的可數集"S"叫做該鏈的“狀態空間”。通常用一系列有向圖來描述馬爾可夫鏈，其中圖"n"的邊用從時刻"n"的狀態到時刻"n+1"的狀態的機率formula_3來標記。也可以用從時刻"n"到時刻"n+1"的轉移矩陣表示同樣的資訊。但是，馬氏鏈常常被假定為時齊的，在這種情況下，圖和矩陣與"n"無關，因此也不表現為序列。這些描述強調了馬爾可夫鏈與初始分佈formula_4無關這一結構。當時齊的時候，可以認為馬氏鏈是分配從一個頂點或狀態跳變到相鄰一個的機率的狀態機。可以把機器狀態的機率formula_5作為僅有元素formula_6的狀態空間為輸入的機器的統計行為分析，或作為初始分佈為formula_7狀態為輸入的機器行為，其中formula_8是艾佛森括號。一些狀態序列可能會有零機率的事件，對應多連通分量的圖，而我們禁止轉移機率為0的邊。例如，若"a"到"b"的機率非零，但"a"到"x"位於圖的不同連通分量，那麼formula_9有意義，而formula_10無意義。formula_11的過程。轉移機率與"n"無關。formula_12的過程。換句話說，未來狀態取決於其前"m"個狀態。It is possible to construct a chainfrom ("Xn") which has the 'classical' Markov property by taking as state space the ordered "m"-tuples of "X" values, ie. "Yn" =("Xn", "X""n"−1, ..., "X""n"−"m"+1)。瞬態演變.用"n"步從狀態"i"到狀態"j"的機率為formula_13而單步轉移是formula_14對於一個時齊馬爾可夫鏈來說：formula_15而formula_16"n"步轉移機率滿足查普曼-科爾莫戈羅夫等式，對任意"k"使得0 &lt; "k" &lt; "n"，formula_17其中"S"為此馬爾可夫鏈的狀態空間。邊緣分佈Pr("X""n" = "x")為第"n"次狀態的分佈。初始分佈為Pr("X"0 = "x")。用一步轉移把過程演變描述為formula_18。注意：上標是索引而非指數。性質.可還原性.馬爾可夫鏈是由一個條件分佈來表示的formula_19這被稱為是隨機過程中的“轉移機率”。這有時也被稱作是“一步轉移機率”。二、三，以及更多步的轉移機率可以導自一步轉移機率和馬爾可夫性質：formula_20同樣，formula_21這些式子可以透過乘以轉移機率並求formula_22次積分來一般化到任意的將來時間formula_23。週期性.邊緣分佈formula_24是在時間為formula_25時的狀態的分佈。初始分佈為formula_26。該過程的變化可以用以下的一個時間步幅來描述：formula_27這是Frobenius-Perron equation的一個版本。這時可能存在一個或多個狀態分佈formula_28滿足formula_29其中formula_30只是為了便於對變數積分的一個名義。這樣的分佈formula_28被稱作是“平穩分佈”。一個平穩分佈是一個對應於特徵值為formula_32的條件分佈函式的特徵方程。平穩分佈是否存在，以及如果存在是否唯一，這是由過程的特定性質決定的。“不可約”是指每一個狀態都可來自任意的其它狀態。當存在至少一個狀態經過一個固定的時間段後連續返回，則這個過程被稱為是“週期的”。各態歷遍性.具有重現性而不具有周期性叫做遍歷的。重現性包括區域性重現性。有限狀態空間.若狀態空間是有限的，則轉移機率分佈可以矩陣表示，該矩陣稱為轉移矩陣，記為P。其中處於formula_33的元素等於formula_34由於P的每一行各元素之和為1，且P中所有的元素都是非負的，因此P是一個右隨機矩陣。穩定分佈與特徵向量和單純形的關係.穩定分佈π是一個向量，它的元素都非負且和為1，不隨施加P操作而改變，定義為formula_35透過將這個定義與特徵向量進行比較，我們看到，這兩個概念是相關的，並且formula_36是由歸一化的轉移矩陣P的左特徵向量 e的倍數，其特徵值為1。如果有多個單位特徵向量那麼相應穩態的加權和也是穩態。但對於馬爾可夫鏈來說，我們更關心的是作為一些對初始分佈的序列分佈的極限的穩態。穩定分佈formula_38的值與狀態空間P有關，它的特徵向量保留各自的相對比例。因為π的成分為正且滿足約束條件formula_39，我們發現π與一個成分全為1的向量的點積是統一的，、π位於一個單純形上。有限狀態空間內的時齊馬爾可夫鏈.對於一個離散狀態空間，formula_40步轉移機率的積分即為求和，可以對轉移矩陣求formula_40次冪來求得。就是說，如果formula_42是一步轉移矩陣，formula_43就是formula_40步轉移後的轉移矩陣。如果轉移矩陣formula_42不可約，並且是非週期的，則formula_43收斂到一個每一列都是不同的平穩分佈formula_47，並且，formula_48,獨立於初始分佈formula_28。這是由Perron-Frobenius theorem所指出的。正的轉移矩陣是不可約和非週期的。矩陣被稱為是一個隨機矩陣，當且僅當這是某個馬爾可夫鏈中轉移機率的矩陣。注意：在上面的定式化中，元素formula_33是由j轉移到i的機率。有時候一個由元素formula_33給出的等價的定式化等於由i轉移到j的機率。在此情況下，轉移矩陣僅是這裡所給出的轉移矩陣的轉置。另外，一個系統的平穩分佈是由該轉移矩陣的右特徵向量給出的，而不是左特徵向量。轉移機率獨立於過去的特殊況為熟知的Bernoulli scheme。僅有兩個可能狀態的Bernoulli scheme被熟知為伯努利過程可反轉馬爾可夫鏈.可反轉馬爾可夫鏈類似於應用貝葉斯定理來反轉一個條件機率：formula_52以上就是反轉的馬爾可夫鏈。因而，如果存在一個π，使得：formula_53那麼這個馬爾可夫鏈就是可反轉的。這個條件也被稱為細緻平衡條件。對於所有的"i"求和：formula_54所以，對於可反轉馬爾可夫鏈，"π"總是一個平穩分佈。伯努利方案.伯努利方案是馬爾可夫鏈的一種特殊情形，其轉移機率矩陣有相同的行，即下一狀態均勻獨立於當前狀態。 僅有兩個可能狀態的伯努利方案是伯努利過程。一般的狀態空間.對於一般狀態空間上的馬爾可夫鏈的概述，詳見文章狀態空間可測的馬爾可夫鏈。應用.物理.馬爾可夫系統廣泛出現在熱力學和統計力學中，語音識別.隱馬爾科夫模型是大多數現代自動語音識別系統的基礎。網際網路應用.谷歌所使用的網頁排序演算法就是由馬爾可夫鏈定義的。如果formula_55 是已知的網頁數量，一個頁面formula_56 有formula_57 個連結到這個頁面，那麼它到連結頁面的轉換機率為formula_58，到未連結頁面的機率為formula_59， 引數formula_60 的取值大約為0.85。馬爾可夫模型也被應用於分析使用者瀏覽網頁的行為。一階或者二階的馬爾可夫模型可以用於對一個使用者從某一網路連結轉移到另一連結的行為進行建模，然後這些模型可以用於對使用者之後的瀏覽行為進行預測。經濟和金融.馬爾科夫鏈可以應用於金融與經濟中一系列現象的建模，包括資產價值與市場衝擊。1974年Prasad等人第一次應用馬爾科夫鏈於金融模型，另一個是James D. Hamilton 1989年應用的機制轉換模型，其中馬爾科夫鏈用來對高GDP增長速度時期與低GDP增長速度時期的轉換進行建模。生物數學.馬爾可夫鏈也有眾多的生物學應用，特別是增殖過程，可以幫助模擬生物增殖過程的建模。隱蔽馬爾可夫模型還被用於生物資訊學，用以編碼區域或基因預測音樂.馬爾可夫鏈也被用於演算法作曲，例如在Csound 、 Max和SuperCollider等軟體中。在一階鏈中，該系統的狀態是音符或音高，再構建每個音符的轉移機率，完成轉移矩陣。演算法根據轉移矩陣生成音符的輸出，該值可以是MIDI音符值、音高或其他量。馬爾可夫文字生成器.馬爾可夫過程，能為給定樣品文字，生成粗略，但看似真實的文字：他們被用於眾多供消遣的“模仿生成器”軟體。馬爾可夫鏈還被用於譜曲。資訊理論.用於計算馬爾可夫信源的極限熵歷史.馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數無限狀態空間是由俄國數學家柯爾莫果洛夫在1936年給出的。馬爾可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學重要課題是相聯絡的，但馬爾可夫尋求的似乎不僅於數學動機，名義上是對於縱屬事件大數法則的擴張。