尽管Chen和Glasserman（2007）进行了密切相关的观察，但似乎最佳停止和最大流量/最小切割之间的明确联系是新颖的。我们将进一步探索这一联系，例如，应用其他算法，从成熟的最大流量理论到最佳停车和期权定价，作为未来研究的一个有趣方向。此外，我们注意到，最优停止和期权定价因此为网络流量作为建模工具和优化框架的强大功能提供了另一个简单而优雅的证明。N的特殊结构赋予了潜在的最大流量问题一些特殊的特征，这可能有助于设计其他流量检测算法以实现最佳停止。我们注意到，有大量关于网络相关家族的专门算法ms的文献（Br ucker（1984）、Ho Off man（1988）、Goldberg and Tarjan（1988）、Ho Off man（1992）、Vishkin（1992）、Cohen（1995））。例如，让我们回顾一下，在s-t流问题中，阻塞流是一种可行的流，因此每个s-t路径至少有一条饱和边，即其流量等于该边的capa城市的边。众所周知，在一般的最大s-t流量问题中，阻塞流量不一定是最优的，尽管任何最优流量都必须是阻塞流量。然而，在树状网络（如N）中，每个阻塞流都是最优的，这是事实。一位直截了当的Chen和Goldberg的主张如下：击败期权定价和最优停止矛盾论证中的维度诅咒，这是众所周知的，我们省略了细节（Hooffman（19851992））。

这一事实提供了一种不同的方法来解释0-sure-optimal对偶鞅的几个性质，这些性质在以前的工作中出现过，这些性质都归结为这样一个事实：如果某个过程沿每个样本路径都有一个零，那么某个鞅必须是对偶最优的。由于最大流量已经是一个多项式时间的可解问题，而Nis上的最大流量问题由于其树结构更容易解决（事实上可以通过一个简单的动态程序来解决，该程序在概念上相当于反向归纳法以达到最佳停止），人们当然可以问，为什么路径相关的最佳停止ping应该被视为一个难题。答案是，eve n非常快的最大流量算法通常集中在节点和边数的运行时多项式上，对于路径相关的最优停止，它将在T中呈指数增长。我们的纯对偶表示和定理1可以解释为这类流量问题的算法，它在一系列回合中同时沿所有路径增加流量（我们展开的每一项对应于给定回合中推动的总流量）。例如，在第一轮中，a流沿着对应于γ的s-t路径推动∈特奎尔斯造币厂∈[1，T]Zt（γ[T]）×P（Y【T】=γ），并且第一轮的总流量pu（通过将所有部分相加）等于E【mint∈[1，T]Zt]。类似地，对于t∈ [1，T- 1], γ ∈t、 一个d v∈ S、 第一轮沿边缘（nγ，nγ| v）推动的流量等于E迷你∈[1，T]Zi英尺+1（γ| v）×PYt+1=γ| v, 我们注意到，可行性（水资源保护能力）来自以下事实：迷你∈[1，T]Zi英尺+1（γ| v）≤Zt+1（γ| v）。在给定的轮数后，Theorem 2限制了与最优性的距离，而我们的算法结果可以解释为提供了一种非常快速的随机算法，可以预先预测每轮中推动的流量（因此是最佳值本身）。3.4.

当然最优对偶和算法加速在这一节中，我们对某些对偶鞅可能是最优的这一更严格的意义进行了评论，注意到我们的方法不具备这一性质，并推测这可能在允许我们的方法如此快速地产生近似解方面起着重要作用。对于1≤ t型≤ t型≤ T，let Tt，tdenote所有整数值停止时间τ的集合，适用于F，s.T.w.p.1 T≤ τ ≤ t、 让我们说M∈ Mhas确定的最优性质（w.r.t.Z）如果：1。P造币厂∈[1，T]Zt公司- Mt公司= 选择=1.和2。就我而言∈ [1，T]，P造币厂∈【i，T】Zt公司- Mt+Mi= infτ∈Ti，TE【Zτ| Fi】= 1.我们注意到这里我们只提到了0-均值鞅，因为它简化了相关的讨论（并且是w.l.o.gby适当的翻译和已知的结果）。如Schoenmakers等人（2013）所述，每个最优停止问题都有这样一个确定的最优对偶解，这一性质可能有助于算法设计，因为它产生了具有零方差的某些超上界的最优性特征。Schoenmakers et al.（2013）还指出，有一些对偶方法是0-sure-optimal martingales，但不一定是最优鞅，尽管大多数方法是Schen和Goldberg：在期权定价和最优止损中击败维数诅咒在最优对偶解上的实际收益率。有趣的是，正如我们现在通过一个简单的例子展示的那样，我们的方法不一定会产生一个最优鞅，在这个例子中，我们将所有相关的证明都推迟到技术附录中。考虑尺寸D=1，地平线T=3的设置；Y=0 w.p.1；Y=1w。p、 1；没错。p、 ，等于1 w.p。；停止问题就是infτ∈TE[Yτ]，即gt（Y[t]）=所有t的Y∈ [1, 3].引理7。在此设置中，唯一（0-mea n）肯定最优对偶鞅M satifiesm（0）=M（0，1）=0，M（0，1，1）=，M（0，1，）=-.

