有效风险估计的多级嵌套模拟

事实上，细样本和粗样本之间的主要相关性是由于内部Monte Carloestimator（2.9）的强收敛性，使用独立样本足以获得（2.11）中的速率。然而，正如我们将在第3节中讨论的那样，使用对偶估计可能会将方差减少一个常数。为了表述清晰，我们在所述理论中不强调这一点。2.3. MLMC的自适应采样。在本节中，我们将第2.1节中提到的自适应采样方法应用于外部期望的MLMC估计，并分析得到的算法。我们的目标是将方差Convergence增加到O（2-`) 虽然仍然平均每个级别使用O（2`）内部样本，但MLMC复杂性为O（ε-2 | logε|）。在本节中，除了假设2.1之外，我们还根据以下假设进行工作。假设2.4。我们假设对于一些2<q<∞, 给定Y的X的qthnormalized，centralmoment对于Y的所有值一致有界，即κq：=supyEhσ-q | X-E[X | Y]| qY=yi<∞.此外，我们将重复使用以下引理：引理2.5。设zn为随机变量Z的N个i.i.d.样本的平均值，q的平均值为零，且qt矩为有限≥ 1、对于任何z>0的情况，存在风险估计的多层嵌套模拟7常数Cq，仅取决于q，因此E[| ZN | q]≤ CqN公司-q/2E[| Z | q]和P[| ZN |>Z]≤ 最小值1，Cqz-qN公司-q/2E[| Z | q].证据用{Zn}Nn=1N个Z样本表示，离散的burkholder-Davis-Gundy不等式给出了[| Zn | q]≤ CqE公司N-2NXn=1Zn！第二季度≤ CqE“N-第二季度-1NXn=1 | Zn | q#=CqN-q/2E[| Z | q]，其中cq是一个仅依赖于q的常数[4]。

第二个结果紧接着使用马尔可夫不等式并将概率限定为1。特别是，给定Y，让Z=X（Y）-E[X | Y]和ZN=bEN（Y）-E[X | Y]并使用κq的定义，我们得到（2.12）Ph本（Y）- E[X | Y]>d易≤ 最小值1，CqκqδN1/2-q.这是（2.10）的推广，当我们有界q-矩时。2.3.1. 算法。回想一下[2]中对自适应样本数的选择（2.3）。另一种选择可以由中心极限定理驱动。我们知道，用Ben表示的具有N个样本的E[X | Y]的蒙特卡罗估计值的误差大致以CpVar[X | Y]/N为界，其中C是一个密度常数。那么，我们只需要N≥ Cσ/din，以确保我们的估计本（Y）≈H（E[X | Y]）是正确的。再次施加O（ε）的最大样本数-1） ，我们得到（2.13）N=最大值O（ε-1） ，Cσd.将其与（2.3）进行比较，并注意（d/σ）的不同幂和置信常数C的引入。更一般而言，在MLMC的情况下，我们要使用的算法应确保，以Y为条件，样本数N`，在水平`，满足度N`=dN\'e，其中N`=N\'max-`, min1，C-1N1/2\'dσ-r（2.14）对于某些给定的置信度常数C和1<r<2，我们将在后面看到。选择（2.14）源于（2.3）和（2.13），其变化如下：i）水平上的样本数量现在以N为界，以8 M为界。B.GILES，A.HAJI-ALI fixed，减少r fixed r，增加δFig。

