用嵌套条件蒙特卡罗法快速比较停车时间

如果这两个条件中的任何一个都失败了，（3）只有在另一个条件充分满足时才能成立。如果N和R使得预算约束c（N，R）=c保持相等，那么（N，R）可以写成var(这里V（R）=（ρ+ρR）v+vR.因此，为了比较不同R值之间的差异，需要比较V（R）值。下一个命题量化了使用我们的算法和R*子样本而非simpleMonte Carlo估计：命题3.2。如果条件（3）成立，则使用带R的嵌套条件蒙特卡罗得到的相对增益（方差减少）*子样本而不是简单的蒙特卡罗由γ给出*=V（R）*)五（1）=qvv+qρ（1+vv）（1+ρρ）。此外，麦克斯ρρ+ρ，vv+v≤ γ*≤ 最多4个ρ+ρ，vv+v.γ的下界*表明方差参数Via和成本参数ρi独立地对我们希望达到的方差减少设置了一个界限：我们最多可以减少一个因子v/（v+v），无论ρ与ρ相比有多小。直觉上的原因是（N，R）永远无法打败理论CMC估计量同样地，无论CMC方差vis与v相比有多小，我们都无法通过将模拟集中在τ的区间上而获得更大的加速∧和τ∨而不是从0到τ的整个区间∨. 这个速度由ρ和ρ+ρ之间的比率表示。因为我们的上限是γ*是下限的四倍，我们看到下限永远不会太远。总之，如果（且仅当）v 范德ρ ρ.在实际实现中，我们将无法精确地使用R*子样本至少有两个原因：因为我们不知道参数SV、v、ρ和ρ，所以必须在飞行员模拟中进行估计。此外，R必须设置为整数值。

因此，重要的是要确保8 FABIAN DICKMANN和NIKOLAUS Schweizer算法的性能对R的选择不太敏感。下一个命题表明，情况确实如此，如果我们只能保证R位于R附近的一个区间，则给出方差减少损失的上界*.提议3.3。假设R*> 1和α-1R*≤ R≤ αR*对于某些α>1的情况。然后我们得到了方差缩减损失的下界：V（R）V（R）*)≤+α + α-1和thusV（R）V（1）≤+α + α-1.γ*.对于α的实际值，这个界限相当严格。对于α=1.2，意味着R的误判率约为20%，我们仍然在最优方差减少的1%以内。对于α=2，几乎实现了90%的最佳方差缩减。因此，我们得出结论，即使是粗略地尝试优化子样本的数量R，也会得到接近最优的结果。命题3.3证明中的一个关键观察是恒等式V（αR）*) =V（α）-1R*). 下一个推论收集了一些关于选择R:If R的实际含义*显著大于1，则R的值存在一个较简单的蒙特卡罗法有所改进的宽区间：任何小于最佳R的平方的R值*比R=1好。此外，考虑到固定的计算预算，高估R总是更好的*以固定的数量，而不是以同样的数量低估它。最后，取整R*对于最接近的整数，无法生成比简单的蒙特卡罗算法更差的算法。推论3.4。假设条件（3）成立，即R*> 1.那么下面的断言是正确的：（i）对于每个R，1<R<R*我们比simpleMonte Carlo有一个改进，V（R）<V（1）。（ii）设r>0，使得r*- R≥ 1.然后V（R）*+ r） <V（r*- r） 。（iii）设R#为最接近R的整数*. 如果R#>1，那么V（R#）<V（1）。