因此，P（M=0）=P（M=0）=1，而P（M=）=P（M=-) =. 然而，我们的方法得出的最优对偶鞅MAR对所有t都满足P（MARt=0）=1。我们怀疑，缺乏确定的最优性可能是我们的方法实现快速近似的根本原因。直觉上，任何产生确定最优对偶鞅的方法（在某种意义上）都必须解决N的所有子树上定义的所有子问题。我们的近似方法是快速的，因为它不必这样做。我们将把这种推理形式化，并理解相关的下界以及我们的方法与对偶公式的联系作为未来研究的一个有趣方向。收敛速度和定理2-5的证明在这一节中，我们证明了定理2-5，这是我们关于收敛速度的主要结果。在这一过程中，我们证明了一个更强的路径收敛结果，这将使我们能够在ApproxiateValue函数的标准框架之外构造出可证明良好的近似策略。我们还证明，对我们的方法稍加修改，即使在E[（ZT）]要比OPT大得多，并将这些结果应用于最佳停止ping文献中感兴趣的几个问题-i.i.d.设置和Robbins问题。最后，我们提供了几个额外的示例，说明我们的方法在某些情况下可以更快地收敛。4.1. 定理2的证明在这一节中，我们证明了c收敛结果的主要速率定理2。首先，我们证明了一个更强大的路径收敛结果，本质上，在扩展的r k次迭代之后，每个样本路径的最小值为mostk+1。这是一个比OREM 2中给出的更有力的陈述，OREM 2中只考虑预期。

我们首先介绍以下stro ng convergenceresult，它的pro of出人意料地简单。引理8。假设w.p.1 Zt∈ [0，U]对于所有t∈ [1，T]。那么对于所有k≥ 1，w.p。1薄荷∈[1，T]Zkt≤英国。Chen和Goldberg：战胜期权定价和最优止损中的维度诅咒证明：请注意，通过定义、可测量性和引理1，对于所有k≥ 1，Zk+1T=ZT-Pki=1mint∈[1，T]青春痘≥ 0 w.p.1。根据引理1保证的单调性，可以得出w.p.1，k×mint∈[1，T]Zkt≤ ZT公司≤ U、 接下来是期望的结果。Q、 定理2的E.D.证明：用引理1，OPT=Pki=1E[mint∈[1，T]Zit]+infτ∈TE【Zk+1τ】。让tingτk+1停止第一次Zk+1t的停止时间≤k+1（如果不存在这样的时间，则在时间T处停止），引理8意味着E[Zk+1τk+1]≤k+1。因此infτ∈TE[Zk+1τ]≤k+1，并结合上述内容完成证明。Q、 E.D.4.2。prophet不等式的交替边界和定理3的证明在最优停止中，一些最著名的结果涉及所谓的p-rophet不等式，与infτ相关∈TE[Zτ]至E[铸币厂∈[1，T]Zt]在Z上的各种假设下，包括有界性、独立性等，我们不打算在这里调查关于此类不平等的大量文献，而是让读者参考Hill和Kertz（1992）的经典调查，以及Lucier（2017）的更近的调查（更具经济学导向的视角）。

