期望退出时间和其他函数的多级估计

HenceEx，t[（p（3））]≤ Ex，tXn公司≥0nh序号= E[S′]Ex，t[bτ- t] 。这就完成了证明。4 MLMC算法多层蒙特卡罗（MLMC）方法有很好的文档记录[7，8]。以下是[8]中给出的MLMC定理的版本：定理4.1。设P表示随机变量，letbPl表示相应级别l 数值近似。如果存在独立估计量Yl每一个都是N的平均值li、 i.d.蒙特卡罗样本，每个样本的预期成本为Cl和方差Vl, 和正常数sα，β，γ，c，c，c≥最小值（β，γ）andi）E[bPl-P]≤ c-α lii）E【Y】l] =（E【bP】，l = 0E[bPl-英国石油公司l-1], l > 0iii）Vl≤ c-β liv）Cl≤ cγl,然后存在一个正常数csuch，对于任何ε<e-1此处是值SL和Nl其中多级估计=LXl=0年l,具有边界均方误差≡ Eh（Y- E[P]）i<ε，预期计算复杂度C，边界C≤cε-2，β>γ，cε-2（对数ε），β=γ，cε-2.-(γ-β)/α, β < γ.在本文的设置中，P=ZτE（0，s）f（Xs，s）ds+E（0，τ）g（Xτ，τ），（4），每条路径从X=X开始，bpl表示级别上相应的数值近似值l 使用大小为h的unifor m时间步l定义人hl= K-lh、 对于某些固定的h>0和整数K>1。根据[7]中的观察结果，我们将在算法描述和后面给出的数值实验中使用K=4，但数值分析将考虑其他值的可能性。现在的问题是如何定义l? Higham等人【13】将其定义为水平数值近似差异的平均值l 和l-1 fromNl独立路径模拟，Yl= N-1.lNlXn=1英国石油公司l（W（n））-英国石油公司l-1（W（n））.0 0.5 1 1.5 2t-1coarse-pathsfine-pathboundary图1：精细和粗糙1D布朗路径的图解，当它们在x=0处穿过边界时终止。

注：实际算法和分析基于分段常数近似，但为了视觉清晰度，此处使用了连续分段线性插值。这里是符号BPl（W（n））-英国石油公司l-1（W（n））表示两个数值近似值的差异，时间步长不同，但驱动布朗运动相同。使用相同的布朗路径是多级处理的关键；正是这一点确保了变量Vl衰减为零l→∞.然而，方差并不像人们希望的那样迅速衰减到零。该问题如图1所示。带圆圈的线表示一条经过3个时间步后穿过边界的内布朗路径。另一条线显示，经过两个粗略的时间步（每个时间步对应两个精细的时间步）后，粗略路径没有穿过边界，但它非常接近边界。从该点继续模拟，多条线对应于布朗路径扩展的多个独立模拟。其中许多很快就跨越了边界，但有些直到很久以后才跨越边界。事实上，对于任何固定时间T，粗路径在跨越边界之前持续时间超过T的概率约为O（h1/2）。Higham等人[13]证明，作为一个序列，Vl= O（h1/2l|日志hl|1/2），这是一个n MLMC计算复杂度界，它是O（ε-3 | logε|）。Higham等人没有使用bo-undary校正，因此他们的近似值只有O（h1/2）弱收敛。

对于平滑边界D、 将其MLMC处理修改为使用Gobet和Menozzi的边界偏移[11]，将改善弱收敛到一阶，并将总体复杂性降低到O（ε-2.5 | logε|），通过将达到所需精度所需的液位数量减半。新的MLMC算法具有与使用标准边界处理或Gobet&Menozzi处理相同的复杂性。将对前者进行详细的数值分析，但对后者具有自然张力。两种方法的数值结果表明，后者为4- 在实践中效率提高10倍。5新的MLMC算法图1不仅说明了现有MLMC算法的问题，还说明了解决方案。新算法的关键思想是，当模拟一对由相同布朗运动驱动的粗路径和细路径时，一条路径退出域，另一条路径被分割（或复制）成多个副本，每个副本从该点开始由不同的独立布朗路径实现驱动。对这些不同副本的输出求平均值可以近似表示该路径的条件期望，而基于条件期望的多水平估计值的方差要低得多。这类似于[6，8]中对数字选项和障碍选项使用条件期望。通过引入分裂，很明显计算成本会增加。这对于确定拆分路径的数量很重要。忽略与对数h成比例的因子l, 将显示分割路径的起始距离为O（h1/2l) 因此，每条分割路径的预期退出时间为O（h1/2l), 根据假设1和3。