百慕大期权定价的应用在本节中，我们将在许多应用程序中说明我们的算法，这些应用程序与百慕大期权定价的著名基准示例[1,7]有关，百慕大期权定价是在Black Scholes模型中对百慕大最大看涨期权的估值。在连续的时间范围内[0，T]存在价格过程为d的股票。在风险中性定价测度下，股票是独立的、同分布的几何布朗运动，波动率σ和漂移r- δ. 这里，r是无风险利率，δ是股息收益率。假设有一组有限的、有序的锻炼日期t，t，tJin[0，T]和writeXj=e-r tjmaxdYdtj- K+.因此，Xjis是在tj时行使百慕大max calloption和strike K的折扣支付。该期权在时间0的公平价格由E[Xτ给出*] 其中最佳停止时间τ*解算τE[Xτ]。通过嵌套CMC 9比较停止时间此处，上确界覆盖所有停止时间，其值在{0，…，J}中。除非维数d很小，否则这个停止问题在数值上是复杂的。确定公平价格置信区间的一种流行方法是[1]中提出的原始-对偶方法。首先，计算τ的近似值τ*估计E[Xτ]，它给出了τ的次优性的下界。然后，τ也可以用来构造高偏估计量，这依赖于[15,18]的对偶方法。我们在这里重点讨论近似τ和评估低偏差估计的第一步。请注意，如果我们对τ的构造和E[Xτ]的计算都使用蒙特卡罗方法，我们需要在两个计算中使用独立的随机性来保持低偏差特性，请参见[12]中的讨论。

自始至终，我们将计算τ时使用的Y路径称为训练路径，并将估计E[Xτ]和相关量时使用的Y路径称为测试路径。在我们的数值实现中，我们主要关注两种计算近似最优停止时间τ的成熟方法，即Tsitsiklis和Van Roy[19]的最小二乘蒙特卡罗算法和Broadie和Glasserman[7]的themesh方法。在Sitsiklis-Van Roy方法的实现中，我们使用时间j的基函数，即股票Ydtjan中的二阶单项式和立即执行Xj的支付。对于网格方法，我们遵循[4]中的实现，包括控制变量的使用，这里省略了细节。在我们讨论应用程序之前，让我们简要地讨论一下这两种方法：可以说，最小二乘蒙特卡罗方法的最大优点是，即使是像上面这样的通用实现，通常也能在非常低的计算成本下实现接近真值的几个百分比。然而，对于每个固定的基函数选择，方法的偏差只能通过增加训练路径的数量降低到某个固定水平。如果不大幅调整算法（基函数的选择）和/或大幅增加计算效率，通常没有可行的通用方法来控制精度。在这里，我们坚持算法的快速“普通”实现，在我们看来，它具有最小二乘蒙特卡罗的所有优点。特别是，该实现非常适合作为第4.2节中易于评估的准控制变量。相比之下，对于网格方法，通过增加训练路径的数量，可以将偏差控制到任意精度。不需要“聪明的想法”，例如基函数的选择。

为这一值得考虑的优势付出的代价是，评估停止时间非常昂贵：当使用网格方法时，计算τ在模拟路径上的实现会占用大部分计算量，因为每个路径必须在每个时间点与所有训练路径进行比较。事实上，第4.2节和第4.3节的例子都可以解释为尝试。出于数值性能的原因，我们不使用欧洲价格作为基本函数，因为在高维中评估这些价格非常昂贵。出于同样的原因，我们使用Tsitiklis-Van Roy方法，而不是稍微流行一点的Longsta ff-Schwartz算法[17]。当使用两组路径（训练和测试）时，这两种方法通常会导致几乎无法区分的结果，参见[3]。10 FABIAN DICKMANN和NIKOLAUS SCHWEIZER^σ- σ 0.005 0.01 0.015 0.02（σ）0.0110.026 0.043 0.066E[Xτσ]8.042 8.042 8.042 8.042E[Xτσ]8.031 8.016 7.999 7.976P（τσ6=τσ）0.022 0.043 0.062 0.081ρ7.975 7.974 7.972ρ0.053 0.104 0.154 0.199v0。008 0.020 0.037 0.061v4。023 8.016 12.053 16.066R*271.8 176.0 129.4 103.3γ*0.016 0.026 0.037 0.047加速62.5 38.5 27.0 21.3表1。^σ不同值的估计模拟参数。加速1/γ*最后一行给出了使用嵌套CMC的步骤。通过开发通用有效的控制变量来提高网格方法的适用性。4.1. 评估参数不确定性。在我们的第一个数值例子中，比较两个停车时间是一种真正的兴趣。我们研究了Tsitsiklis-Van Roy方法估计的停止时间对参数误判（即误判波动率）的敏感性估计问题。用τσ表示从具有正确波动率σ的训练路径计算的停止时间，而τσ是从具有波动率σ6=σ的训练路径计算的。

