期权定价中的维度诅咒与最优解

我们相信，类似的方法可以应用于文献中的其他最优停止问题，并且可以证明更强的收敛速度，这是未来研究的有趣方向。4.5. 在这一部分中，我们提供了一些例子，说明收敛速度可能比定理2中证明的要快得多。我们的例子还表明，即使对于玩具问题，我们的扩展也会导致非平凡的动力学，我们将深入理解这些动力学的问题作为未来研究的一个有趣方向。事实上，准确理解ZK和相关余项的分布是如何在i.i.d.c情况下进行的仍然是一个有趣的开放问题。4.5.1. 一次迭代收敛的示例。考虑到水平长度T一般，且存在固定的非负常数a、b s.T.P（Zt∈ {a，b}）=1表示所有t∈ [1，T]，否则Z的联合分布是基因ral。也就是说，ZT对所有t都有相同的2点支持∈ [1，T]。引理10。在此设置中，E=OPT。Chen和Goldberg：战胜期权定价中的维度诅咒和最优止损证明：假设w.l.o.g.t认为a<b。那么，从一个直接的矛盾中可以看出，最优策略是在第一时间t止损，Zt=a，d在时间t止损，否则。因此，OPT=a×P造币厂∈[1，T]Zt=a+ b×P造币厂∈[1，T]Zt=b= E、 Q.E.D.我们注意到，每当T=1或每个zt都有零方差时，收敛也会发生在一次迭代中。4.5.2. 快速和慢速指数收敛的示例以及定理5的证明。对于一般n≥ 1，考虑T=2，D=1，Zt=YT的设置∈ [1，2]，且P（Y=n）=1，P（Y=1）=n，P（Y=0）=1-n、 引理11。