通过使分割路径的数量为O（h-1/2l), 分割路径的成本为O（h-1.l), 这与拆分前粗路径和细路径的成本顺序相同。因此，总成本增加了一些因素，但其顺序没有改变。在定理6.4证明之后，将在后面显示，此分裂路径数是将多级方差减少到与使用真实条件期望相同的阶数所需的最小值，这相当于使用有限数量的分裂路径。计算Y的算法l在算法1中给出。级别上的时间步l 被带到b e hl= 4.-lh、 对于每个Nl样本、细路径和粗路径使用相同的驱动布朗路径W（n）计算，直到第一个粗时间步结束，两条路径中的至少一条已经离开域D或r到达终点时间T。如果另一条路径尚未退出D或到达时间T，则将其拆分为Ml复制，并且each继续使用由Z（n，m）表示的独立布朗路径，直到它最终退出域或到达时间T。Y的最终值l收到了吗l= N-1.lNlXn=1Pl（W（n））-Pl-1（W（n））其中Pl（W（n））=M-1.lMlXm=1bPl（W（n），Z（n，m）），和pl-1（W（n））的定义类似。稍微滥用符号，每个数量bpl（W（n），Z（n，m））是第4节中定义的费曼-卡茨函数（4）的适当近似值，对于未分裂的路径，m上的平均值很小，因此不依赖于Z（n，m）。6数值分析6.1方差分析对于完整性，数值分析从这个一般结果开始，然后进行拆分。这种分裂的使用与计算Y的条件算法1有关l使用Nl粗/细路径对，分为Ml一次退出后的子路径n=1。

NlDo对于给定的W（n），computebX（n）landbX（n）l-1使用带布朗运动W（n）和时间步长h的Euler Maruyama离散化l, h类l-1相应地，直到第一个粗略时间步结束，两个时间步中至少有一个已退出域D或达到终端时间TifbX（n）l已退出D或已达到终端时间T，则P（n）l:=英国石油公司l（W（n））基于已计算的路径sep（n）l:= M-1.lMlXm=1bPl（W（n），Z（n，m））基于ml使用Z（n，m）end-ififbX（n）表示的布朗路径的独立路径连续l-1已退出D或已达到终端时间T，则P（n）l-1： =bPl-1（W（n））基于已计算的路径sep（n）l-1： =米-1.lMlXm=1bPl-1（W（n），Z（n，m））基于ml使用Z（n，m）end-ifend-forY表示的布朗路径的独立路径连续l:= N-1.lNlXn=1P（n）l- P（n）l-1.蒙特卡罗方法（见[1]第145–148页），但与罕见事件模拟中的分裂技术截然不同。引理6.1。如果W和Z（1），Z（M）是独立的随机变量，如Z（1），Z（M）与随机变量Z的分布相同，则f=M-1MXm=1f（W，Z（m））是E[f（W，Z）]的无偏估计量，其方差为v[f]=VhE[f（W，Z）| W]i+m-1EhV[f（W，Z）| W]i.证明。以W的值为条件，期望值off为E[f（W，Z）| W]，其方差为M-1V【f（W，Z）| W】，因此EHF | Wi=E[f（W，Z）| W]+ M-1V[f（W，Z）| W]。对W的分布取期望，然后给出[f]=EhE[f（W，Z）| W]i=E[f（W，Z）]，Ehfi=Eh（E[f（W，Z）| W]）i+M-1EhV[f（W，Z）| W]i，由此得出V[f]=Ehfi-E【f】= VhE[f（W，Z）| W]i+M-1EhV[f（W，Z）| W]i.使用M将此结果应用于第5节中的多级估计器l级别上的拆分路径l, 提供usVl= 五、Pl-Pl-1.= VhE[英国石油公司l-英国石油公司l-1 | W]i+M-1.l超高压[bPl-英国石油公司l-1 | W]i。

