馬可夫鏈與 PageRank：為網路排序的特徵向量

當矩陣是一張機率表

一個隨機（馬可夫）矩陣 P 的元素非負、每一行之和為 1：元素 P[i,j] 是一步內從狀態 j 轉移到狀態 i 的機率。若 p 是當前在各狀態上的分布，則 P p 是一步之後的分布，P^t p 是 t 步之後的分布。這不過是矩陣乘法在為隨機遊走記帳。

# Weather chain: states = {Sunny, Rainy}, columns sum to 1
#            from Sunny   from Rainy
P = [ [ 0.9 ,        0.5 ],   # to Sunny
      [ 0.1 ,        0.5 ] ]  # to Rainy
# start certain it is Sunny:  p0 = (1, 0)
# p1 = P p0 = (0.9, 0.1)
# p2 = P p1 = (0.86, 0.14)
# p_inf       = (0.833..., 0.166...)   <- it settles down

穩態就是一個特徵向量

一個再走一步也不變的分布 pi 滿足 P pi = pi——它是 P 的、對應特徵值 1 的特徵向量。這個特殊的特徵向量就是穩態分布。每個隨機矩陣都有特徵值 1（全 1 列向量是它的左特徵向量），所以穩態總是存在；問題在於它是否唯一、以及你是否真的會收斂到它。

Perron–Frobenius 定理給出了答案：若 P 的元素嚴格為正（或更一般地是不可約且非週期的），則特徵值 1 是單根且其模嚴格大於其餘所有特徵值，穩態分布唯一且嚴格為正，並且 P^t p 從任意起點都收斂到它。

PageRank：網路圖上的隨機衝浪者

把網路建模為一張圖：處於某頁的衝浪者均勻隨機地選一個出鏈。這就由鄰接矩陣定義出一個隨機矩陣。它的穩態分布按衝浪者落在各頁面上的頻率為頁面排序——這就是 PageRank。兩個修補讓 Perron–Frobenius 乾淨地適用。

1. 懸掛節點修補：沒有出鏈的頁面以均勻隨機的方式跳轉到任意一頁。
2. 阻尼：以機率 1 - d（通常 d = 0.85）衝浪者隨機跳到任意頁面，從而保證矩陣元素嚴格為正。
3. 結果是一個正的隨機矩陣 G = d P + (1 - d)(1/n) 11^T，它有唯一的穩態分布。

如何計算：冪法

面對數十億頁面，你絕不會顯式構造 G 或對它做對角化。你只需迭代：從均勻分布出發，反覆施加這個映射，直到它不再變化。由於特徵值 1 嚴格佔優，這個冪法會收斂到主特徵向量——也就是穩態分布——其速度由阻尼因子決定。

# PageRank via the power method (no dense matrix needed)
r = ones(n) / n            # uniform start
repeat:
    r_new = d * (P @ r) + (1 - d) / n   # apply G implicitly
    if ||r_new - r||_1 < tol: break
    r = r_new
return r                   # r is the stationary distribution