動機
模擬把難以直接完成的計算,轉成電腦可以重複進行的實驗。複雜區域的積分也許難以解析求值,但抽取一點並計算函數值卻可能很容易。電腦沒有消除不確定性,而是把問題轉成可以用概率分析誤差的計算。要讓大量輸出有意義,必須先指定估計的對象,以及把輸出與目標連接起來的假設。
三種誤差需要分開。數學模型可能簡化了研究對象;數值模擬器可能再以離散化近似該模型;最後,有限次 Monte Carlo 平均會在模擬器輸出的期望附近波動。增加重複次數主要處理第三種誤差,不能自動消除模型誤差或離散偏差。即使平均值看來十分穩定,也可能穩定地估計了錯的目標。
以單位區間上的積分為例,均勻取一點並計算函數,可把面積寫成期望。不同機器可以各自完成多次重複,並用上一單元的摘要公式合併結果。然而,摘要的算術正確只是論證的一部分;各次重複還必須具有分析中指定的聯合分佈。若所有工作節點意外採用同一條隨機序列,平行處理可能根本沒有增加獨立資訊。
定義
設 在 上均勻分佈。對可積函數 ,目標積分可寫成 。
定義 2.1.1
(重複與普通 Monte Carlo 估計量)
設 是一次完整模擬重複的輸出,且期望 存在。由 的獨立同分佈副本 組成普通 Monte Carlo 估計量:
定義 2.1.2
(無偏與均方誤差)
若 ,稱 的估計量 無偏。其均方誤差是 。
有有限二階矩時,均方誤差等於方差加偏差的平方。無偏並不保證某一次結果接近真值;波動很小也不能排除相對於真正研究目標的系統偏移。
定義 2.1.3
(標準誤及其估計)
若 的方差是有限的 , 的標準差稱為標準誤。當 ,以樣本方差 估計它:
單次輸出的標準差描述模擬結果的變動,標準誤則描述其平均值的變動。除以 必須由獨立性或其他適當理論支持,不能只因輸出檔有 行便套用。
概念視角幾何
樣本方差是投影的長度平方
把輸出寫成 中的向量 ,其中 。殘差 組成 ,而 是到與 垂直的超平面的正交投影。因此 。當 時,其期望是 :分母數的正是擬合均值後剩下的維數。
定義 2.1.4
(置信程序與覆蓋率)
置信程序是由數據產生隨機區間的規則。其覆蓋率是在假設成立時重複應用該規則、區間包含目標的概率。
覆蓋率不是單靠頻率派論證就能事後賦予固定參數的概率。我們先推導有限樣本界,再區分它與正態近似。
定義 2.1.5
(可重現性)
若指定的計算輸入及執行選擇足以讓計算重做並得到相同結果,稱模擬可重現。
種子只是其中一項;還可能需要生成器算法、函數庫版本、串流分派、模型參數、樣本數及歸約次序。確定性的偽隨機序列並不真的是無限個獨立隨機變量。概率分析是良好模擬程序的數學模型,實際使用仍要檢查生成器及抽樣實作是否合適。
定理 / 命題
定理 2.1.6
(獨立重複的均值與方差)
設 獨立同分佈,均值為 、有限方差為 ,且 預先固定。則
若 ,樣本方差滿足 。
命題 2.1.7
(有限樣本的誤差保證)
在相同假設下,任意 都有
若已知確定的有效界 ,且 ,選取 ,可保證誤差小於 的概率至少為 。此界可能保守;把隨機樣本方差直接代替 ,不會自動保留這項保證。
證明思路
證明
(展開中心化總和及樣本方差恆等式)
期望的線性性給出無偏,這一步不需要獨立。計算方差時,把每項減去均值,再展開總和的平方。獨立性令不同項的交叉期望為零,剩下 個 ,除以 後得到 。估計量無偏,所以均方誤差等於它的方差。
樣本方差則用恆等式:
右方兩項的期望分別是 與 ,故相減後除以 即得結論。這也解釋為何樣本方差的分母與觀測記錄的描述性方差不同。
證明透視
獨立性在哪裏用到,在哪裏不用
的無偏性只用線性性,所以重複之間有任何相依都仍成立。獨立性只在一處用到:展開 的平方後有 個交叉項 ,要靠不相關才全部為零。樣本方差一步再次用到這個方差公式,即 。恆等式本身是確定性的代數,所以分母 正是從 減去單一個 而來。
概率界只需要剛證明的方差公式。
證明
(對平方誤差應用 Markov 不等式)
再對非負變量 使用 Markov 不等式。其期望是 ,而誤差至少為 的事件,迫使平方誤差至少為 。這就是此處的 Chebyshev 界。樣本數公式只是移項;若方差為正,任何有限樣本數都不能令這個界變為零。若要求確定性的零誤差,需要另一種論證。
獨立同分佈且有正的有限方差時,中心極限定理還說明標準化平均漸近服從標準正態。它支持以約 個估計標準誤形成名義 區間,但這是漸近近似,並非上述有限樣本界的直接結論。高度偏斜、罕見事件及小樣本都可能令近似很差。
例題詳解
例題 2.1.8
(平方積分與預算規劃)
令 。積分得到 、,故 。 時,標準誤為 。由於它按 縮小,要減半就需四倍獨立重複。
若要求絕對誤差小於 、失敗概率不多於 ,有限樣本界要求 ,故 次足夠。這裏用的是教學例子已知的真實方差。實際問題中,先導實驗可協助規劃,但先導樣本方差本身不是確定上界。若只知道 ,可用有效界 ,得到較保守的 次預算。
例題 2.1.9
(罕見事件與看似完美的輸出)
令 是概率 的事件指示變量。方差為 。取 ,比例的標準誤為 。Chebyshev 界說絕對誤差至少 的概率不多於 。若正態近似合適,名義區間半寬約為 ;兩者屬不同類型的結論。
改成 ,一萬次獨立試驗完全沒有事件的概率是 ,約 。這時觀測樣本方差是零,但不能報告零不確定性;實驗沒有證明事件不可能發生。抽樣預算必須足以分辨目標的尺度,尤其在要求相對精度時。
例題 2.1.10
(對偶配對與公平的成本比較)
每次抽一個 ,改用 。由於 與 都均勻分佈,均值仍是 。化簡得 ,對其平方積分後減去 ,得到方差 。
同樣有 次函數求值預算時,普通方法平均 個獨立輸出,方差為 。對偶方法平均 個獨立配對輸出,方差為 ,小八倍。每對內部刻意相依,不同對之間則必須獨立。比較時要計函數求值數,不能只計平均的項數;若配對有額外開銷,實際時間效率還需另行測量。
對偶法並非必然改善。若 ,便有 ,每對只是重複同一數值。在固定求值預算下,相對於獨立抽樣浪費了一次求值。改善與否取決於所選函數能否產生有利的負協方差。
常見錯誤
反例模式
長輸出檔不等於大獨立樣本
錯誤說法是:平均 個輸出,方差總會除以 。抽一次有正的有限方差的 ,然後令所有 。每項邊際分佈都正確,但平均仍是 ,任何 的方差都一樣。一般平均的方差還包含交叉協方差。修正說法必須加入獨立性,或另有明確控制相依性的分析。各節點重用完全相同的隨機串流,就可能在程式中造成此問題。
常見錯誤
(把固定種子或相鄰種子當作獨立性的證明)
固定種子只能證明可重做,不能證明無偏、獨立或準確。平行計算應使用已記錄的子串流分派或生成器支援的獨立串流設施。選取相鄰整數種子本身不是串流獨立的證明。每個節點負責哪些重複索引也應有記錄,並確保重試不會多接納結果,或選擇性丟棄難以完成的輸出。
常見錯誤
(區間看來夠好便停止)
當估計區間「已經夠窄」就停止,也改變了程序。固定 的定理不能自動用於依數據決定的停止時間。此處應預先決定預算,或改用本身具有效保證的序貫方法。先導實驗也要清楚標示,說明它怎樣影響最終估計量的設計。
總結
Monte Carlo 的準確度取決於完整重複的分佈及各重複之間的關係。無偏性、方差與可重現性回答不同問題。有限方差給出平方根樣本數的誤差尺度及保守有限樣本界。方差縮減應按相同計算預算比較;模型誤差與離散誤差則要另外分析。
練習
練習 2.1.11
(設 。求期望及方差;取 ,用 Chebyshev 不等式估計樣本平均偏離目標至少 的概率上界。)
基礎
解答 · 答案
由 、,得期望 、方差 。樣本平均的方差為 ,故概率不多於 。這是上界,不是等號,也不是正態近似的概率。
練習 2.1.12
( 次獨立重複的標準誤是 。輸出分佈不變時,要降至 需多少次?指出這種縮放不能處理甚麼。)
基礎
解答 · 答案
目標標準誤是原來的四分之一,按 規律需十六倍次數,即 。這不能修正模型誤差、離散偏差、實作引入的相依性,亦不能忽略輸出方差改變的情況。
練習 2.1.13
(對 形成對偶配對輸出,求其方差並與兩次獨立求值比較。為何此例不能建立對所有被積函數都成立的規則?)
核心
解答 · 答案
配對平均恆等於 ,方差為零。兩次獨立均勻求值的平均方差則是 。精確抵消利用了函數的線性及兩個自變量之和固定。對稱函數如 的兩個輸出相同,不會有這種抵消。
練習 2.1.14
(四個節點各自重用相同的 個獨立數學輸出,歸約器平均全部 個記錄。以單次方差 表示估計量方差,並指出有助發現問題的重現記錄。)
核心
解答 · 答案
每個不同輸出出現四次,記錄平均等於最初 個輸出的平均,方差為 ,而非 。應記錄每個節點的生成器算法、種子或串流識別碼、重複索引範圍、樣本數及分派規則。重複的串流與索引範圍能暴露問題;單改最終歸約樹不能修復相依性。