在此设置中，对于所有k≥ 1，可选- Ek=n×（1-n） 证明：首先，我们不需要通过一个简单的归纳，V ar[Zk]=0 f或所有k≥ 1，即Zkisalways w.p.1为常数（可能取决于k）。由于Z是一个鞅，它从optionalstopping that OPT=n得出。然后从定义和鞅性质的基本保持性质得出，zk是所有k的鞅≥ 1，并因此通过可选停止fτ∈TE公司Zk+1τ= EZk+1对于所有k≥ 1、用引理1证明期望的结果，必须证明Zk公司=n×（1）-n） k级-1对于所有k≥ 由于zk总是某个常数，因此可以通过归纳法证明PZk=n×（1-n） k级-1.= 1代表所有k≥ 基本情况k=1是微不足道的。现在，假设归纳法适用于k≥ 1、利用mart-ingale性质和归纳假设，可以得出Zk=n×（1）-n） k级-1和Zkequals（1-n） k级-1瓦。p、 n和0 w.p.1-n、 因此，Zk+1等于Zk- E造币厂∈[1,2]Zkt=n（1-n） k级-1.- （n） （1）-n） k级-1=n（1-n） k，完成证明。Q、 注意，如果n很小，例如2，则引理11表示指数收敛迅速。然而，如果n很大，引理11表示指数收敛速度，但速度很小。我们现在用这个观点来完成定理5的证明。定理5的证明：注意对于任何n≥ 2, (1 -n） k级≥对于所有k≤ n完成proo f.Q.E.D.4.5.3。各种2周期示例。现在我们提供了各种简单的2周期示例。在所有情况下，第一个周期的r.v.是一个常数，第二个周期的r.v.是指数分布还是均匀分布。有趣的是，我们发现，即使在这种简单的环境中，各种非琐碎的行为也是可能的。对于两个r.v.s X，X，设X=dx表示分布中的等效性。设X为Expo（1）r.v.，即指数分布的r.v。v

平均值为1；对于p∈ [0,1]，设B（p）表示一个成功概率为p的伯努利r.v.Chen和Goldberg：在期权定价和最优止损中击败维数诅咒。e、 PB（p）=1= p=1- PB（p）=0. 进一步假设B（p）独立于X。对于X>0，letU（X）表示在[0，X]上均匀分布的r.v.，其中{U（X），X>0}，{B（p），p∈ [0，1]}相互依赖。我们把所有的证据都放在技术附录中。指数分布：平衡平均值。考虑T=2、D=1、Zt=YT的设置∈ [1，2]，P（Y=1）=1，Y=dX。引理12。在此设置中，limk→∞k×（可选- Ek）=1。注意，尽管该设置超出了定理2的范围，但由于r.v.s是u边界，收敛速度仍然是Θ（k）。指数分布：不平衡平均数。考虑T=2、D=1、Zt=YT的设置∈ [1，2]，P（Y=）=1，Y=dX。引理13。在此设置中，limk→∞k-1×对数（可选- Ek）=- 日志（2）。有趣的是，在平衡和非平衡ncedmeans的情况下，收敛速度非常不同，因为引理13表明，对于任何>0和所有足够大的k，选择- Ek<经验值- （日志（2）- ）k.均匀分布：均衡分布。考虑T=2，D=1，Zt=YT的设置∈ [1，2]，P（Y=1）=1，Y=dU（2）。引理14。在此设置中，limk→∞k×（可选- Ek）=4。有趣的是，这种情况下的收敛速度是Θ（k），比定理2中证明的最坏情况下的（k）收敛速度快，以及当Zis指数分布时的Θ（k）收敛速度（用平衡平均值）。5.

仿真分析和定理6-7、推论2-3的证明在本节中，我们完成了算法分析、定理6-7和推论2的证明。然后，我们结合我们的收敛性结果，制定具有类似性能保证的有效策略，完成推论3.5.1的证明。计算zktre的高效随机算法为每个k调用≥ 1和t∈ [1，T]，zktc可以被认为是tto R+（根据我们前面提到的警告，所有R.v.s对en s尿道完全无病理性，gs中的所有相关条件都得到了适当的定义）。现在，我们正式确定了一个事实，即通过利用递归定义，我们可以构建一个“良好”算法hm来近似Zk+1t（γ）Chen和Goldberg：克服期权定价和最优停止中的维数诅咒给定了一个“良好”算法来近似Zkt（γ′）f或所有相关γ′。我们注意到，由于我们的算法只尝试计算模拟器实际输出的rγ的Zkt（γ），因此我们的方法永远不会试图计算不确定的量。我们进一步注意到，虽然我们在此正式描述的所有算法都假设所有r.v.s都有界（在最大化框架中通过适当的截断），然后使用Hoeffing不等式显示适当的集中度，但这种假设根本没有必要，我们的算法可以很容易地适应无界情况，通过C hebyshev不等式或任何其他需要较弱假设的集中结果来重新放置Hoeffing不等式。通过与例如定理4相结合，可以证明（在比有界性弱的适当假设下，例如适当有界矩），可以导出有效的近似算法。对于，δ∈ （0，1），设N（，δ）= 2log（δ）.5.1.1. 算法的形式定义。

现在，我们递归地定义相关的算法序列，算法Bk（t，γ，，δ）将（加法）-近似值恢复为Zkt（γ）w。p、 至少1个- δ（我们将很快使其完全精确）。回想一下，对于t∈ [1，T]和γ∈ t、 Y（γ）表示分布为Y的随机矩阵，条件是事件{Y[t]=γ}。我们也将基本模拟器B称为随机d算法，它作为输入t∈ [1，T]和γ∈ t、 并输出Y（γ）的独立样本。此外，回想一下，对于t∈ [1，T]和γ∈ t、 gt（γ）等于zt的值，条件是事件{Y[t]=γ}。为了便于标记，首先确定算法B会很有帮助，该算法也会输入t、γ、、δ，尽管我们注意到，在形式上这是多余的，因为该算法将简单地返回准确的值gt（γ）。算法B（t，γ，，δ）：返回k的gt（γ）≥ 我们对Bk+1的定义如下。算法Bk+1（t，γ，，δ）：为i=1到N（，δ）创建一个长度为N（，δ）的向量a，生成对B（t，γ）的ind.调用，并通过t矩阵a存储在D中，为j=1创建一个长度为t的向量a，以生成对Bk的ind.调用j、 A[j]，，δ4N（，δ）T存储在AjChen和Goldberg：击败期权定价和最优停止中的维数诅咒计算A的最小值并存储在A生成一个ind。调用Bk（t，γ，，δ）和st ore作为变量返回A-N（，δ）-1PN（，δ）i=1Ai5.1.2。Bk的形式化分析。我们现在正式分析Bk，在适当的sen集合中证明它确实是一个逼近Zk+1t（γ）的“好”算法。首先，我们回顾了概率论的一个标准结果，该理论常用于证明估计量的集中性。引理15（霍夫丁不等式）。假设对于某些n≥ 1和U>0，{Xi，i∈ [1，n]}是i.i.d.，和P（X∈ [0，U]）=1。

然后是Pn-1Pni=1Xi- E[X]≥ η≤ 2经验值-2ηnU.回想一下fk（，δ）=102（k-1)× -2（k-1） ×（T+2）k-1×1+对数（δ）+对数（）+对数（T）k-1、我们还需要以下辅助引理，证明Fksaties是与OUR算法性能相关的某些递归，其证明我们遵从技术附录。引理16。对于所有，δ∈ （0，1）和k≥ 1，fk+1（，δ）≥N（，δ）+1×（T+2）×fk，δ4N（，δ）T.利用引理15和16，我们现在证明以下结果，这证明BK是一个“好”算法。引理17。对于所有k≥ 1，t∈ [1，T]，γ∈ t、 ，δ∈ （0，1），当对t，γ，，δ进行评估时，算法BK实现以下目标。在最多（C+G+1）fk（，δ）的总计算时间中，以及在对基本模拟器B调用最多fk（，δ）的随机性时，返回一个满足P的随机数X|十、- Zkt（γ）|≥ ≤ δ.证明：我们继续归纳。基本情况k=1是微不足道的。现在，假设归纳法对一些k是真的≥ 1、我们首先证明Bk+1满足期望的概率误差界。让{Xi，i∈ [1，N（，δ）]}是r.v.s的一个i.i.d.序列，每个序列以最小值分布∈[1，T]Zki（Y（γ）[i]），其中Y（γ）的相同实现用于所有i∈ [1，T]。然后，它遵循我们的归纳假设，最小函数的Lipschitz性质，一个覆盖所有i∈ [1，N（，δ）]和j∈ [1，T]和一些简单的代数，我们可以构造{Xi，i∈ [1，N（，δ）]}和{Ai，i∈ 概率至少为1的公共概率空间s.t上的[1，N（，δ）]}-δ、 | Xi-Ai |<所有i∈ [1，N（，δ）]。

