前面的方法撞上的那道牆
回頭看看本級做過的一切。逆變換取樣與拒絕取樣把一條均勻串流變成某個分布的樣本；蒙地卡羅積分在那些樣本上把函數平均；重要性取樣則重塑樣本落點的位置以縮小變異數。這每一個都悄悄假設了同一件事：你能直接從你在意的那個分布抽出獨立樣本。對鐘形曲線或指數分布，沒問題。但驅動真實科學的那些分布，卻把這個假設狠狠打破。
標準的例子是貝氏統計。你有一個關於——比方說——五十個參數的後驗分布，你能寫下一條在任一點 x 都與該處密度成正比的公式 p(x)——但僅僅是成正比。真正的密度是 p(x) = g(x) / Z，其中 g(x) 是你算得出來的容易部分，而 Z 是個正規化常數，等於 g 在全部五十維上的積分。那個積分，正是維度詛咒使其無法計算的那頭高維巨獸。於是你被困了兩次：你找不到 Z；就算找得到，五十維的自訂分布也沒有逆變換公式可用。
拒絕取樣也救不了你。要用它，你需要一個處處都罩在密度上方的包絡，而在高維裡，幾乎每一個被提議的點都落在密度近乎零的區域而遭拒絕——接受率隨維度增長而崩向零。我們需要一個根本不同的想法：一種漫遊穿過該分布的辦法，它只需要相鄰兩點上的比值 g(x') / g(x)，永遠不碰那個可怕的常數 Z，也永遠不需要全域的包絡。那個想法，就是馬可夫鏈蒙地卡羅，簡稱 MCMC。
一條記得自己身在何處的隨機漫步
馬可夫鏈是一串狀態 x_0, x_1, x_2, ...，其中每個下一個狀態的隨機抽取只用到當前狀態——這條鏈除了此刻所站之處以外沒有任何記憶。想像一個漫步者在一片地景上踏步，每一步都僅憑它眼下的立足點來決定。你其實已經見過這副骨架、只是沒見過名字：像 x_{n+1} = M x_n + c 這樣的定常迭代就是一條確定性的鏈，而它的長期行為由譜半徑主宰。MCMC 把那一步從固定改成隨機，並反過來問一個鏡像的問題。
這裡有個讓整套方法成為可能的關鍵事實。許多馬可夫鏈，只要你讓它跑得夠久，就會忘掉起點、安頓進一個平穩分布——也就是在每個狀態被找到的固定機率，無論它從哪裡出發。漫步者待在任一區域的時間比例，不再依賴它起步之處，而收斂到一個固定的形狀。MCMC 以大膽的巧思把這件事倒過來用：我們不是拿一條鏈來問它的平穩分布是什麼，而是反向設計這條鏈，好讓它的平穩分布恰好就是我們想取樣的那個 p(x)。
鏈一旦建好，回報就很直接。讓漫步者跑很久，然後單純地把它拜訪過的狀態蒐集起來：x_1, x_2, ..., x_N。依照建構方式，這些就是來自 p(x) 的樣本——正是逆變換與拒絕在高維裡給不了你的東西。接著你就用蒙地卡羅一向的辦法去估計任何期望值：把你的函數在蒐集到的狀態上平均。整座建築就靠一個問題撐著：我們要怎麼設計一個隨機步伐，使它的平穩分布落在我們選的那個 p 上？答案是一條簡單得令人卸下心防的規則。
Metropolis-Hastings：先提議，再接受或拒絕
Metropolis-Hastings 演算法用兩個動作搭出一步。從當前點 x 出發，先用某條容易的隨機規則提議一個候選 x'——最簡單就是踏一小步高斯位移，x' = x +（一點點隨機推擠）。接著靠比較密度來決定是否接受這一步。關鍵在於，這個決定只用到比值 g(x') / g(x)，而在那個比值裡，未知常數 Z 完美地相消：g(x')/Z 除以 g(x)/Z 就只是 g(x')/g(x)。我們永遠算不出的那個東西，乾脆消失了。那一次相消，就是整套方法的祕密引擎。
Metropolis (symmetric proposal), one step:
propose: x' = x + step * randn() # random nudge from x
ratio : r = g(x') / g(x) # Z cancels — never needed
accept : if r >= 1 -> move to x' (uphill: always)
else with prob r -> move to x' (downhill: sometimes)
otherwise -> stay at x (count x AGAIN)
record the current state (x' or the repeated x), then repeat.把規則平白地讀一遍。如果候選點落在密度更高之處（r >= 1），就一律移過去——漫步者朝機率的主體往上爬。如果更低，仍以恰好等於 r 的機率有時移過去：一個機率只有一半的候選，大約有一半的時候被接受。這份願意往下走的溫和意願，正是讓這條鏈去探索整個分布、而非爬到那唯一的最高點就凍住的原因——那也正是困住一個天真最佳化器的同一個誘惑。為什麼恰恰是這個比值管用，靠的是一條一行的條件，叫做細緻平衡：它保證鏈一旦到達 p(x)，每一步都讓 p(x) 維持不變，於是 p 就是我們追求的那個平穩分布。
值得用一句話一提的近親是吉布斯取樣（Gibbs sampling），當你的分布是高維、而你恰好知道每個座標在其餘所有座標給定下的條件分布時，它就是自然的選擇。吉布斯不是一次推擠整個向量，而是一次更新一個座標：在其餘一切給定下重抽 x_1，再 x_2，如此繞著循環一路下去。它其實就是 Metropolis-Hastings 配上一個被巧妙挑選、接受率永遠是 1 的提議——每一步都被採納。當那些條件分布好處理時，吉布斯就繞開了調步長這件麻煩事。
樣本彼此相關所付的代價
MCMC 替你買來了不可能分布的樣本，卻索取一筆真實的費用，而對它的誠實，正是本節的全部重點。這些樣本並不獨立。因為每個狀態都是上一個的一小步推擠，相鄰的狀態強烈相關——第 1001 步的漫步者，就緊挨在它第 1000 步所站之處。你學過的那條樸素蒙地卡羅誤差律，誤差以 O(1/sqrt(N)) 下降，假設的是獨立抽取。對相關的抽取而言，N 個樣本所攜帶的資訊，少於 N 個獨立樣本，所以你的有效樣本數比原始計數 N 來得小——有時小得驚人。
鏈甩開它的相關、漫遊整個分布的速度，稱為它的混合——見混合時間。一條混合良好的鏈探索得快，它的樣本表現得幾乎像獨立樣本；一條混合差的鏈則原地洗牌，或許困在一個多峰分布的某一個峰裡，使其餘區域即使跑了一百萬步仍幾乎沒被拜訪。混合受同一類量主宰，就和普通的迭代一樣：鏈的轉移算子的第二大特徵值，正是線性系統那一級裡決定定常迭代速度的那個譜半徑的直接回響。越接近 1，混合越慢。
調參把這些線索綁在一起。提議的步長是一場拿捏的平衡：推得太小，幾乎每一步都被接受，但漫步者寸寸蠕行、幾乎不動、混合糟糕；推得太大，候選點落進低密度的荒野，幾乎一切都被拒絕，漫步者原地不動。甜蜜點接受相當比例的移動——隨機漫步 Metropolis 的經驗法則把它放在高維裡約 23% 的接受率附近，這常讓以為「越高越好」的人吃驚。弄錯了，鏈在理論上終究還是會收斂；但實務上，那個「終究」可能熬過你的耐心、也熬過你的計算預算。
誠實地說，MCMC 是什麼
退一步，看清這項成就的輪廓。MCMC 讓你能從一個只能算到未知常數倍的分布裡抽樣，而且是在本級其餘每個方法都乾脆失效的維度裡。它除了「算得出比值 g(x')/g(x)」這個能力之外，什麼都不需要——不需要正規化積分、不需要全域包絡、不需要逆變換公式。這正是它為何成為現代貝氏計算與統計物理的引擎，在那些領域裡，那個搆不著的常數 Z 是常態、而非例外。當你讀到某個模型是「用 MCMC 擬合的」，跑的正是這條配著接受／拒絕規則的隨機漫步。
並且把那些誠實的限制擺在眼前。MCMC 是漸近正確的，卻不提供乾淨的有限樣本誤差棒：你永遠不會知道自己已經混合，你只是找不到尚未混合的證據而已。它可能在一個多峰分布的單一峰裡停滯許久，還悄悄地報出一個自信而錯誤的答案。樣本是相關的，所以原始的 N 高估了你的資訊。這一切都不會讓這個方法少一分非凡——它讓這個方法成為一件要謹慎揮舞的工具。用得好，配上診斷與對自己的鏈一份健康的疑心，它便能觸及那些對你學過的其餘一切都徹底搆不著的分布。