關於此實驗
馬可夫鏈會在狀態之間隨機跳轉，但每次跳轉的機率只取決於它目前所處的狀態，而不取決於它是如何到達那裡的。明天的天氣取決於今天的天氣，網路瀏覽者接下來造訪的頁面取決於目前頁面，分子的下一個形態取決於它現在的形態。無論鏈從何處開始，性質良好的鏈都會忘記起點，並趨於穩態 π。編輯轉移機率，執行這條鏈，觀察長期頻率和分布 pₙ 如何收斂至 π。
學習目標
- 寫出馬可夫鏈的轉移矩陣，並檢查每一列的總和是否為 1
- 將 n 步後的分布計算為 p₀Pⁿ
- 透過求解 πP = π 找出穩態分布
- 探討收斂速度與 P 的第二大特徵值之間的關係
- 辨識不會收斂的鏈，例如週期鏈
使用方法
- 1在天氣鏈中，按下「執行」並觀察代幣。接著按下「1000 步」。長條與虛線有多接近？
- 2更改初始狀態。穩態會改變嗎？上方圖表的前段會改變嗎？
- 3手動檢查穩態：用 π 乘以矩陣，並證明結果仍是 π。
- 4選擇「緩慢混合」。上方圖表需要幾步才能穩定下來？將它與 |λ₂| 和讀數比較。
- 5選擇「週期循環」。為什麼上方圖表始終無法穩定下來，儘管各狀態所占的時間比例已經穩定？
- 6選擇「立即遺忘」。為什麼分布只需一步就能達到 π？
模型
假設
- 有三個狀態，且轉移機率不隨時間變化。每一列都透過兩個滑桿編輯；剩下的機率就是留在原狀態的機率。
- 樣本路徑由帶有種子的隨機數產生器生成，因此相同的執行編號總會得到相同的路徑；選擇「新執行」會更改種子。
- 透過精確求解線性方程組來求出穩態。要將誤差控制在 1 % 以內，所需步數估計為 ln 100 / (-ln |λ₂|)。
在課堂上試試這個實驗
- Q1對於 P = [[0.9, 0.1], [0.5, 0.5]]，求其平穩分布。
- Q2證明：只要 P 的每一欄總和也為 1，均勻分布就是平穩分布。
- Q3某個馬可夫鏈滿足 |λ₂| = 0.95。它大約需要多少步才能忘記初始狀態？
- Q4解釋為什麼「週期循環鏈」有平穩分布，但 pₙ 不會收斂到該分布。
- Q5Google 最初的 PageRank 是隨機瀏覽者的穩態分布。為什麼要加入一個以小機率跳轉到任意頁面的機制？
常見問題
這裡的「無記憶」是什麼意思？
未來只透過目前狀態依賴過去。如果你知道今天下雨，即使知道上週是晴天，也無法因此進一步了解明天的情況。
每個鏈都有穩態嗎？
每個有限馬可夫鏈都至少有一個平穩分布。如果每個狀態都能到達其他所有狀態，該分布就是唯一的；此外，如果該鏈也不是週期性的，無論從哪個狀態開始，pₙ 都會收斂至此分布。
馬可夫鏈有哪些用途？
它應用於排隊與可靠度模型、遺傳學、語音辨識、文字預測、金融，以及馬可夫鏈蒙地卡羅方法。此方法會建立一條以你想抽樣的分布為穩態分布的鏈。