（5） 主要定理将限制V[E[bPl-英国石油公司l-1 | W]]和E[V[bPl-英国石油公司l-1 | W]]，然后我们将绑定Cl, 使用分裂时每个样本的预期cos t。为了做好准备，我们将τ定义为一对粗/细路径的起始时间，并将τ四舍五入到粗/细路径的末端（即h的倍数l-1） ，这是两条路径中的一条路径仍在域中时发生分裂的时间。注意，τ6=τ仅当在粗路径之前存在细路径时，部分通过粗时间步。以下引理限制了粗末细路径与时间τ之间的差异，以及时间τ处细路径与可能不同时间τ处粗末细路径之间的差异。引理6.2。鉴于上述定义，对于q≥1我们有[sup[0，τ]kbXl,t型-bX公司l-1，tkq]1/q=O（h1/2l-1 |对数hl-1 | 1/2）安第斯l,τ-bX公司l-1，τkq]1/q=O（h1/2l-1 |对数hl-1 | 1/2）证明。这些直接来自引理3.1和推论3.2。对于特定对（W，Z），我们定义bτl和bτl-1是最终和最终路径的退出时间。下一个引理限定了这两个退出时间之间的预期绝对差异。这不受路径分裂的影响，因此有必要考虑没有分裂时会发生什么。引理6.3。鉴于上述定义以及假设1和3，E[| bτl-bτl-1 |]=O（h1/2l-1 |对数hl-1|1/2).证据每个W导致三种可能性中的一种：obXl,τ/∈D和BXl-1,τ/∈DobXl,τ/∈D和BXl-1,τ∈DobXl-1,τ/∈D和BXl,τ∈在第一种情况下，| bτl-bτl-1| =τ - τ<hl-1、在第二种情况下，自BX起l-1,τ∈D但BXl,τ/∈D、 有一个点y∈ 在两者之间划清界线。

因此，注意到uexit（y，τ）=τ，我们有e[bτl-1.-τ| W]=日分l-1，出口（bXl-1,τ,τ) - uexit（bXl-1,τ,τ)+uexit（bXl-1,τ,τ) - uexit（y，τ）.第一项以假设3为界，第二项以假设1中的Lipschitz性质为界，给出[bτl-1.-τ| W]≤ cexith1/2l-1+词汇kbX公司l,τ-bX公司l-1，τk+hl-1..加上τ-bτl≤ h类l-1，这可以简化为whichE的常数c[bτl-1.-bτl|W]≤ c2012年上半年l-1+kbXl,τ-bX公司l-1，τk.第三种情况下也有类似的结果，因此whichE[bτ]有一个常数cl-bτl-1 | W]≤ c2012年上半年l-1+kbXl,τ-bX公司l-1，τk.结合这两个结果，对W取一个期望值，并使用resultin引理6.2给出期望的结果E[| bτl-bτl-1 |]=O（h1/2l-1 |对数hl-1|1/2).Bouchard、Geiss和Gobet[2]的一篇新论文分析了出口时间的预期误差，并证明了在一定条件下E[| bτ-τ|]=O（h1/2）。由此可知，我们得到了略强的结果E[| bτl-bτl-1 |]=O（h1/2l-1).我们现在准备证明这一节的主要定理。定理6.4。根据假设1和3，VhE【bPl-英国石油公司l-1 | W]i=O（hl-1 |对数hl-1 |），超高压[bPl-英国石油公司l-1 | W]i=O（h1/2l-1 |对数hl-1|1/2).证据

对于最终路径，bPl=Zbτl是l（0，s）f（bXl,s、 s）ds+bEl（0，bτl) g（bXl,bτl, bτl)= p（1）l（W）+p（2）l（W）p（3）l（W，Z），其中P（1）l（W）=ZτbEl（0，s）f（bXl,s、 s）ds，p（2）l（W）=bEl（0，τ）p（3）l（W，Z）=ZbτlτbEl（τ，s）f（bXl,s、 s）ds+bEl（τ，bτl) g（bXl,bτl, bτl),同样地，对于c oarse路径，bPl-1=Zbτl-1bEl-1（0，s）f（bXl-1，s，s）ds+bEl-1（0，bτl-1） g（bXl-1，bτl-1，bτl-1） =p（1）l-1（W）+p（2）l-1（W）p（3）l-1（W，Z），其中P（1）l-1（W）=ZτbEl-1（0，s）f（bXl-1，s，s）ds，p（2）l-1（W）=bEl-1（0，τ）p（3）l-1（W，Z）=Zbτl-1τbEl-1（τ，s）f（bXl-1，s，s）ds+bEl-1（τ，bτl-1） g（bXl-1，bτl-1，bτl-1).注意exp（v）-exp（w）=（v-w） exp（ξ），对于具有端点v、w和定义K的区间中的某些ξbXk公司∞= 支持∈[0，τ]kbXl,t型-bX公司l-1，tk，然后是s∈ [0，τ]我们有是l（0，s）-是l-1（0，s）≤ exp（T kV k∞) T级bXk公司∞.我们还有f（bXl,s、 s）- f（bXl-1、s、s）≤ Lfk公司bXk公司∞,因此存在一个常数c（1）（独立于W），使得p（1）l-p（1）l-1.≤ c（1）kbXk公司∞+ h类l-1exp（T kV k∞) kf k∞, （6） 右边的第二项是由于p（1）定义的积分上限可能存在差异l, p（1）l-类似地，存在一个常数c（2）（独立于W），使得p（2）l-p（2）l-1.≤ c（2）kbXk公司∞+ h类l-1exp（T kV k∞) 千伏k∞.