1： （2.14）中的函数N′作为δ=d/σ的函数，用于不同的andr值。N`，ii）我们引入了一般的幂r，其中，对于给定的Y值，样本数随着r的减小而增加，见图1，以及iii）我们引入了密度常数C≥（2.14）的难点在于，给定Y，我们无法先验地知道d和σ的值，因此我们使用了一种迭代算法，该算法受[2，算法3]的启发，在每次迭代时将样本数N\'加倍，然后估计d和σ。当N `满足N时，算法终止`≥bN′，其中bN′与N′相同，但分别用bd和bσ表示的d和σ的当前估计值进行计算。因此，算法的输出，N ` satifies（21.5）bN`≤ N `<20亿`。算法1中列出了完整的算法。请注意，此算法用于确定N`的内部样本数最多为（2-2.-`)N `<2 N`。2.3.2. 数值分析。在本节中，我们将说明，在假设2.1和2.4下，自适应算法有一个随机输出N`，满足[N`]=O（2`）。此外，我们将表明，通过随机选择内样本数，我们得到了VarhH本`（Y）-H（E[X | Y]）i=O（2-`). 从这里开始，使用标准的MLMC复杂性分析，我们方法的复杂性为O（ε）-2 | logε|）。我们从引理2.6开始，当我们完全了解d和σ时，证明结果，然后在定理2.7中，我们考虑当nbd和bσ是d和σ的蒙特卡罗估计时的情况，给出Y。在下文中，我们将用（2.16）ν表示“归一化δ”：=C-1N1/2`δ，引理2.6（完美自适应采样）。

在假设2.1和2.4下，对于使用算法1获得的估计量（2.5）和样本数N\'，风险估计的多级嵌套模拟9算法1：确定N的自适应算法。数据：`，y，N，rResult:N `set N`:=N`；设置完成：=假；重复/*如果我们继续自适应算法，将使用至少2N个内部样本（此步骤中为N个样本，然后在计算蒙特卡罗估计时为另一个N个样本）。因此，如果2N`大于最大内部样本数，则终止*/如果2N`≥ N`thenset N`:=N`；设置完成：=真；elsegenerate新的、独立的内部样本；计算新的估计值sbd和bσ，给定Y=Y；如果N`≥ 不适用-1N1/2“bdbσ！-rhenset done：=真；elseset N`：=2N`结束结束；返回N`；1<r<2-2/q，bd=d=| E[X | Y]|，bσ=σ=Var[X | Y]我们有E[N`]=O（2`）和VarhH本`（Y）- H（E[X | Y]）i=O（2-`).议论尽管这个引理的设置是理想化的，因为它假设了d和σ的完美知识，但它的证明仍然说明了重要的观点。第一点是使用（2.12）来限制蒙特卡罗平均值的尾部概率。第二点是r值的界∈(1, 2-即使拥有如此完美的知识，也需要2/q）。如前所述，随着r的增加，对于相同的y值，所需的内部样本数减少。这意味着，根据条件r<2-2/q或何时q→∞, 我们希望r尽可能接近2，以减少所需内部样本的总数，同时保持相同的方差收敛速度。另一方面，例如，如果我们只有有界的四阶矩，即q=4，那么我们必须使r<3/2才能具有相同的方差收敛速度。证据在这个引理中，我们假设我们对d和σ有很好的了解，hencebN=N。回想一下，自适应算法的输出满足（2.15）。10 M.B.GILES，A。

哈吉·阿利滕，假设我们有，E[N`]≤ 2N\'Z∞最大值-`, 最小值1.C-1N1/2 `δ-rρ（δ）dδ（2.17）≤ 2N`+2N`Z∞最小值1.C-1N1/2 `δ-rρ（δ）dδ≤ 2N`+2N`ρZ∞最小值1.C-1N1/2 `δ-rdδ+2N\'min1.C-1N1/2 `δ-r≤ 2N`+2CN1/2ρrr-1`+2克朗（2-r） /2δ-r（2-r） `，我们首先使用（2.7），然后使用（2.8）。自2日起-r<1，我们有E[N`]=O（2`）。另一方面，根据（2.12），VarhH本`（Y）-H（E[X | Y]）i≤ EhPh本`（Y）-E[X | Y]>dYii型≤ E“min1，CqκqdσN1/2`-q！#。使用（2.16）中ν的定义和N`≥N\'，我们有var[H本`（Y）-H（E[X | Y]）]≤ E“min1，CqκqC-qν-q不，不`-问题2#≤ 最小照度1，CqκqC-qν-qmin`q/2，最大值（1，νrq/2）我≤ ρZ∞最小值1，CqκqC-qν-最大尿流率1，νrq/2dδ+最小值1，Cqκq-`第二季度-q/2δ-q≤ ρCN-1/2-`Z∞最小值1，CqκqC-qν-q1+νrq/2dν+Cqκq-`第二季度-q/2δ-q、 我们首先使用（2.7），然后将积分变量从δ改为ν。第一项中的积分是一个独立于`的常数，可以使用（2.8）计算，因为q-rq/2>1。因此，由于q>2，方差为O（2-`).定理2.7（使用BD和bσ-估计量的自适应采样）。假设2.1和2.4保持不变，并考虑估计量（2.5）和使用算法1获得的样本数N'（2.18）1<r<2-√第4季度+1- 第1季度。进一步假设，在给定Y的算法的每次迭代中，当前样本数N′，和{x（m）（Y）}N′N=1是给定Y的x的i.i.d.样本，我们估计风险估计的d多层嵌套模拟11和σbybd=本`（Y）=N\'N\'Xn=1x（N）（Y）（2.19）和bσ=N\'N\'Xn=1x（n）（Y）-本`（Y）,（2.20）。然后我们有e[N`]=O（2`）和VarhH本`（Y）- H（E[X | Y]）i=O（2-`).在证明这个定理之前，我们将在估计方差σ时产生给定错误的概率与（2.20）绑定。推论2.8。假设2.4成立。对于固定的“=”。

2`和a givenY，表示为bσ`使用X的N个样本计算σ的估计，Y由（2.21）bσ`=N\'N\'Xn=1给出x（n）（Y）-本`（Y）,然后，对于任何常数c>0，存在一个常数c，仅取决于N，κq，qa和c，这样pHbσ`- σ> cσ易≤ c-q`/4，证明。我们可以写出bσ`=N`N`Xn=1x（n）（Y）- E[X | Y]-本`（Y）- E[X | Y].接下来，使用引理2.5和E[（X-E[X | Y]| Y]=σ，yieldsPhbσ`- σ> cσ易≤ PN\'N\'Xn=1x（n）（Y）- E[X | Y]- σ>cσY+ P本`（Y）- E[X | Y]>c1/2σY≤ 第2季度/第2季度/第2季度-q/2κqN个`-4季度+2季度/2季度质量控制-q/2κqN个`-第二季度≤ c-q`/4。推论2.9。假设2.4成立，并假设在算法1内循环的每次迭代中，σ由bσ估计，如（2.20）所示。然后，存在一个常数C，例如pH | bσ- σ|>cσ易≤ c-q`/4，尤其是对于返回N`之前在算法1中计算的σ的最终估计，这是正确的。12 M.B.GILES，A.HAJI ALIProof。使用推论2.8，Pbσ- σ> cσY≤2`X`=`Phbσ`- σ> cσ易≤ c2`X`=`-q`/4≤c1类- 2.-第4季度-q`/4。我们现在准备证明定理2.7。证据首先，对于给定的Y值和相应的δ=d/σ，假设在完全了解δ的情况下，自适应算法将返回N`*作为内部样本数，用于`≤`*≤2`. 给定停止条件，我们得到（2.22）(`*-1)`<C-1N1/2 `δ-r≤`*`,无论何时`<`*≤ 2 `对于左不等式和任何时候`≤ `*< 2 `代表权利不平等。此外，假设对于给定的Y，算法1返回N`=Nb` for `≤b`≤ 2`并将BD和bσ分别作为算法1中计算的d和σ的最终估计值。通过分析B’s显著不同于`*约束差异和工作。在下文中，O（·）表示法中的常数仅取决于κq、q、N、C和r。界定工作范围。

为了限制工作，我们考虑了自适应算法终止于如下水平的情况`≥ `*+ 3用于`≤ `*≤ 2` -3，即返回太多内部样本的情况；这里的“太多”意味着自适应算法返回的样本数至少比我们使用d和σ代替其近似值bd和bσ时返回的样本数多2个。选择`*+3有点武断`*+2是确保证明中某些项的正性的最小值，但这种特殊的选择简化了子序列代数。在任何情况下`≥`*+3表示自适应算法的终止条件在每个(`-`)算法的迭代`*+2.≤`< `. 利用（2.22）中的右不等式，得出C-1N1/2\'bδ`-r≥``≥ 4`*`≥ 4.C-1N1/2 `δ-r==>bδ`<4-1/rδ，其中bδ`=bd`/bσ`，bd`和bσ'分别表示使用N'个内部样本对d和σ的蒙特卡罗估计。然后，由于算法1的运算中使用的内部样本是相互独立的，因此我们得到了p[b`=` | Y]≤`-1年`=`*+2P级dbd`·bσ`∑>41/rY≤`-1年`=`*+2.博士>21/rbd`Yi+Phbσ`>41/rσ易,风险估计的多级嵌套模拟13`≥`*+3、使用（2.22）和（2.12）中的右不等式，Yieldshd>21/rbd`Yi=博士-bd`>1.- 2.-1/rd易≤ 酸碱度本`（Y）- E[X | Y]>1.- 2.-1/rCσN-1/2-`(2`-`*)/r易≤1.- 2.-1/r-qCqκqC-q-q（（2`-`*)/r-(2`-`)/2)≤ O（2-q（`-`*)/2).此外，使用推论2.9，对于任何Y，Phbσ`>41/rσ易≤ Ph | bσ`- σ|>（41/r- 1)σ易≤ O（2-q（`-`*)/4).因此，对于任何`*+3.≤`≤2`和`≤`*≤2`-3，我们有（2.23）P[b`=``Y]≤`-1年`=`*+2O（2-q(`-`*)/4) ≤ O（2-q（`-`*)/8).一般来说，这将P[b`=` | Y]作为所有`≤`*≤2 `因为P[b`=` | Y]=0`*+3.≤`≤2`每当2 `-3 < `*≤2`.

接下来，以Y为条件，计算期望的样本数N`，如下所示不，不`Y=2\'X`=\'P[N`=N` | Y]2`-2`≤ 2`*+3.-2`+2`X`=`*+3P[b`=`Y]2`-2`.≤ 2`*+3.-2`+O`*-2`2英尺X`=`*+3.-q（`-`*)/8+`-`*,我们在最后一步中替换了（2.23）。由于上一个方程中的和对于任何q都是有界的，我们使用`*在（2.22）中，`≤`*≤2 `和νin（2.16）的定义，即不，不`Y= O`*-2`= O（最小值1，最大值-`, ν-r),对于ν的所有值，与（2.17）类似的计算给出了预期内部样本总数的期望界限。限定方差。在界定方差时，我们希望控制b `显著小于`*, i、 例如，返回内部样本的概率比我们使用d和σ而不是其近似值bd和bσ时返回的内部样本数量少得多。尤其是b`<`*意味着BD高估d和/或bσ低估σ。我们首先处理的是14 M.B.GILES，A.HAJI，后者表示G`:=H本`（Y）-H（E[X | Y]），并写出方差a（2.24）Var[G`]≤ EE[G` | Y]= EE[G` | Y，bσ>bσ]P[bσ>bσ| Y]+ EE[G\'bσ≤bσ| Y].对于某些常数0<b<1，独立于``*andb`。（2.24）中的第一项处理的是bσ低于σ的情况，而第二项处理的是相反的情况。使用推论2.9，我们得到，对于任何Y，Pbσ>bσY≤ P|σ- bσ|>1.- bσY≤ O（2-q`/4）。另一方面，由于用于计算G`的内部样本独立于用于计算N`的内部样本，我们可以对任何Y进行绑定，E[G` | Y，bσ>bσ]=E[G` | N`]| Y，bσ>bσ]=E[P[| bEN`（Y）- E[X | Y]|≥ d | N`]| Y，bσ>bσ]≤ E[最小值1, δ-2N个-1`| Y、 bσ>bσ]≤ 最小值1, δ-2N个-1.-`.这里，我们使用（2.10），然后N`≥N `。

