速率是固定的——所以去攻擊那個常數
上一篇留給你一條定律，既解放又惱人：一個蒙地卡羅估計的誤差以 O(1/sqrt(N)) 縮小，與維度無關。解放，因為這個速率完全無視維度詛咒。惱人，因為 1/sqrt(N) 很慢——要多得一位正確的小數，你得把樣本數乘上一百。而本篇要誠實面對的高牆就在這裡：再怎麼聰明都改不了那個指數。平方根速率被烙進了中央極限定理，我們不會打贏它。
但更仔細看完整的誤差公式。平均值的標準誤是 sigma/sqrt(N)，其中 sigma 是你正在平均的那個單一隨機量的標準差。這個分式裡有兩個旋鈕，不是一個。猛轉 N 是蠻力旋鈕，而它很貴。另一個旋鈕是 sigma——你所抽樣那東西的散布。如果你能把問題改寫成「同樣的答案、卻以更小的 sigma 跑出來」，整條誤差曲線就在每一個 N 上、免費地往下掉。這就是變異數縮減的全部精神：別碰 1/sqrt(N) 速率，去縮小乘在它前面的常數。
值得把這筆帳算清楚，因為它聽起來不起眼，其實不然。假設某個技巧把變異數 sigma^2 砍掉十倍。既然誤差按 sqrt(sigma^2/N) 縮放，把變異數砍十倍恰恰等同於把 N 乘十倍——你用十分之一的樣本、或十分之一的執行時間，就達到同樣的準確度。一個幾乎不費成本就能套用的聰明變異數縮減方案，因此可能值一個 10 倍或 100 倍的加速。這就是為什麼它自成一門學問、而非一條註腳：在認真的蒙地卡羅裡，真正的勝利通常就藏在縮小變異數這件事上。
重要性抽樣：把飛鏢花在有戲的地方
想像要估計一個函數下方的面積，它在 [0, 1] 的絕大部分又平又小，卻在 x = 0.8 附近有一根又高又窄的尖峰。普通蒙地卡羅把飛鏢均勻地撒，所以絕大多數落在無聊的平坦區、幾乎貢獻不了什麼有用的東西，而尖峰——它握著答案的大部分——只拿到寥寥幾次擊中。那少數幾次擊中起伏劇烈：抓到尖峰的頂就讓估計暴衝，沒抓到就讓它塌陷。這就是高 sigma 的局面，而均勻抽樣正在糟蹋它的力氣。
重要性抽樣的解法，是刻意在被積函數大的地方抽樣。你不再均勻地抽點，而是從一個你選定的分布 p(x) 抽，讓它模仿被積函數的形狀——尖峰附近抽得密、平坦處抽得疏。但更常在尖峰附近抽樣，若不處理就會把它算過頭。於是你替每個樣本除以 p(x) 來修正：被 p 弄得常見的點權重壓低、被它弄得稀有的點權重抬高。這套記帳是精確的——估計保持無偏、瞄準真正的答案——但加權後那些值的散布卻可能小得驚人。
Estimate I = integral of f(x) dx over the domain.
Plain Monte Carlo (uniform on [0,1]):
draw x_1..x_N uniform
I_hat = (1/N) * sum f(x_n)
Importance sampling (draw from your chosen p):
draw x_1..x_N from density p(x)
I_hat = (1/N) * sum f(x_n) / p(x_n)
the ratio f/p is what you actually average
Goal: pick p so that f(x)/p(x) is nearly CONSTANT
-> tiny variance. Perfect p (impossible): p proportional to f.魔法與陷阱，都住在同一句話裡：當比值 f(x)/p(x) 最接近常數時，變異數最小。如果你能選 p 恰好正比於 f，每個加權樣本都會回傳一模一樣的值，變異數會是零——一個樣本就釘死答案。那個完美的 p 當然搆不到（知道它就等於已經知道積分了），但它指出了目標：把 p 的形狀塑造得像 f。把 p 弄得大致正確，sigma 就崩塌；把它弄得糟糕透頂，你會比普通蒙地卡羅差得多——挑一個恰好在 f 大的地方很小的 p，少數樣本落在那裡帶著巨大的權重 f/p，變異數甚至能爆到無窮。重要性抽樣是把利刃：強大，而握錯了它會割傷你。
分層抽樣：先把房間分隔，再抽樣每個角落
第二個、較溫和的點子，攻擊的是另一個浪費來源。當你把 N 支均勻飛鏢撒過 [0, 1]，純粹的運氣會把有些擠成團、別處留下空隙——而那種結團本身就是一個變異數來源，與被積函數的形狀無關。分層抽樣用強制手段除掉結團。把定義域切成 k 條相等的條帶，並堅持每條帶恰好拿到 N/k 個樣本，而不讓機運來決定。在每條帶之內你仍隨機抽樣，所以估計保持誠實，但覆蓋現在保證在整個定義域上都是均勻的。
為什麼強制均勻覆蓋有幫助？因為它精準地切除了變異數裡來自樣本恰好落在哪的那一部分，只留下來自 f 在每條帶之內如何擺動的那一部分。把條帶弄窄，f 在每條帶裡看起來就近乎平坦，於是那殘餘的變異數也跟著縮。分層永遠不會把事情弄得更糟——最壞也只是打平普通蒙地卡羅——而且在低維裡幾乎不費力就能實作。它的弱點又是詛咒：把 d 個軸各切成 k 條帶要 k^d 個格子，所以在高維裡你沒辦法把每個軸都分層。實務上的折衷——拉丁超立方抽樣——一次只把每個軸做一維的分層，便宜地擷取了大部分好處。
控制變量與對偶配對：便宜、近乎免費的勝利
第三族利用的是你已經知道的東西。控制變量是這樣運作的：假設在你真正想要的量 f 旁邊，有一個相關的量 g，它逐個樣本地與 f 一起上下起伏，而你恰好確切知道它的真實平均。那麼每當你隨機的 g 跑得高於它已知的平均，那就是一個暗示：你隨機的 f 大概也跑高了——於是你把 f 的估計往下推同樣的好運份量，反之亦然。你正在減去 f 的擺動裡那一份 g 能預測的部分，只留下真正無法預測的殘餘。f 與 g 之間的相關越強，你抵消的擺動越多、變異數越小。
對偶變量的技巧更簡單，便宜得近乎好笑。注意若 u 是一個均勻樣本，那麼 1 - u 也是一個完全合法的均勻樣本——它的鏡像。所以成對地產生樣本：一個來自 u，它的雙胞胎來自 1 - u。如果被積函數是單調的，那麼當 u 把第一個估計推高，它的鏡像 1 - u 就把第二個推低，而它們的平均抵消掉大部分擺盪。你幾乎不花額外力氣就得到變異數縮減——反正你本來就要抽那些隨機數，把它們反射只花一次減法。這是整門學問裡最接近免費午餐的東西，不過老實說，它只在那個鏡像對稱恰好與你的函數對上時才有幫助。
誠實的界限，以及這條路指向何方
握緊這份誠實的摘要，因為這些技巧很容易被誇大。這裡每個方法都是縮小 sigma 的辦法；沒有一個碰得到 1/sqrt(N) 速率，所以每個都是常數倍的加速，而非種類上的改變。每個也都帶著一個生效的條件：重要性抽樣需要一個真正神似被積函數的提案分布、分層需要維度夠少、控制變量需要一個有已知平均的相關量、對偶需要對的對稱。盲目套用其中之一，你可能毫無所獲，或者——尤其對重要性抽樣——把變異數弄得糟糕透頂。估計自始至終保持無偏（它仍瞄準真正的答案）；這些技巧在適配時所買到的，是繞著那個瞄準點更緊的散布。
還有一個這些方法都解不了的問題，替它命名正好接到最後一篇。重要性抽樣假設了你能從你選的 p 抽出樣本，而上一篇的抽樣工具——反轉法、拒絕法——在低維裡運作得漂亮。但在物理、統計、機器學習裡最要緊的那些分布，活在數百或數千維裡，你往往連把它們歸一化都辦不到，更別說反轉它們、或為拒絕法給它們設界。對那些分布，唯一還能取到樣本的辦法，是走一趟受引導的隨機漫步，讓它更常造訪高機率的區域，把正確的分布建構成一條遊蕩的鏈在長程上的行為。
那正是本級下一篇、也是最後一篇的跳躍：馬可夫鏈蒙地卡羅。它把至此每個方法那種乾淨的獨立性，換成沿著一條鏈彼此相關的鄰居樣本——一種新的、更微妙的成本，並帶著它自己的診斷，判斷鏈是否已遊蕩夠久而值得信賴。眼下，把本篇的教訓帶著走：1/sqrt(N) 速率是一條你遵守的定律、不是一面你打破的牆，而高效蒙地卡羅的全部手藝，就是耐心地縮小乘在它前面那個常數的藝術。