（7） 对Z取一个期望，我们得到了[p（3）l|W]=bul（bXl,τ、 τ），E[p（3）l-1 | W]=bul-1（bXl-1，τ，τ），因此，使用假设3 tog乙醚和假设1的Lipschitz性质，我们得到E[p（3）l-p（3）l-1 | W]≤ 铜（h1/2l+ 2012年上半年l-1） +LukbX公司l,τ-bX公司l-1，τk+hl-1.（8） 结合方程式（6）-（8）中的结果，存在常数c、c、c，与W无关，因此E[bPl-英国石油公司l-1 | W]≤ ck公司bXk公司∞+ ckbX公司l,τ-bX公司l-1，τk+ch1/2l-因此，利用引理6.2的结果，存在一个常数c，使得vhe[bPl-英国石油公司l-1 | W]i≤ EE[bPl-英国石油公司l-1 | W]≤ c h公司l-1 |对数hl-1 |对于足够小的hl-这证明了定理陈述中的第一个界。对于第二个边界，我们注意到VHBPl-英国石油公司l-1 | Wi=Vhp（2）l（W）p（3）l（W，Z）- p（2）l-1（W）p（3）l-1（W，Z）| Wi=p（2）l（W）Vhp（3）l（W，Z）| Wi+p（2）l-1（W）Vhp（3）l-1（W，Z）|以上第一行是因为p（1）l（W）和p（1）l-1（W）不随Z变化，因此不影响方差。第二行来自这样一个事实，即最多只有一条粗路径和细路径被分割，因此在大多数情况下，只有一条p（3）l（W，Z）和p（3）l-1（W，Z）具有非零方差。术语p（2）l（W）和p（2）l-1（W）分别以exp（T kV k）为界∞). 使用REM 3。4到边界V[p（3）l（W，Z）]和V[p（3）l-1（W，Z）]给出了存在常数c的结果，使得vhbpl-英国石油公司l-1 | Wi≤ c E[最大值（bτl, bτl-1) -τ| W]≤ c E[| bτl-bτl-1 | | W]。上述不等式适用于随机变量W的each值。

取期望值，并使用引理6.3中的结果，然后给出最终结果，即EHVHBPl-英国石油公司l-1 | Wii=O（h1/2l-1 |对数hl-1|1/2).利用这个定理的界，我们注意到方差V的界中的两项l当Ml= O（h）-1/2l-1 |对数hl-1|-1/2).6.2预期复杂度最后，根据之前的结果，我们可以得出以下关于预期复杂度的结果，以获得ε均方根误差。推论6.5。在给定的假设下，可以通过O（ε）实现ε的均方根误差-2 | logε|）预期计算成本。证据证明与[7]中的标准多级复杂性分析非常相似，但由于使用了额外的对数hl方差中的因素意味着它不完全具有定理4.1中条件iii）中所期望的通常形式。在le Level上l ≥1、我们选择使用hl= 4.-lH带Ml= 2.l/l1/2 分裂估计器中的路径（带x个 表示x向上舍入到最接近的整数）。回顾假设2，假设每个时间步都有一个单位计算成本，一个样本的计算成本等于两条路径中的第一条退出域之前的粗略时间步和精细时间步的数量之和，加上后续Ml拆分粗路径或细路径。因此，一个样品的预期成本与水平裂缝相同l≥1 isCl≤ （h）-1.l+ h类-1.l-1） E[最小值（bτl, bτl-1） ]+米lh类-1.lE[| bτl- bτl-1 |]=O（h-1.l),自M起l=O（h-1/2l|日志hl|-引理9给出了E[| bτl-bτl-1 |]=O（h1/2l|日志hl|1/2).给定O（h1/2l) 弱收敛，以减少ε的偏差/√2要求在最低水平上hL=O（ε），而对于O（hl) 弱收敛使用Gobet&Menozzi校正，我们需要hL=O（ε）。