Q quant秘技——MC方差縮減（對偶變數篇）

02-04

大家好，我是黑貓Q形態。感謝@Yupeng博士給了我一個溫暖的喵窩寫文章。

接下來的一段時間裡我將普及我們Q派礦門裡的一件殺器：MC方差縮減技術，來做為一個專題。這個專題會設計一些蒙特卡洛方法里的抽樣技巧，採取這些技巧會使我們用同樣多的樣本可以獲得更精確的計算結果（或者同樣精確的結果用更少的樣本），從根源上發提高運算速度，進而秒殺全場，毀滅世界。（大誤）。

專題暫定先介紹四種方差縮減技術：對偶變數（Antithetic Variates），控制變數（Control Variates），分層抽樣（Stratified Sampling），重要性抽樣（Importance Sampling）。如果寫完大家反應好，那麼講繼續介紹更多的技術。（ PS：四種夠大家回答Quant 通常需要什麼樣的教育背景和知識結構？ - 袁浩瀚的回答里數學部分的第三題了，在此向袁老師致敬@袁浩瀚）

今天要向大家普及的是對偶變數（Antithetic Variates），我們先從簡單的歐式期權MC實驗例子說起：

我們都知道，期權的價值無非是到期日payoff條件期望的貼現，如果把賣期權得到的錢全部投入到最安全的貨幣市場（就是確定無風險測度的通俗說法）那我們的期權價格無非就是：

$tilde{E}^Q_{t_0} [S_0expleft{ (r-frac{1}{2}sigma^2)T+sigma W_T right}-K ]$

我們都知道這個東西的解是著名的BS公式，但是如果變成別的不會解的東西了怎麼辦？

聰明的工程師們想到了MC這個方法，大體思路就是：

1.我們知道了價格式子里隨機部分的分布（基本例子里，W_T的分布就是N[0,T*sigma^2])；

2.既然期望是對無窮個概率對應的變數求期望，那麼我們生成足夠多個隨機種子，其他都是確定之。這樣只要我的隨機種子很多，再去求所有這些模擬樣本的期望，肯定能逼近答案；

聽起來是很美好，但是根據中心極限定理，我們知道了這種逼近法誤差的級別：

$lim_{n rightarrow infty }{P(frac{tilde{c}-c }{s_c/sqrt{n} }<x )} =N(0,1)$

什麼意思呢，看見那個根號n了么，那時我們的模擬數。上面是式子意味著，我的模擬次數要多100倍，標準誤(s)才能減小10倍。雖然計算機計算的很快，但是這個計算數量增長的也太快了（平方級）。

由此可見，我們需要一種減小方差的技術，使得同樣的計算數量能獲得更小的誤差從而提高運算效率，這就是我們的方差縮減技術。

1.對偶原理：

今天我們主講的對偶變數，聰明且學過概率論的同學可能一致通過標題那兩隻喵猜到我要幹什麼了——利用一些對稱分布（比如正態分布）的對稱性：

因為大家知道，正態分布的概率密度函數（pdf）是偶函數，所以其對應的累積分布函數（cdf）必然有如下關係：

$Phi (-z)=U_{-z} =1- Phi(z) = 1-U_z$

而cdf是單調的，意味著我們的真正隨機種子，也就是cdf的反函數也是單調的。 所以對於正太分布，我們生成了一個z，就可以馬上知道-z服從正態分布，可以作為另一個隨機種子：

這意味著，本來需要生成10000個隨機數的任務，一下縮到了5000；

那麼，偷了懶之後，誤差會怎麼變化呢？

$frac{tilde{c_{av}}-c }{s_{av}/sqrt{2tilde{n} } } Rightarrow N(0,1)$

實際上根據中性極限定理，我們「複製」一遍對偶變數之後，會發現誤差和原來是一樣。

那麼這種辦法到底為什麼快呢？之所快是因為，我們在實際計算的時候，通過用對偶變數的解析值（-z），而省去了調用隨機生成函數的時間從而減小了調用次數和矩陣所佔內存，因而節省了時間（計算機處理正態隨機使用的是Box-Muller演算法之後求反函數，顯然直接一個負號運算量更小）

2.數學解釋

那麼為什麼我們可以只用一半的樣本就達到和原來一樣的精確度了呢？或者說我的方差為什麼被縮減了？

這是由於對偶變數的負相關性導致的,我們知道我們把變數分成了兩組，原組合對偶組，他們的總方差是：

$Var(Z,-Z) = 2Var(Z) + 2Cov(Z,-Z)$

但是我們知道因為Z和-Z是完全對稱的，所以我們可以得到一個顯然的負相關性：

$Cov(Z,-Z)<0$

這將導致的結果就是：

$Var[frac{1}{n} sum_{i=1}^{n}{Z_i} +frac{1}{n} sum_{i=1}^{n}{-Z_i}] <Var[frac{1}{2n} sum_{i=1}^{2n}{Z_i} ]$

根據@春風暖花的提示：

「f(Z)需要是單調函數。在 2.數學解釋中，應該從f 的方差減小出發。cov(z,-z)<0必然成立，但是，是由於f的單調性導致 ncov(f(z),f(-z))<0才使得最後的方差縮小了，只有cov(z,-z)<0,不一定能達到最後方差減小的效果。"

3.作死實驗

為了驗證對偶節省的時間，我們用上面給的BSclosed例子瞎寫一段代碼驗證一下：

from numpy import random,exp,average,hstack

s0=50

K=49

r=0.05

sigma=0.1

t=10

start

import datetime

start =datetime.datetime.now()

mc=100000

rand1=random.normal(0,1,mc)

s_matrix =s0*exp((r-0.5*sigma**2)*t +sigma*t**0.5* rand1)

option =exp(-r*t)*average(s_matrix -K)

end=datetime.datetime.now()

print(end-start)

# testing time

start =datetime.datetime.now()

rand2 =random.normal(0,1,mc/2)

s_matrix1 =s0*exp((r-0.5*sigma**2)*t +sigma*t**0.5* rand2)-K

s_matrix2 =s0*exp((r-0.5*sigma**2)*t +sigma*t**0.5* -rand2)-K

option2 =exp(-r*t)*average((s_matrix1,s_matrix2)

end=datetime.datetime.now()

print(end-start)

先對比10萬次的時間發現並沒有節省多少：

0:00:00.005015 vs 0:00:00.004009

百萬次減少的就有些多了：

0:00:00.057151 vs 0:00:00.042145

千萬次減少的時間就有點明顯了：

0:00:00.538464 vs 0:00:00.408520

但是感覺減少的不多，是因為兩次消耗的內存並不是很多，同時先跑第一個後對第二個內存有影響

為了體現對偶的強大，我作了個死——分批跑一億次

mc=100000000

0:00:05.734788 vs 0:00:00.443149

因為「長度為一億的向量」操作吃了我將近一個G的內存，這個級別的內存消耗增量嚴重降低速度(內存消耗太多，時間非線性增加）。所以第二次的少了五千萬次效果拔群，而因為剛才的誤差分析證明了他們的值相差無幾（同時模擬次數高導致了本來誤差就小）！

20.2810599302 vs 20.2799766337

當計算量相當高的時候，對偶變數法展現了他強大的提速能力

今天的對偶篇就講到這裡，下一期內容暫定為：

Q quant秘技——MC方差縮減（控制變數篇）歡迎小夥伴們吐槽~