尊重Y并使用（2.7）和（2.8），我们得到了E[G` | Y，bσ>bσ]≤ 2ρN-1/2-`/2+ δ-2N个-1.-`.因此，（2.24）中的第一项为O（2-`/2.-q`/4）=O（2-`), 自q起≥2、现在，我们将注意力转向（2.24）中的第二项，其中估计值bσ并不显著低于估计值σ，即给定bσ≤ bσ。首先，对于一些p∈(2/(2-r） ，q），我们受（2.12）E[G\'bσ≤bσ| Y]=EhE[G ` | Y，bd，bσ]1bσ≤bσ易≤ EhPh本`（Y）-E[X | Y]>dY、 bd，bσibσ≤bσ易≤ E最小值1，CpκpδN1/2`-pbσ≤bσY≤ E最小值1，CpκpδN1/2`-pbσ≤bσY≤ min1，CpκpC-pν-pE“不，不`-p/2bσ≤bσY#！。这里我们使用了这样一个事实，即用于计算G`的内部样本与用于计算d和bσ的内部样本是独立的。我们将继续限定n `太小的概率，然后用这个概率来限定条件期望sehN个`/N个`-p/2bσ≤bσ易。最后，我们通过遵循引理2.6证明中的相同步骤得出结论。首先，我们要解决的问题是：如果`≤`*-3和bσ≤bσ？一、 e.返回太少内部样本的概率；这里的“太少”意味着自适应算法返回了风险估计的大多数多级嵌套模拟的一小部分151/2样本，如果我们分别使用d和σ而不是其近似值bd和bσ，它将返回这些样本。选择`*-3有点武断`*-2是确保证明中某些项的正性的最大值，但这一特殊选择简化了后续代数。无论如何`≤ `*-3，算法1中的终止条件和（2.22）中的左不等式意味着C-1N1/2\'bδ-r≤``≤·(`*-1)`<C-1N1/2 `δ-r==>bδ>41/rδ，对于`≤ `≤`*-3和`+3≤`*≤2`.

因此，选择b使4-1/r<b<1，wehaveP[b`=`，bσ≤ bσ| Y]≤ P“bdd·∑bσ>41/r，bσ≤ bσY型#≤ Phbd>41/rbd，bσ≤ bσ易≤ Phbd- d>1.- 4.-1/rb-1.bd，bσ≤ bσ易≤ Ph | bd- d |>b- 4.-1/rCσN-1/2-`(2`-`)/r、 bσ≤ bσ易≤ 酸碱度本`（Y）- E[X | Y]>b- 4.-1/rCσN-1/2-`(2`-`)/r易≤b- 4.-1/r-qCqκqC-q-q（2`-`)（1/r-1/2).此外，对于`P[b`=`Y]=0≤`≤`*-3无论何时`≤`*< `+因此（2.25）P[b`=`，bσ≤ bσ| Y]=O（2-q（2`-`)（1/r-1/2）），用于`≤`≤`*-3和`≤`*≤2`. 现在，我们有了这个“不，不`-p/2bσ≤bσY#=2 ` X `=` P[N `=N\'，bσ≤ bσ| Y]2p（2`-`)/2.≤ 2p（2`-`*+2)/2+`*-3X`=`P[b`=`，bσ≤ bσ| Y]2p（2`-`)/2、代入（2.25）并表示u：=q（r-2） /r+p产量“不，不`-p/2bσ≤bσY型#≤ 2p（2`-`*+2)/2+`*-3X`=` O（2u（2`-`)/2)≤ 2p（2`-`*+2） /2+Ou（2`-`*+2)/2- 2u`/2-u/2- 1..注意（2-r） q=2r的根r=2-(±√第4季度+1-1） /q，因此从（2.18）我们得到q>2r/（2-r） 。因此，我们可以选择p来满足2/（2-r） <p<q（2-r） 在这种情况下，我们有u<0<p和之前的条件期望16 M.B.GILES，A.HAJI ALIis O（2p（2`-`*)/2） 无论何时`≤`*≤2`. 在上使用绑定`*在（2.22）中，`≤`*≤2`和νin（2.16）的定义，yieldsE“不，不`-p/2bσ≤bσY#=O（2p（2`-`*)/2） =O最大值1，最小值`p/2，νrp/2.对于ν的所有值。条件p>2/（2-r） 意味着r<2-与（2.18）相似的计算结果表明（2.24）中的第二项也是O（2-`).因此Var[G`]=O（2-`).3、模型问题。在本节中，我们将看一个简单的示例，该示例模拟了计算金融投资组合的重大损失概率所面临的许多挑战。事实上，潜在的模型问题可以被视为单一期权的损失，股票遵循布朗运动，最终支付函数f（x）=-X到期时评估，T=1。