我们注意到，文献中的许多结果仅在独立性假设下成立，这将不适合我们的目的，就像{Zt，t∈ [1，T]}是i.i.d.，{Zt，T∈ [1，T]}一般不会这样。然而，也有一些显著的例外，包括Hill和Ke rtz（1983）的以下结果。虽然最初是以最大化的形式陈述的，但我们在此陈述了相应的版本形式化，这很容易从Hill和Kertz（19 83）的原始结果中得到，我们省略了细节。回想一下，对于x∈ [0，1]，h（x）=（1- x） 日志（1-x） ；对于k≥ 2和x∈ [0，1]，hk（x）=h香港-1（x）.引理9（有界序列的Prophet不等式（Hill and Kertz（1983）））。假设PZt公司∈ [0, 1]= 1 f或所有t∈ [1，T]。然后选择- E[铸币厂∈[1，T]Zt]≤ h（可选）。4.2.1. 定理3的证明。定理3的证明：我们首先说明了H的一些基本性质，这些性质很容易通过简单的微积分参数验证，我们省略了细节。第一，h（x）∈ [0，1]对于所有x∈ [0, 1].第二，h（x）≤ x代表所有x∈ [0，1]，然后是一个直接的归纳论证，对于每个固定的x∈ [0，1]，{hk（x），k≥ 1} 是单调递减的。第三，他严格递增[0，1- 经验值(- 1)]. 第四，h（x）≤ 经验值(-1） 对于所有x∈ [0, 1].接下来，我们证明，对于所有k≥ 1，可选- 埃克≤ 香港（OPT），并通过入职培训进行。因为引理1意味着OPT=Ek+infτ∈对于所有k，TE【Zk+1τ】≥ 1，对于所有k，所需结果等效于提供≥ 1，infτ∈TE[Zk+1τ]≤ 香港选择. 基本情况k=1紧跟引理1和引理9。现在，让我们从归纳法开始。假设理想的陈述是trueChen和Goldberg：击败期权定价中的维度诅咒和s ome k的最优停止≥ 1.

然后从定义，可选停止，引理9，infτ∈TE[Zk+2τ]等式infτ∈TE公司Zk+1τ- E[铸币厂∈[1，T]Zk+1t | Fτ], 自身等于infτ∈TE[Zk+1τ]- E[铸币厂∈[1，T]Zk+1t]≤ h类infτ∈TE[Zk+1τ].根据我们的归纳假设，infτ∈TE[Zk+1τ]≤ 香港选择. 正如我们已经表明的那样，香港选择≤ h类选择≤ 经验值(-1) < 1 - 经验值(-1） ，his在[0，1]上增加- 经验值(- 1） ]之后infτ∈TE[Zk+1τ]≤ h类香港选择= 香港+1（可选）。结合以上完成归纳，再结合一些直代数完成定理的证明。Q、 E.D.我们注意到，不幸的是，它可以证明hk（x）不在一般情况下（即，如果一个人在所有x中采取最坏的情况∈ [0，1]）得到一个比T heorem 2更好的界作为k→ ∞. 然而，它可能会对OPT的特定值产生强边界。例如，如果OPT接近1，那么定理3意味着我们的方法即使在一个单一的ite比率之后也有很小的误差。更一般地，引理9也可以用来证明两个OPT- ek以及在我们展开的第k次迭代过程中取得了多少进展，例如，通过使用以下事实（源自astraightforward Taylor展开），h（x）~ x个-xas x↓ 0，尽管我们在这里不进行这种分析。4.3. 交替界限当Z是无界的并且证明定理4时，我们现在完成定理4的证明，它提供了一个关于收敛速度的界限，这是完全通用的，即不需要归一化，也不需要通过任何上界重新调整绝对误差，甚至不需要存在任何上界。定理4的证明：首先，我们声明对于所有k≥ 1，E[铸币厂∈[1，T]Zkt]≤k×选项。（6） 事实上，这完全遵循了单调性和引理1，这也意味着（通过一些简单的代数）为了证明整个定理，必须证明infτ∈TE[Zk+1τ]≤ 2 ×OPT×E[（ZT）]×k。

（7） 要继续，让我们考虑以下thr eshold策略的性能。让xk=E[（ZT）]×OPT×k-1.. 考虑第一次停止Zk+1t的政策≤ xk，如果[1，T]中不存在这样的T，则简单地停止时间T。通过τk计算该停车时间，注意w.p.1 Zk+1τk≤xk+I造币厂∈[1，T]Zk+1t>xkZk+1T，通过单调性（意味着Zk+1T≤ ZTw。p、 1）在mostChen和Goldberg：击败期权定价和最优止损中的维度诅咒XK+I造币厂∈[1，T]Zk+1t>xkZT。考虑到期望值和适用的Cauchy-Schwarz，我们发现[Zk+1τk]最多为xk+E[（ZT）]×P造币厂∈[1，T]Zk+1t>xk. 进一步应用Markov\'sinequality和（6），我们得出E[Zk+1τk]最多为xk的结论+OPT×k-1×E[（ZT）]xk= 2xk，完成验证。Q、 E.D.4.4。i.i.d.设置和Robbins问题的备用边界在某些情况下，可能需要不仅保证绝对误差，而且保证相对误差或。也就是说，一个人可能会在几个回合后出错，这个错误最多只是OPT本身的一个小错误。Theo rem 4产生这样的结果，只要E[（ZT）]比OPT大不了多少倍。然而，文献中深入研究的许多特定理论停止问题，例如Z是[0,1]上均匀分布的i.i.d.（即U[0,1]）的设置，或标定的Robbins问题（B russ（2005）），都具有以下特征：当T较大时，E[（ZT）]比OPT大很多倍。在这种情况下，定理2-4的边界可能需要k非常大（用t缩放），才能获得较小的相对误差。我们现在表明，对我们的方法稍加修改即可克服这一问题。我们不认为，尽管我们怀疑我们的方法，未经改进，也能在此类问题的相对误差（未被我们证明的界限捕获）下取得良好的性能，但这是一个有趣的开放问题。

让Y={Yi，i≥ 1} 表示T的U[0,1]r.v.s.的i.i.d.序列≥ 1和T∈ [1，T]，let gUt（Y[T]）= Yt；和gRt（Y[t]）=Pti=1I（Yi≤ Yt）+（T- t） 年初至今。然后简单地验证了r.v.s的i.i.d.U[0,1]序列的最优停止问题等价于问题OPTU（T）= infτ∈TE公司gUτ（Y[τ]）. 我们注意到，由于这一问题是经典的al问题，其解决方案已被充分理解（Gilbert和Mosteller（1966），Kennedy和Kertz（1991）），例如，它被称为atlimT→∞T×OPTU（T）=2，在这种情况下，我们的结果仅说明了我们框架的适应性。同样可以证实（Bruss（2005））著名的Robbins问题等同于OPTR（t）问题= infτ∈TE公司gRτ（Y[τ]）. 然而，对于这个问题，我们知之甚少，而且我们对OPTR（T）的价值和（近似）最优政策的性质的理解仍然是近期大量研究中的公开问题（Bruss（2005），Den dievel et al.（2016），G nedin and Iksanov（2011），Meier et al.（2017））。例如，虽然已知Limt→∞OPTR（T）存在，e xact极限值仍然是一个未决问题。让罗宾斯的公共关系问题如此棘手的一个方面是，它表现出了完全的历史依赖性，即使是在有限的时间内→ ∞ （Bruss（2005））。当然，对于我们的方法来说，这种依赖性不是问题。我们的程序如下。请注意，由于zt可能比OPT大得多，因此如果一个人运气不好，那么它并不意味着在时间T停止∈[1，T]Zktwas大于预期。相反，我们使用的事实是，对于i.i.d。

停止U[0,1]r.v.s和Robbins问题，f或任何固定η∈ （0，1），如果T很大（对于固定η），则很像存在T∈ [(1 - η） T，T]suchChen和Goldberg：击败期权定价和最优止损中的维度诅咒，即Zt不会比OPT大太多（这里“太多”将是η的一些函数），而且一些止损时间（在这个区间上）几乎可以达到预期的效果。因此，我们继续采用修正的扩展，其中我们只取第一个（1）的最小值- η） T时间段，如果我们运气不好，留给我们足够的时间自我纠正。然后，通过取一个双极限来证明结果，其中η被设置为所需精度的适当函数，并应用了几个附加边界。我们注意到，我们对i.i.d.sett Ingan和Robbins问题的结果来自于我们在技术附录引理20中证明的更一般的界，这可能对其他此类Stop-in-g问题有用。更正式地说，让我们定义一个修改后的扩展，如下所示。对于η∈ （0，1）和t∈ [1，T]，letZη，T= Zt。对于k≥ 1, η ∈ （0，1），t∈ [1，T]，设Zk+1η，T= Zkη，t- E迷你∈[1,(1-η） T型]Zkη，i | Ft. 然后，相应的收敛结果如下所示。Let Hk（η）= E[最小1≤t型≤(1-η） T型Zkη，t]和Ek（η）=Pki=1Hi（η）。定理8。存在一个绝对的严格正有限常数C，与任何其他常数无关，对于所有t≥ 1和k≥ 1.OPTU（T）- 埃克（k+1）-≤ C×（k+1）-×OPTU（T）；和OPTR（T）- 埃克（k+1）-≤ C×（k+1）-×OPTR（T）。我们将定理8的证明推迟到技术附录中。定理m 8的一个重要方面是，展开式中获得良好相对误差所需的项数与时间ho rizon T无关。

我们相信，类似的方法可以应用于文献中的其他最优停止问题，并且可以证明更强的收敛速度，这是未来研究的有趣方向。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）如下。

Bk+1的定义，-（t，γ，，δ，U）与Bk+1（t，γ，，δ）几乎相同，唯一的区别是对Bk的调用j、 A[j]，，δ4N（，δ）T在算法定义的第6行被对Bk的调用所取代，-j、 A[j]，，δ4N（，δ）T，U; 算法定义第8行对Bk（t，γ，，δ）的调用通过对Bk的调用来替换，-（t，γ，，δ，U）。Chen和Goldberg：战胜期权定价中的维度诅咒和k的最优止损≥ 1、我们定义了^Bk，-（，δ，U）如下。^Bk的定义，-（，δ，U）与Bk（，δ）几乎相同，唯一的区别是对Bk的调用j、 A[j]，，δ2N（，δ）T第6行的算法定义由ca ll替换为Bk，-j、 A[j]，，δ2N（，δ）T，U.然后我们有以下辅助算法结果，与定理6完全类似。定理10。仅假设Zt≥ 0表示所有t∈ [1，T]w.p.1，以下是正确的。对于所有k≥ 1，随机优化算法^Bk，-将任意、δ作为输入∈ （0，1）和U>0，并实现以下功能。在最多4（C+G+1）fk+1（，δ）的总计算时间中，如果对基本模拟器B调用最多fk+1（，δ）的随机性，则返回一个满足P的随机数X|十、- H-U、 k |≤ ≥ 1.- δ.证明：证明与定理6的证明基本相同，我们省略了细节。事实上，定理10源自定理6，该定理适用于交替最小化问题，其中使用交替g函数g′t=1- U-1×min（U，gt）。我们注意到，计算成本界中出现的额外乘法4（与定理6相比）来自计算1所需的额外计算- U-1×min（U，gt）。事实上，如果一个人在我们的计算模型下计算时间G，那么他可以计算1- U-1×min（U，gt）时间G+3≤ 4×G。

Q、 E.D.接下来，我们正式声明算法^A，ich将对Bk执行适当的操作和调用，-（使用适当的参数）以产生定理7中保证的近似。算法^A（，δ，M，M）：计算项目（M）并存储在γ计算中10×γ×-2×M存储在U中创建长度-（UM） i=1至（UM）生成指向^Bi的索引，-（UM）+1-2, δ ×（UM）+1-1，U并存放在AiReturn U×1.-P（UM）i=1Ai在定义了算法^A并掌握了定理9的情况下，定理7的证明与推论2的证明类似，尽管需要验证截断的适当性等额外的复杂性，我们将证明提交给技术附录。Chen和Goldberg：击败期权定价和最优止损中的维度诅咒5.4。推论3的证明在本节中，我们讨论如何使用基于仿真的方法来实现良好的近似停止策略，从而证明推论3。我们从以下引理开始，将单个停止策略在不同的停止问题上实现的价值联系起来（由Zk定义）。引理18。对于所有（可能随机的）整数值停止时间τ，适应于F whichw。p、 1属于[1，T]，所有k≥ 1，E【Zτ】=E【Zkτ】+Pk-1i=1E[铸币厂∈[1，T]青春痘]。证明：我们仅对非随机停止时间的情况进行证明，因为一般设置遵循直线条件论证。我们采用归纳法。基本情况k=1源自定义。现在，假设归纳法对某些k是真的≥ 1.然后根据定义和可选停止，E[Zk+1τ]=EZkτ- E[铸币厂∈[1，T]Zkt | Fτ]= E【Zkτ】- E[铸币厂∈[1，T]Zkt]，本身（通过归纳）等于E[Zτ]-Pki=1E[铸币厂∈[1，T]Zit]，它在重新排列后完成屋顶。Q、 结合引理18、引理8和定理1，我们得到以下推论。推论4。

对于k≥ 1，让τkdenote表示第一次停止Zkt的停止时间≤k、 我们注意到引理8中存在这样一个时间，即w.p.1。然后E[Zτk]- 选择≤k、 现在，如果不是因为我们不能在一个高效的管理器中计算zktex的fa ct，我们就可以完成了。然而，根据《纽约时报》第17期的报道，我们很清楚该如何应对。在每个时间段t中，我们将使用模拟来估计到目前为止观察到的给定历史Y[t]的Zkt（Y[t]）（对于适当的k），并以足够的精度和足够高的概率来这样做，以确保所有边界都通过。现在让我们做一下准备。对于任何给定的>0，我们首先确定适当的（随机）停止时间τ。即τ定义如下。在时间1，在看到Y[1]之后，独立调用B4-1.1，Y[1]，，4T. 如果返回的值最多为，请停止。如果没有，请继续。我们归纳未来行为如下。假设对于某些t∈ [1，T- 2] ，我们还没有在时段t结束时结束。在时间t+1，在观察到Yt+1后，独立调用toB4-1.t+1，Y[t+1]，，4T. 如果重新返回的值最多为，则停止。如果没有，请继续。最后，如果我们还没有在周期T前停止，那么就在周期T内停止。很容易验证，对于任何∈ （0，1），τ是一个定义良好、适当适应、随机最小化的停止时间。现在我们用τ来完成推论3的覆盖。Coro llary 3证明：Let k= . 让G1，表示事件(B4-1.t、 Y[t]，，4T- Zkt（Y[t]）≤ t型∈ [1，T]）；Chen和Goldberg：击败期权定价和最优止损中的维度诅咒2，表示事件( t型∈ [1，T]这样B4-1.t、 Y[t]，，4T≤);G3，表示eve ntZkτ≤. 观察引理8、引理17、定义和se veralstraightforward并集边界以及三角形不等式的应用，可以确保：1。P（G1，）≥1.-; 2、P（G2，| G1，）=1；和3。

P（G3，| G1，TG2，）=1。因此P一般条款3，≤因此，由我们的假设和单调性P（Zkt）确定≤ 1） =1表示所有t∈ [1，T]，EZkτ= EZkτI（G3，）+ EZkτI（Gc3，）≤+EI（一般条款3，）≤ .结合引理18、引理8和定理1，完成了对第一部分定理的证明。第二部分直接来自引理17。Q、 E.D.6。结论在这项工作中，我们开发了一种新的纯对偶方法，用于解决高维全路径依赖的最优停止和期权定价的基本问题。与文献中大多数过去的方法相比，我们的（数据驱动）算法允许人们在所需的近似水平和相关条件预期中的运行时/样本复杂性/测试水平之间进行优雅的权衡。事实上，我们对结果的一个关键见解是，即使存在全路径依赖性和高维性，对于任何给定的错误参数，我们也可以在T中获得时间多项式中的-ap近似，并且仅通过模拟单个样本路径的成本来取决于维度（更一般地说是状态空间），其中只需要多项式数量的此类模拟。我们的方法还揭示了与网络流的新联系以及文献中的其他结果。我们的工作为未来的研究留下了许多有趣的方向。对真实数据和金融实例的实施和测试。此时，我们的结果和分析证明了在精度和计算/样本复杂性之间进行权衡在理论上是可能的。在真实数据和实例上测试该方法，了解如何将我们的方法与其他启发式方法相结合（例如。

从ADPand simulation）提高速度和准确性，并与过去的应用程序进行严格比较，这对于从概念验证阶段转变为期权定价的有用工具来说当然至关重要。此外，研究实用智能的新设置将是一件有趣的事情，因为数据、机器学习和更复杂的模型的使用越来越多，这可能会激发我们的灵感。Schen和Goldberg：战胜期权定价和最优止损中的维度诅咒，我们的方法可以提供高效的算法。更好地理解收敛性的理论。在不同的环境中，我们提供了方法收敛速度的几个界限。我们怀疑，在许多情况下，我们的分析会很松散，仅使用相关系列的几个术语就可以得到相当准确的结果。无论是在期权定价的一般设置中，还是在诸如Robbins问题等更结构化的最优停止问题中，理解这一现象都是有趣的。我们还注意到，如果有人怀疑在任何特定情况下，扩展的收敛速度比我们的理论结果所认为的要快，那么可以通过简单地显示E[Zk+1τ]很小的终止时间τf来确定上限，并且将这种过程形式化也可能值得考虑。使用高级仿真技术进行更好的算法和分析。似乎通过将我们的方法与更复杂的工具和模拟分析相结合，可以得出更快的算法和更严格的界限。例如，我们没有尽力优化样本的使用，更好地理解如何在嵌套模拟的不同“级别”之间分配样本，和/或如何更智能地重用和重新组合样本，可能会导致显著的加速。

应用多层蒙特卡罗技术也是如此。此外，我们怀疑，从重要性抽样和更普遍的度量变化中获得的技术在这里可能非常有用，例如，我们在第4节中对几个2周期问题的研究表明，算法减慢的原因可能是零和/或非常小的值的存在（这会导致一个进程变慢），而避免这种路径的偏差/条件化可能会使进步更快。与其他双重配方进行深入比较。我们的方法产生快速近似的能力似乎与我们的ap方法不具有确定的最优性（Schoenmakers et al.（2013）），这是大多数以前的方法所共有的特性（尽管不是所谓的乘法对偶）有关。更好地理解我们的方法在概念上和技术/计算上如何与过去的双重方法相关联，仍然是一个有趣的开放问题。广义地推广到随机控制。我们相信，我们的方法可以扩展到一系列广泛的随机控制问题。这里的第一步是扩展到多重终止，这几乎直接来自我们当前的分析，根据多重终止和最优终止之间众所周知的（递归）关系（Bender et al.Chen和Goldberg:在期权定价和最优终止中击败维度诅咒（2015））。事实上，最近在理解这种多重停止问题的贝叶斯后悔方面取得了很多进展（Arlotto和Gurvich（2017），Bumpensanti和Wang（2018），Vera和Banerjee（2018）），与我们自己的工作联系仍然是未来研究的一个有趣方向。

当然，还有一个更广泛的问题，即我们的方法可以扩展到一般的随机控制问题，同时保持可跟踪性的相关概念。使用与Bender et al.（2015）类似的减少，似乎很少采取行动的控制问题，其中不能多次改变行动（在适当意义上）可能是一个很好的起点。有趣的是，我们注意到，在相当普遍的意义上，suchan方法能够适应未来成本分布可能取决于个人过去行动的环境。此外，还需要研究一些方法，这些方法不只是试图导出嵌套的停止问题，例如，在多重停止框架中，可以尝试直接实现一个扩展（类似于此处为最佳停止而实现的扩展），其项直接对应于一个多重停止问题。还有几个技术方向可以扩展，例如连续时间和相关随机过程的设置、有限水平问题等。下限、随机化和计算复杂性。一组有趣的问题围绕着证明所研究问题的计算复杂性和样本复杂性的下界展开，例如依赖于时间的最优停止。最近有很多有趣的工作在随机控制和马尔可夫决策过程的设置中阐述了计算复杂性理论（具有积极和消极的结果）（Halman et a l.（2014，2015），Chen和Wang（2017），Sidford et al.（2018），Halman（2017））和pricingof complex fi financial products（Bertsimas et al.（2002），Van Roy（2010），Arora et al.（2011），Braverman等人（2014年））。

更好地理解我们的方法和方法之间的联系仍然是未来研究的一个有趣方向。这里的一个关键问题围绕着随机化和不同近似概念的使用，以及计算复杂性和样本复杂性之间的相互作用等问题。网络流量理论中其他工具的应用。正如我们的引理6所示，一般最优停止可能被表示为树网络上的大规模最大流量问题，这为利用网络流量理论（Ahuja et al.（201 4））上个世纪开发的庞大算法工具包打开了大门。此外，来自网络流理论的组合见解可能有助于确定我们的方法更快收敛的结构特性。或者，研究otherChen和Goldberg：击败期权定价中的维数诅咒和大规模图上的最优停止组合问题是否可以用我们的方法解决，这将是一件有趣的事情。交替展开和预处理。正如我们在第4节中看到的，以及我们对定理7的证明（以及在相关算法中实现的截断），对于一些问题，考虑修改我们的方法可能会有帮助。实际上，可以证明，在原则上，许多其他显式展开式也会收敛到最佳值，例如（对于c asethe P（Zt∈ [0，1]）=1表示所有t）定义Z′k+1t=Z′kt- E[QTi=1Z′ki | Ft]。也可以写下收敛性不太清楚的展开式，例如alte rnating符号的展开式，其收敛性仍然是未来研究的有趣方向。也可以通过定义Z′k+1t=Z′kt，将某些测量变化纳入膨胀本身- E迷你∈[1，T]Z′kiI迷你∈[1，T]Z′ki>|英尺.

另一方面，在加速已知算法方面相当成功的一种方法是从良好的初始近似开始。对于我们的方法，这相当于执行一个初始轮，其中一个用一个鞅M补偿Z（可能是由于问题特定的特征或使用其他一些算法/近似），一个怀疑很好地近似最优对偶鞅，然后用这个补偿过程作为基过程执行我们的表达式。新pro-phet不等式的公式。你的方法可能为新的预言不等式的公式化打开了大门（Hill和Kertz（1992）），因为它提供了一种表达最优停止问题价值的新方法。我们不认为，在某种意义上，在一个以上的任期后截断我们的扩张可以解释为一种“高阶”预言不平等，表达某种中间对手（即不称职但不需要按照适应的政策行事的人）可以获得的价值。应用于最佳停止、顺序假设测试和机器学习中的其他理论问题。我们的方法也可能有助于对最优停止文献中研究得很好的几个理论问题，如Robbins问题和多臂bandit问题中Gittins指数的计算，提供新的见解。在这里，我们的结果可能不仅作为计算工具有用，而且因为它们为最佳值提供了新的纯分析表达式，这可能会产生新的理论和结构见解。鲁棒最优停止的含义。我们的方法也可能有助于对所谓的鲁棒最优停止（Bayraktar et al。

（2014）、Nutz等人（2015）、Goldenshluger和Zeevi（2017）），因为我们的扩张是一般性的，不依赖于Chen和Goldberg：击败期权定价中的维度诅咒，并（从结构上）根据考虑的特定分布进行最优停止。应用于运营管理、定价和机制设计中的问题。最佳停止、prophet不等式和其他此类工具的另一个有用领域是运营管理、机制设计和定价问题领域（Blanchet al.（2016），Oh）。Arlotto和Gur vich（2017）、Bumpensanti和Wang（2018）、Vera和Banerjee（2018）、Abholhassani等人（2017）、C orrea等人（2017）、Luc ie r（2017））。将我们的结果推广到这种情况，并更广泛地将这篇文献与关于最优停止的对偶鞅方法的文献联系起来，仍然是未来研究的一个有趣方向。7、技术附件7.1。引理7的证明引理7的证明：首先，我们证明所有t的MARt=0∈ [1，3]w.p.1。事实上，我们有min1≤t型≤3Zt=最小1≤t型≤3Yt=Y=0 w.p.1。单调性和负性n然后yieldsmin1≤t型≤3Zkt=0 w.p.1。因此S=P∞k=1min 1≤t型≤3Zkt=0 w.p.1。因此，我们得出结论，定义为Doob鞅E[S | Ft]的MARt对于所有t必须等于零∈ [1，3]w.p.1的条件期望的基本性质。接下来，我们证明了唯一（0-均值）的确定最优双马丁酒M（0）=M（0，1）=0，M（0，1，1）=，M（0，1，）=-. 事实上，M（0）=M（0，1）=0直接源于Yand Yare const w.p.1这一事实，即mt适用于所有t∈ [1，3]，以及M上的0-平均假设。回想一下，对于i=2，确定的最佳特性需要造币厂∈[2,3]Zt公司- Mt+M= infτ∈T2,3E[Zτ| F]= 1，它（在简化和使用f-actthat Yand-Yare常数后）等于P最小值1，Z-M= infτ∈T2,3 E[Zτ]= 1.