ComputerScience－馬可夫鏈

簡介：馬可夫鏈 （Markov chain） 或稱離散時間馬可夫鏈（Discrete-time Markov chain，縮寫為DTMC）是一種隨機過程，在數學上只要這傳遞矩陣有一些好的性質，就可以證明經由這馬可夫鏈抽樣的分佈會收斂到想要的機率分佈。



Markov Chain可以看成圖論的有向圖：狀態是點，狀態轉移是邊，機率是邊的權重，轉移矩陣是資料結構adjacency matrix。主要功用是預測未來發展。體積微小、性質穩定的東西（布朗運動就可以用此來說明），適合使用其來模擬未來發展，同時也是物理模擬、化學模擬領域的重要工具。

該過程要求具備「無記憶」的性質：下一狀態的機率分布只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定類型的「無記憶性」稱作馬可夫性質。

選定一個狀態作為起點，不斷移動（不斷轉移狀態、狀態不斷變化），走出一條路線。考慮所有可能的路線，每一條路線都可以明確計算其機率。

許多個狀態，每個狀態都可以轉移到其他狀態，轉移機率的總和都是 1 。轉移機率習慣寫成一個矩陣，稱作「轉移矩陣 Transition Matrix 」、「隨機矩陣 Stochastic Matrix 」。

有詳細的說明動畫，連結請點此。

介紹幾個術語：

Reducibility：狀態 x 到 y ，有路可通（機率大於零）。即是圖論 Reachability。

Periodicity：狀態 x 到 x ，所有走法，找出步數規律。即是找出經過 x 的環。有如圖論 Cycle Basis。

Recurrent：狀態 x 出發，所有路線都走回 x ，無法擺脫輪迴。

參見：演算法筆記

學習資源一

學習資源二