将引理15应用于{Xi，i∈ [1，N（，δ）]}，通过参数η=，U=1，N=N（，δ），我们得出结论（对于一些简单代数），在相同的概率空间上，PN（，δ）-1N（，δ）Xi=1Xi- E[X]<≥ 1.-δ.Chen和Goldberg：战胜期权定价和最优止损中的维度诅咒我们注意到，在上面我们应用了引理15，U=1，因为Xi∈ [0，1]对于所有i≥ 1.注意事项|xi- Ai |<所有i暗示事件N（，δ）-1N（，δ）Xi=1Ai-N（，δ）-1N（，δ）Xi=1Xi<,我们可以将上述内容与并集boun d和三角形不等式结合起来，得出结论，在相同的概率空间（和一般的h ence）上，PN（，δ）-1N（，δ）Xi=1Ai- E[X]<≥ 1.-δ.因为归纳假设确保PA.- Zkt（γ）≥≤δ、 我们可以再次应用联合和三角形不等式，以及Zkt（γ）和X的定义，得出以下结论：A.-N（，δ）-1N（，δ）Xi=1Ai- Zk+1t（γ）≥ ≤ δ符合要求。（8） 接下来，我们证明Bk+1满足所需的计算和样本复杂性边界。对Bk+1随机性的唯一访问是通过其N（，δ）直接调用B（t，γ）（其ou tputis每次存储在A中），其N（，δ）t调用Bkj、 A[j]，，δ4N（，δ）T, 它的最后一个调用toBk（t，γ，，δ）（输出存储在A中）。因此，根据归纳假设以及N和fk的几个易于验证的单调性，Bk+1（t，γ，，δ）对基本模拟器的调用次数最多为tn（，δ）+N（，δ）×t×fk，δ4N（，δ）T+ fk（，δ）≤ N（，δ）×（T+2）×fk，δ4N（，δ）T. （9） 接下来，我们将重点讨论计算成本。

