馬可夫鏈(Markov Chain)介紹

馬可夫模型大意是:選一個狀態作為起點,然後沿著邊隨意走訪任何一個狀態,一直走一直走,沿途累計機率,走累了就停在某個狀態。

馬可夫模型一共有 N 個狀態,通常標作 s₁ 到 sN 。 N 是我們自行設定的常數。全部狀態構成的集合,標作大寫 S 。每一個狀態都會射出 N 條邊,這 N 條邊分別連向每一個狀態,這 N 條邊的數值都是機率,這 N 條邊的數值皆介於 0 到 1 ,這 N 條邊的數值總和必為 1 ,滿足機率公設。

一條由狀態 sᵢ 到狀態 sⱼ 的邊,其數值通常標作 aᵢⱼ 。亦可標作條件機率 P( sⱼ | sᵢ ) ,意思是現在在狀態 sᵢ 、要來去狀態 sⱼ 。亦可套用稍後提到的狀態序列,標作 P( qt+1 = j | qₜ = i ) 。全部邊構成的集合,標作 A 。通常把 A 看作一個 N×N 矩陣。馬可夫模型的 A 的數值,會隨時間及來源狀態而改變。

寫程式時,我們可以利用圖的資料結構 adjacency matrix 儲存全部的數值。當 A 有很多數值是零,去掉一些邊之後,也可以改用 adjacency lists 。

主要作用

  • 預測未來發展-體積微小、性質穩定的東西(例如空氣分子、細胞),適合使用 Markov Chain 模擬未來發展(例如氣體擴散、細胞繁殖)。

名詞定義

  • reducibility :狀態 x 到 y ,有路可通(機率大於零)。即是圖論 Reachability 。
  • periodicity :狀態 x 到 x ,所有走法,找出步數規律。即是找出經過 x 的環。有如圖論 Cycle Basis 。
  • recurrent :狀態 x 出發,所有路線都走回 x ,無法擺脫輪迴。