動機
一個數值積分或期望可能難以精確計算,但容易產生單個隨機樣本。Monte Carlo 估計用模擬值的平均數代替期望。這個平均數本身是隨機的:再次運行相同算法,通常會得到不同結果。因此分析應說明估計的目標是甚麼,以及指定大小的誤差有多大概率發生。
幾種保證需要區分。無偏性討論假想的重複運行中估計量的均值;大數定律討論樣本量增長時的極限;有限樣本界控制指定樣本量下的誤差概率。在任意抽樣條件下,它們不能自動相互推出。特別地,平均帶來的方差下降取決於模擬結果的依賴結構,而不只是程式輸出了多少個數值。
從均勻隨機數構造目標分布
估計量需要來自所選分布的樣本,單有期望的公式還不夠。一個基本構造從 上理想的均勻隨機變量 出發。設 為累積分布函數:它不遞減、右連續,在負無窮與正無窮處的極限分別為零和一。對 定義其廣義逆
這個集合非空且有下界,所以 有限。在該集合中選取遞減趨於下確界的點列,由右連續性得 。於是對每個實數 ,
正向由 的單調性得出;反向則因為此時 屬於定義下確界的集合。因此
所以 服從目標分布,即使 有跳躍或平坦區間也成立。證明不要求密度或嚴格遞增。若把同一個確定性函數 分別作用於獨立的均勻變量 ,所得變量仍然獨立同分布;這就連接到下文的獨立樣本公式。
例題 9.1.1
(指數分布與離散分布的抽樣)
當 時,指數分布在 有 ,在 有 。解方程 得 。例如 給出 。
另一個離散變量取值 ,概率分別為 ,累積概率為 。當 返回 ,當 返回 ,當 返回 。各區間的長度恰是所需概率。階梯函數沒有普通的一一反函數;廣義逆使這個構造仍然有效。
證明使用理想連續均勻變量和精確運算。電腦提供的是有限集合上的偽隨機值,並非真正獨立的連續變量;端點約定也很重要。指數公式中 會要求計算 ,而有限網格不能精確表示無界尾部。固定偽隨機種子可以重現一次運行,但本身不能證明獨立性或給出 Monte Carlo 誤差界。應查閱實際生成器的取值範圍,並判斷它是否適合計算。
快速檢查
(目標變量以概率 取 、以概率 取 。給出由均勻變量 得到它的變換,並求目標變量的期望。)
把 的區間與累積概率對照。
解答 · 答案
當 返回 ,否則返回 。期望為 。這是理想構造的分布結論,並非對單次有限網格實現的保證。
快速檢查
(若指數分布的速率為 ,變換 在 處返回甚麼?)
取 代入 。
解答 · 答案
,這正是該分布的中位數。
定義
定義 9.1.2
(Monte Carlo 估計量與方差)
令 為獨立同分布實隨機變量,具有有限均值 。對整數 ,Monte Carlo 估計量為
若 ,記 。由獨立性,
最後一個量是均方根誤差,並非單次運行的確定性誤差界。兩兩協方差為零也足以得到這裏的方差公式,但下文強大數定律和 Hoeffding 界的證明使用獨立性。
概率密度 下的期望就是積分:若 ,可獨立抽取 並取 。在隨機漫步計算中,一個 也可以是整條模擬路徑的函數;此時上式要求的是不同路徑之間獨立,而不是同一路徑中相鄰位置獨立。
定義 9.1.3
(依概率收斂與幾乎必然收斂)
如果對每個 都有 ,稱 依概率收斂到 。如果使 成立的結果集合具有概率一,稱其幾乎必然收斂。幾乎必然收斂是在一次結果上討論整條無窮序列,並不表示每個有限樣本估計都落在指定容差內。
大數定律與誤差界
定理 9.1.4
(有限方差的大數定律)
若 獨立同分布,均值為 且方差 有限,則 既依概率成立,也幾乎必然成立。對每個 ,Chebyshev 不等式給出有限樣本界
對獨立同分布變量,更一般的強大數定律在一階絕對矩有限但方差無窮時也成立;下面的證明使用更嚴格的有限方差條件。
定理 9.1.5
(有界獨立輸出的 Hoeffding 界)
假設 獨立,幾乎必然都落在同一區間 中,其中 ,且均值均為 ;在這一均值條件下不需要同分布。那麼對每個 ,
特別地,對 ,只要 ,上界便至多為 。
樣本量公式給出充分保證,並非精確失敗概率。Chebyshev 使用方差界,Hoeffding 使用已知的幾乎必然取值範圍。一次運行中觀察到的範圍較小,本身不能證明輸出分布受到該範圍限制。
收斂與集中結論為何成立
證明
(均值、方差與弱大數定律)
期望的線性性給出無偏性。由獨立性,求和方差中的所有非對角協方差為零,所以 。估計量無偏,因此這個方差也等於均方誤差。對 應用 Markov 不等式得到 Chebyshev 界;固定 時右邊趨於零,證明依概率收斂。
這裏使用的是真實方差。如果 未知,以隨機樣本方差代替需要另外的統計論證;所寫的界不會自動變成置信保證。
證明
(有限方差下的幾乎必然收斂證明)
令 、。 相互獨立、均值為零、方差為 。先證明最大值不等式
對每個 ,令 為首次滿足 的下標是 的事件。 互不相交,並由 確定。由獨立性及零均值,交叉項在期望中為零,而不是逐點為零:。剩餘增量平方非負。因此
對 求和,並利用 ,得到最大值不等式。
對整數 ,取 、。存在某個 使 的概率至多為 ,這些上界對 可求和。由第一 Borel–Cantelli 引理,幾乎必然只有有限多個事件發生。因此充分大時,對每個 均有 。對 將這些概率一的事件取交集,得到 幾乎必然成立。
證明透視
為何要對整塊指標而非單個指標作估計
有限方差透過 進入證明,這是唯一量度波動大小的地方。獨立性只用了一次: 只依賴 ,而 只依賴其後各項,所以兩者乘積的期望可以分解,均值為零的增量使它消失。
不顯而易見的一步是選擇估計甚麼。對每個單獨指標用 Chebyshev 只得 ,而調和級數發散,Borel–Cantelli 引理便無從使用。最大值不等式只付出一個因子 ,就同時控制所有 ;再把指標分成 的塊,界 便成為等比數列。塊內 ,故 推出 ,代價只是一個因子二。
論證分兩階段收尾:Borel–Cantelli 引理把可求和的失敗概率序列轉化為單一結果上「最終不再失敗」,再對 取可數交集,便去掉對容忍度的依賴。若沒有獨立性,交叉項未必消失;本頁稍後完全相依的例子中,平均值永不穩定。
證明
(有界輸出為何給出指數尾界)
先用一個有界變量估計:若 幾乎必然成立,則對任意實數 ,
為說明這一點,令 。有界性保證可以在期望號下求導。對分布進行指數傾斜後,其支撐仍在 ;對對數求導可知 是傾斜後分布的方差。支撐於 的變量方差至多為 :將其到自身均值的平方距離與到區間中點的平方距離比較即可。由於 ,而中心化給出 ,將二階導數界積分兩次,得到 。
對於上尾,由 Markov 不等式和獨立性,對 有
取 得到 。對 重複論證,並對兩個尾事件使用並集界,便得係數二。獨立性用於將和的指數矩分解為各項乘積。
證明透視
指數矩令獨立性變成乘積
真正的想法是對 而不是對和本身使用 Markov 不等式,這樣獨立性就把矩分解成 個單變量因子的乘積。有界性只透過單變量估計 進入,獨立性只用在分解這一步。參數 之後可以自由選取:指數 在 時最小,得到 。因子二來自兩個尾部的聯合界。沒有獨立性,乘積這一步就不成立,下面完全相依的例子就是這樣。
重要性抽樣
定義 9.1.6
(改變抽樣密度)
設 是相對於同一個參考測度 的概率密度,記 ,「幾乎處處」也相對於 。設 是實值可測函數且 。假設在 的集合上, 幾乎處處成立。獨立抽取 ,定義
在 的 零測集上可任意定義比值。支撐條件保證
如果另外有 ,則其方差為
上面的支撐條件針對這一個被積函數。若希望用同一提議分布處理 下任意被積函數,則應要求 在 上幾乎處處成立。若提議分布遺漏 有非零貢獻的區域,給所觀察樣本乘權重也無法恢復遺漏部分。即使支撐足夠,過小的 仍可能導致巨大權重和無窮方差。
衡量方差能降到多小,有一個有用的理論基準。令 ,假設 。對任意滿足支撐條件且權重二階矩有限的提議密度 ,Cauchy–Schwarz 不等式給出
因為 。取 可達到等號;它是密度,並具有此被積函數所需的支撐。權重方差可達到的最小值是 。若 在 下幾乎處處非負,,最優權重恆為 ;變號的被積函數則不一定能達到零方差。這是理論基準:精確使用 需要其歸一化常數 ,而它可能未知。
例如,令 為 上的均勻密度,。此時 、、。權重在左半為 、右半為 ;在提議分布下兩半概率均為 。其方差為 ,小於均勻抽樣的 ,但並非零。
概念視角分析
把權重的方差看作卡方距離
取 ,則 ,。若在 的地方 ,則 。這是 相對於 的卡方散度:它當且僅當 幾乎處處成立時為零,當且僅當 發散時為無窮大。在下面方差無窮的例子中,。
例題
例題 9.1.7
(估計圓盤面積)
獨立地從 均勻抽取 ,令 。正方形面積為四,圓盤面積為 ,所以 。估計量是落入圓盤的比例乘四。這裏 ,且
若要求絕對誤差 、失敗概率至多 ,Hoeffding 給出充分條件
所以 足夠。這是獨立均勻抽樣條件下的事前保證,不是此程式返回某個具體小數的實際概率。
例題 9.1.8
(方差為零的重要性提議分布)
估計 時,取目標密度 、提議密度 ,。雖然單點 ,支撐條件仍幾乎處處成立。對提議分布的一個樣本,
因此任何正樣本量的估計都恰為 ,方差為零。相比之下,均勻抽樣時 的方差為 。這是一個理想的教學例子,不是一般性的現成方法:將與未知非負被積函數成比例的密度歸一化,可能需要先知道正要估計的積分。
例題 9.1.9
(支撐正確但方差無窮)
現在以同樣的 、 估計 。對 ,權重為 。其期望為一,但
因此估計量仍然無偏,但每個有限 的方差均無窮:權重非負,所以 。有限方差 Chebyshev 公式和有界輸出 Hoeffding 公式都不適用。一般的一階絕對矩強大數定律仍可能給出幾乎必然收斂,但這一事實不提供有限方差誤差證書。
反例模式
許多相依輸出可能只有一份資訊
令 為公平 Bernoulli 隨機變量,並對所有 設 。每個 的均值為 、方差為 ,但輸出完全相依。無論 多大,平均值始終為 ,其方差保持 ,也不依概率收斂到 。若把這 個值誤當成獨立變量,就會錯誤地預測方差為 。
常見錯誤
常見錯誤
(把無偏性當成單次估計可靠)
無偏估計在某一次運行中可能離目標很遠,甚至可能有無窮方差。有限樣本保證需要足夠強的尾部控制假設,並須給出容差及失敗概率。幾乎必然收斂是漸近結論,不是某個有限 的誤差證書。
常見錯誤
(忽略提議密度為零的位置)
如果 的集合上 有非零貢獻,估計器永遠不會從那裏取樣。例如估計 時取 ,但取 ,則每個被抽到的點都有 ,期望輸出為 而非一。問題是缺失支撐,而不是大樣本波動。
總結
方差有限時,獨立模擬的平均值無偏且方差為 。Chebyshev、Hoeffding 和強大數定律在不同條件下給出不同類型的結論。重要性抽樣改變觀測分布;使用基於方差的保證前,必須檢查支撐以及權重的二階矩是否有限。
練習
練習 9.1.10
(獨立輸出的均值為 、方差為 。當 時,求平均值的方差和均方根誤差,並給出誤差至少為 的 Chebyshev 上界。)
基礎
解答(3)
- 1
平均值的方差
- 2
均方根誤差
依據: 估計量無偏,所以其均方誤差就是方差。
- 3
應用 Chebyshev 不等式
這只是上界,不是所有具有所述均值和方差的分布的精確概率。
練習 9.1.11
(對 中的獨立輸出,求一個整數 ,使 時 Hoeffding 雙側界至多為 。)
基礎
解答(3)
- 1
寫出條件
依據: 此處 。
- 2
解出
- 3
向上取整
足夠。
練習 9.1.12
(取 、,,估計 。求重要性權重、其均值和方差。)
核心
解答(3)
- 1
計算權重
關鍵一步
對 ,幾乎必然有
- 2
計算均值
- 3
計算二階矩與方差
若獨立抽取 個提議樣本,其平均值方差為 。
練習 9.1.13
(對所有 令 ,其中 為公平 Bernoulli 隨機變量。計算 ,並解釋為何不能使用獨立樣本的 Hoeffding 界。)
核心
解答(3)
- 1
確定平均值
每個 都等於 ,所以對每個 都有 。
- 2
計算概率
由於 ,恆有 ,所以所求概率對每個 都是 。
- 3
找出不成立的假設
輸出完全相依,這個分解不成立。界 在 較大時小於 ,與精確值 矛盾。
依據: Hoeffding 的證明把和的指數矩分解為各樣本的乘積。