線性代數 · 馬可夫鏈

馬可夫鏈

馬可夫鏈會在不同狀態間隨機轉移,下一個狀態的機率只取決於目前的狀態。將這些機率寫成轉移矩陣P,今天的分布右乘P就是明天的分布。重複計算,往往會趨近滿足πP = π的穩態分布π,也就是特徵值1的左特徵向量。

圖中的馬可夫鏈

在馬可夫鏈中,下一個狀態的機率只取決於目前的狀態。這裡的三個狀態是晴、陰、雨。轉移矩陣PP的第ii列,列出今天在狀態ii時明天各種天氣的機率,所以每一列都是機率向量。若今天的分布是列向量pp,明天就是pPpP,nn天後就是pn=p0Pnp_n = p_0 P^n。三個狀態的任何分布都可用三角形內的一點表示。頂點代表某個狀態的機率為1,三個機率則是三個頂點的權重。深色點代表PP的各列,藍點是起點,紅線依序連接p0,p1,p2,…p_0, p_1, p_2, \dots。

走一步會發生什麼

每走一步,各頂點就移到對應的那一列:今天確定是晴天,明天的分布就是第一列。其他分布pp都是各頂點的加權平均,於是pPpP就是以相同權重對各列取平均。整個三角形因此落進各列張成的較小三角形。走兩步就落進P2P^2各列張成的三角形,依此類推。若PP的某個次方所有元素都為正,這些層層內縮的三角形就會收向一點:穩態分布π\pi。

為什麼π是特徵向量,以及pₙ靠近它的速度

不動點滿足πP=π\pi P = \pi,所以π\pi是特徵值1的特徵向量,更精確地說,是左特徵向量(用行向量表示即PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T})。差向量p0−πp_0 - \pi的分量總和為0。在這個子空間上,PP的特徵值是其餘兩個λ2,λ3\lambda_2, \lambda_3。沿特徵方向的向量每走一步會乘以對應的特徵值。兩個絕對值都小於1時,pnp_n趨近π\pi,由較大的絕對值∣λ2∣|\lambda_2|決定主要的收斂速率。天氣鏈中∣λ2∣≈0.462|\lambda_2| \approx 0.462,若起始分布在λ2\lambda_2的特徵方向上有分量,nn夠大時每一步剩下的距離略少於前一步的一半。特徵值為複數時,路徑會一邊縮小一邊旋轉。

分布何時不收斂

在循環中,晴、陰、雨依序重複。另外兩個特徵值的絕對值為1,所以除非從π\pi出發,pnp_n會一直繞下去。若有兩個吸收態,晴與雨都會持續,特徵值1出現兩次。任何晴雨混合分布都保持不動,因此pnp_n仍會收斂,只是結果取決於起點。對有限狀態的鏈來說,pnp_n從任何起點都趨近同一個π\pi的充要條件,是恰有一個封閉的互通類,而且這個類是非週期的。類內各狀態彼此可達,進入後不會離開。若有某個次方PmP^m的所有元素都為正,就足以保證收斂。

值得注意

  • 不論從哪種天氣開始,穩態分布都給出久遠以後某一天天氣的機率;天氣本身每天仍可能改變。
  • 狀態多於三個時,所有分布填滿三角形的高維版本,也就是單純形。同樣的推理依然適用。

操作

  • 拖曳深色點可修改轉移矩陣的一列,拖曳藍點可改變起始分布。用方向鍵可將取得焦點的點每次移動0.01。

相關概念