積分中的維度災難（curse of dimensionality in integration）

那些精緻的求積法則——辛普森、高斯、龍貝格——在一維中效率高得耀眼。要在正方形、立方體，或一百維的盒子上積分，最顯然的做法是鋪一張網格，沿每個軸套用一維法則（張量積）。在二維或三維，這行得通。在高維，它災難性地崩潰，而這場崩潰就是維度災難。

數一數點。一個好的一維法則每軸或許用 m 個節點。d 維上的張量積法則於是需要 m^d 個點——成本隨維度「指數」成長。每軸用適中的 m = 20 個節點，三維花 8,000 次計算（沒問題），但十維花 20^10，約十兆次，而二十維在任何將會存在的電腦上都無望。更糟的是，達到的精度也劣化：每軸 O(m^-p) 的法則，以總工作量 N = m^d 來看只剩 O(N^(-p/d))，所以每多一維就稀釋收斂速率。高維積分不斷出現——統計力學、貝氏推論、多資產金融衍生品、機器學習——所以這是一道真實而頻繁的牆。

這場災難正是蒙地卡羅積分存在並在高維稱霸的原因。蒙地卡羅藉著在隨機取樣點上平均被積函數來估計積分；無論維度多少，它的誤差都按 1/sqrt(N) 下降。那 1/sqrt(N) 的速率在一維中緩慢而不起眼——那裡高斯把它輾壓——但它對維度的「無關性」才是重點：在 50 維中，一個忽略 d 的 1/sqrt(N) 方法勝過任何速率被 d 除的網格方法。準蒙地卡羅（低差異序列）與稀疏網格等改良把前沿再往前推，但根本訊息屹立不搖：超過區區幾維，經典張量積求積就是錯的工具。