馬可夫鏈

佩龍–弗羅貝尼烏斯定理(Perron-Frobenius theorem)

/ peh-RON froh-BAY-nee-oos /

為什麼轉移矩陣總有一個平衡,而且它唯一又可抵達?深層的答案來自線性代數而非機率:佩龍–弗羅貝尼烏斯定理,一個關於非負元素矩陣的強大結果。它正是平穩分布存在與唯一、以及 P^n 收斂背後的結構性原因。

定理說,一個元素非負的不可約矩陣有一個最大的特徵值,它是實的、正的、且單純(無重根),其特徵向量的元素全部嚴格為正 —— 而沒有其他特徵向量能取成全正。對隨機矩陣 P(列加總為 1),那個首要特徵值恰好是 1,所有其他特徵值的絕對值至多為 1,而那個正的左特徵向量、歸一化到加總為 1,正是解 pi P = pi 的平穩分布 pi。所以「存在一個在每個狀態上都有正權重的唯一平衡」,不過是佩龍–弗羅貝尼烏斯套用到不可約鏈上的結果。

它也解釋了收斂與其速度。若鏈非週期,特徵值 1 是嚴格的冠軍:其他每個特徵值的絕對值都嚴格小於 1,於是它們對 P^n 的貢獻衰減,只留下平穩的部分 —— 因此 P^n 收斂。第二大特徵值的絕對值掌控速度有多快:1 與它之間的間隙決定了混合速率。週期鏈有其他特徵值也落在單位圓上(如 -1),這正是它振盪、無法收斂的原因。PageRank 讓佩龍–弗羅貝尼烏斯名聞遐邇:Google 的排名就是整個網路那個巨大隨機矩陣的正佩龍特徵向量。

天氣 P 的兩列為 (0.8, 0.2) 與 (0.4, 0.6)。它的特徵值是 1 與 0.4。佩龍–弗羅貝尼烏斯:1 是最大且單純的,其正的左特徵向量為 (2/3, 1/3) —— 即平穩分布。另一個特徵值 0.4 的絕對值小於 1,所以與平衡的距離每一步大約以 0.4^n 縮小 —— 因為 0.4 很小,故收斂很快。

特徵值 1 給出平穩分布;下一個特徵值的大小決定收斂的速度。

佩龍–弗羅貝尼烏斯需要不可約性,首要特徵向量才會唯一且嚴格為正。可約矩陣(多個閉類)可以有數個獨立的平衡 —— 唯一性並非白給的。

又称
Perron-FrobeniusPerron eigenvalue佩龍-弗羅貝尼烏斯定理