我们希望根据这种错误的计算来估算行使期权的成本，即：。，（σ）=E[Xτσ- Xτ^σ]其中，预期当然是针对波动率σ的正确模型。按照[1,7]中的例子，我们假设10个练习日期t。。。，t=t，在时间范围[0，t]上均匀分布，并使用以下参数集：d=2，t=3，r=0.05，δ=0.1，σ=0.2k=100，Yd=90。我们使用10万条基本布朗运动的训练路径来计算停止时间，并始终保持这些时间不变。表1报告了参数ρi和Vi的估计值，这些参数分别代表了错误定义的波动率^σ的不同值。从表中观察到的第一件事是，在所有四种情况下，嵌套CMC都会导致显著的方差减少，在大约60到大约20之间变化，如果σ和^σ最相似，则收益最大。vand-vis之间的比率相当恒定，并且（远）小于ρ和ρ之间的比率，因此，这对于通过嵌套CMC 11减少实现的停止时间差异比较具有决定性意义。我们还报告了两次停车时间不同的概率——因此实际上必须进行补贴——并发现其介于2%和8%之间。这些数字是ρ值较小和子样本数较高（103到272之间）的一个关键原因。我们报告ρ的单位是不相关的（只有比率是重要的），并且是故意选择的（但在整个表格中是固定的）。更重要的是，应该强调的是，这些数字的精确值在该方法的不同数值实现中不可避免地存在差异。在上表中，我们试图尽可能准确地估计这些参数。然而，正如第3节所示，这是没有必要的——粗略估计在实践中是有效的。4.2. 改进的准控制变量。

在本节和下一节中，我们将转向更经典的问题，即计算给定停止时间τA的E[XτA]。引入第二个停止时间τ带写入[XτA]=E[XτB]+E[XτA- XτB]。在经典的控制变量方法中，人们会选择τb，这样就可以明确计算右侧的第一个预期值，然后通过蒙特卡罗只估计第二个预期值。一个流行的例子是选择τB=J，它对应于使用欧式期权作为控制变量。在更抽象的背景下，Emsermann和Simon[9]指出，有时使用所谓的准控制变量是有益的，即预期值未知的控制变量。如果XτBis的模拟成本明显低于乙烷XτA，则会出现这种情况。在这种情况下，可以通过对XτB的多次（廉价）模拟来估计第一次求和。对于第二次求和，由于XτB的方差减小效应，可能只需要少量（昂贵）路径。最后，请注意，第二个期望值正是嵌套CMC可以有效估计的术语类型。因此，我们希望通过我们的方法显著增强准控制变量。我们保留上一节的数值示例，除了将尺寸增加到d=3。我们选择τAas，这是一个近似的最佳停止时间，由网格法计算，控制变量来自[4]，有2500条训练路径。随着时间的推移，我们选择了一个有10万条训练路径的齐齐克利斯·范罗伊停站时间。在表2中，我们陈述了生成XτA样本的预期值uA=E[XτA]，方差vA=Var（XτA）和成本ρafo的估计值，以及τB的相应数量。如预期，vA和Vb相似，但ρAis比ρB大3000倍。