在外部for循环的N（，δ）次迭代（由i索引）中，第一次直接调用B（t，γ）（计算成本为C）；然后打电话给Bkj、 A[j]，，δ4N（，δ）T（对于不同的j值），每种计算成本最多为（C+G+1）×fk，δ4N（，δ）T; 然后计算长度T向量的最小值（在计算成本T）。然后再调用Bk（t，γ，，δ），计算成本最多为（C+G+1）×fk（，δ）；最后，以计算成本N（，δ）+1计算并从A中减去Ais的N（，δ）元素的平均值。因此，根据归纳假设以及N和fk的几个易于验证的单调性，Bk+1（t，γ，，δ）的计算成本为mostN（，δ）c+N（，δ）t（c+G+1）fk，δ4N（，δ）TChen和Goldberg：战胜期权定价和最优停止中的维度诅咒+T+（C+G+1）fk（，δ）+N（，δ）+1≤ （C+G+1）×N（，δ）+1×（T+2）×fk，δ4N（，δ）T. （10） 结合引理16，完成了Q.E.D.5.2的程序。定理6和推论2的证明利用引理17，我们现在完成了主要算法结果定理6和推论2的证明。首先，让我们正式定义相关的算法^Bk，它将使用Bkandsimulation来近似Hk。算法^Bk（，δ）：为i=1到N（，δ）创建一个长度为N（，δ）的向量，生成对B（0，) 并将矩阵a存储在D中，为j=1创建一个长度T向量a，以生成对Bk的ind调用j、 A[j]，，δ2N（，δ）T并存储在AJ中计算A的最小值并存储在AiReturn中N（，δ）-1PN（，δ）i=1定理6的极限：根据引理17，结果来自一个并定界，引理15和16 n的应用早期与我们之前的证明中使用的相同，因此是一个简单的代数，其中我们将n（，δ）与n（，δ）绑定，并将fk（，δ2N（，δ）T绑定通过fk（，δ4N（，δ）T,我们省略了细节。

计算复杂性和样本复杂性的说明也几乎相同，我们同样省略了细节。Q、 我们将推论2的证明推迟到技术附录中。5.3. 最大化算法和定理7的证明在本节中，我们将展示如何将我们以前的算法与适当的变换和仔细截断参数相结合，以证明定理7。在此过程中，我们将证明几个与E[maxt]相关的一般边界∈[1，T]Zt]，这对于最终证明适当的相对误差界至关重要。粗略地说，我们表明只要最大方差的平方系数∈[1，T]T不是太大，然后\\T选择[maxt∈[1，T]Zt]不能太小。虽然许多密切相关的结果，例如，在之前几篇与prophet不等式相关的论文中，都出现了辅助界限，但由于我们无法找到我们需要的精确界限的精确参考，我们将p Roof forChen和Goldberg纳入了《击败期权定价中的维度诅咒和最优终止完整性》（通常将细节推迟到技术附录中）。给定一个错误tole rance，我们接着执行：1。将所有值存储在适当的E[最大值]倍数处∈[1，T]Zt]，2。规范化并转化为最小化io n p问题，以及3。在我们的展开式中计算适当数量的项。结果表明，如果最大值的平方变化系数得到了很好的控制，那么，如果将项的位置和数量作为和该平方变化系数的函数，则所有误差都可以得到适当的控制。对于U>0，让ZU，t= U-1×min（U，Zt）；Z1，-U、 t型= 1.- ZU，t；对于k≥ 1，Zk+1，-U、 t型= Zk，-U、 t型-E[微型∈[1，T]Zk，-U、 i |英尺]。

回想一下，M=E[最大值∈[1，T]Zt]，M=E最大值∈[1，T]Zt, γ=M（M）。对于k≥ 1和U>0，设H-U、 k级= E[铸币厂∈[1，T]Zk，-U、 t]和E-U、 k级=Pki=1H-U、 在正式描述相关算法之前，我们验证了几个辅助结果，为我们的基于截断的d方法奠定了基础。沿着这些思路得出的关键结果如下所示，即如果我们在展开式中计算出足够数量的项，则计算出经过处理和归一化的r.v.s，再乘以归一化常数，把它作为[OPT]的近似，我们可以控制相对于[OPT]的误差。我们的语句还允许f有一定的误差项z，这将在以后成为额外的误差，因为所有的量都只能被模拟（我们也将控制）。定理9。对于所有U>0，k≥ 1和z∈ R[选择- U×1.- E-U、 k+z≤ 7 × γ×嗯×（k+1）-1+| z|+ （UM）-×[选择。我们将定理9的证明提交给技术附录。接下来，我们将描述几种相关算法。在所有情况下，这些算法将（非常）与之前定义的算法msbk（t，γ，，δ）和Bk（，δ）略有不同，本质上是相同的，只是现在有一个额外的参数U输入到算法中，这会导致算法执行所有计算，就像gtare等于g′t=1一样- U-1×min（U，gt）。首先，我们定义适当的“基本情况”算法。算法B1，-（t，γ，，δ，U）：返回1- U-1×最小值U、 gt（γ）对于k≥ 1，我们定义Bk+1，-（t，γ，，δ，U）如下。