还要注意的是，ua远大于uB。这里有一点微妙之处，这取决于使用XJor E[XJ | Fτa]作为控制变量、欧洲支付还是欧洲价格。第二，最优选择可以理解为R=∞. 然而，这通常会产生比我们考虑的控制变量更大的vt值，因为τB=Jis不一定是τ的良好近似值*. 此外，欧洲价格并非总是以封闭的形式存在。我们不知道拟控制变量在百慕大/美国期权定价中的应用。正如本例所示，对于这个重要的问题，它们是相当通用且强大的方差缩减技术。12 FABIAN DICKMANN和NIKOLAUS SCHWEIZERuAvAρAuBvBρBvρvρ11.276 182 37.92 11.224 206 0.0124 0.044 36.23 19.536 1.728表2。估计的模拟参数。由于两种估计都有向下的偏差，这反映了网格方法的更高精度。特别是，对于E[Xτ，u在95%置信区间[11.265,11.308]内*] 从[1]开始。用ρ（R）和v（R）表示估计E[XτA时的计算成本和方差检验路径- XτB]由嵌套的CMC和R个复制，即ρ（R）=ρ+Rρ和v（R）=v+vr，其中ρi和v的定义与第2节完全相同。设nb为用于估计u波段的路径数，如前所述，设N为用于估计uA的路径数- uB.对于给定的计算预算Tc和固定的R，Nb和N的最佳选择是MinNb，NvBNB+v（R）Ns的解。t、 ρBNB+ρ（R）N≤ C.通过类似于[9]中的计算（或我们命题3.1的证明），可以得出N和nb之间的最佳比率由（4）NBN=svBv（R）ρ（R）ρB给出，而不管计算预算的大小。

最后，观察最佳值R*R的值与第3节中的值相同，无论u带uA的估计值之间的计算效果如何- uB.根据通孔和ρi的值，我们注意到R*= 97.037和估算的γ*在uA的模拟中- μBis由γ给出*= 0.067，对应于这部分估算中几乎经常出现的加速。表3比较了三种蒙特卡罗估值器对uA的性能，这三种估值器具有（大约）相同的计算成本，并且参数受上述考虑因素的指导。第一行给出了3150个样本路径下ua的直接蒙特卡罗估计值的方差。第二行显示了一个简单的准控制变量估计器（R=1）的方差，其中在u波段的估计中NB=536178条路径，在ua的估计中N=2989条路径- uB.第三行显示了一个准控制变量估计器的方差，在uA的估计中，每个路径的R=100个重复，然后=468个路径- uBand NB=1，784，813个路径，用于估算uB。因此，我们看到了超过100个因子的改进，这在准控制变量和嵌套模拟中是相等的。在本例中，vand-vis之间的比率比ρ和ρ之间的比率更有利，这意味着后一个比率控制着我们实现的方差减少。这是因为ρ的值相对较高，这是因为在大约60%的情况下，通过嵌套CMC 13方法方差运行时间简单蒙特卡罗60.4×10比较停车时间是便宜的Tsitsiklis Van Roy-3125sQuasi控制变量6.77×10-3121sQuasi控制变量，嵌套CMC 0.514×10-3105稳定的3。比较三种运行时间相似的方法。

此表报告了在带有2.6 GHz AMD处理器的标准系统上，用C++实现的平均超过100次模拟。首先停止的停止时间。通过修改Tsitiklis-Van Roy停止时间，使其略微偏向延迟停止，从而增加方差Vbut，降低ρ，可以构造一个更有效的UASI控制变量。这可以通过向估计的连续值添加一个小常数来实现。4.3. 一种改进的多级算法。由Heinrich[16]和Giles[11]提出的多级蒙特卡罗方法可以很容易地理解为准控制变量方法的扩展：不是单一的准控制变量，而是一个随机变量序列，序列中的每个元素都作为其后续变量的准控制变量。在最近的一篇论文中，Belomestny、Dickmann和Nagapetyan[4]介绍并分析了数值计算E[Xτ近似值的多级方法*].[4]的算法可以总结如下：固定一个级别L和一个递增序列k，考虑稳定时间序列（τ（ki））i，它是τ的近似值*通过使用Kittraining路径的Mesh方法计算。在这些停车时间中，τ（kL）是最精确和最昂贵的。因此，为了估计[Xτ（kL）]，我们写（5）E[Xτ（kL）]=E[Xτ（k）]+LXi=1E[Xτ（ki）- Xτ（ki）-1） 在[4]的多级方法中，右手边的每个求和都是通过蒙特卡罗独立估计的，具有N个测试路径，其中序列N。NL正在下降。该算法的动机如下：τ（k）的计算成本很低，因此可以通过许多测试路径来估计E[Xτ（k）]。（5）中的summand随着i的增加而变得更加昂贵。