最优多次停车的解析递推方法：Canadization

过程（exp（Φ（α）Xt-αt））t≥0是一个鞅（见[32]中的（3.11）），因此我们可以证明（如[32]证明的第一部分，定理3.12所示），即eΦ（α）Xt∧T+y-α（t∧T+y）= 1，t≥ 0。（2.17）此处，左侧的被积函数在t中以可积随机变量为界，即Φ（α）Xt∧T+y-α（t∧T+y）=e（Φ（α）-1） Xt公司∧T+yeX（α）T∧T+y≤ e（Φ（α）-1） Xt公司∧T+yeX（α）∞≤ e（Φ（α）-1） yeX（α）∞,（2.18）最优多重停止、CANADIZATION和相位型拟合7，其中最后一个不等式成立，因为Φ（α）>1和Xt∧T+y≤ y a.s.由于缺乏积极的跳跃。因此，在（2.17）中应用支配收敛，给定1=EeΦ（α）XT+y-αT+y{T+y<∞}= eΦ（α）叶河-αT+y{T+y<∞}i、 （2.19）在{T+y<∞}. 这就完成了证明。由于引理2.1和过程X必然向上爬行，因此XT+a=aon{T+a<∞} 带x的PX下≤ a、 我们可以写ev（n）a（x）=（e-Φ（α）（a）-x） φ（n）（a），x<a，φ（n）（x），x≥ a、 （2.20）备注2.1。可以看出，阈值水平从下方以log K为界，并且随着剩余停车机会的减少而增加，即log K<a*N≤ ··· ≤ 一*. 文献[41]表明，当折射时间δ被推广为独立的、同分布的随机变量时，这种单调性也成立，前提是它们独立于X，并且Xδ允许密度。它们还表明存在一个极限a*∞:= 画→∞一*N≥ 日志K.3。递归分析公式如前一节所述，最优策略的表征大大简化了问题。然而，在实践中，由于（2.12）中Xδ的分布通常未知，因此无法解析地获得该解。

因此，最大的障碍是计算expectationExe-αδv（n-1） （Xδ）, 2.≤ n≤ N、 （3.1）为了避免这种差异，我们采用了Carr[14]的Canadizing技术和近似（3.1），用一些独立的Erlang随机变量η（M，λ）替换常数δ，或用参数λ替换M个独立、相同分布的指数随机变量的等效和。在此，我们设置λ=λ（M）：=M/δ。（3.2）那么，η（M，λ）≈ 用强大数定律计算大M的δ。换言之，我们解决了最优多次停止问题的随机化版本，以近似折射时间恒定的问题。对于具有随机折射时间的最优停止问题，需要修改滤波；具体构造见【16】。然而，如【16，41】所述，该技术细节不会影响最佳停车策略的最终阈值结构。在这一节中，我们将展示具有随机折射时间的值函数可以通过用尺度函数编写的预解测度来获得。8 T.LEUNG、K.YAMAZAKI和H.ZHANG3.1。第一步。我们首先构建基本案例。鉴于n=1的（2.20），因为φ（1）≡ φ、 a的价值*通过（2.14）分析得出。

一阶条件为0=φ′（a）- Φ（α）φ（a），（3.3），允许a给出的唯一解*= 对数Φ（α）KΦ（α）- 1.（3.4）很容易检查这是否等同于平滑条件v（1）′（a*+) = v（1）′（a）*-).现在我们从atu（1,0）（x）开始：=v（1）（x）=（φ（x），x≥ 一*,φ（a*)e-Φ（α）（a）*-x） ，x<a*,（3.5）并导出expectationEx的分析表达式e-αη（M，λ）v（1）（Xη（M，λ））（3.6）作为n=2时（3.1）的近似值。最初的任务是计算指数时间范围的情况，u（1,1）（x）：=Exe-αη（1，λ）v（1）（Xη（1，λ））= λZ∞e-（λ+α）tExv（1）（Xt）dt=Mxu（1,0），（3.7），其中，对于任何可测f，我们定义（无论何时存在）Mxf：=λZRΘ（λ+α）（x，dy）f（y）（3.8），对于预解测度Θ（q）（x，dy）：=Z∞e-qtPx{Xt∈ dy}dt，y∈ R和q>0。（3.9）已知在光谱负L'evy过程的情况下，该预解测度允许密度，并且可以用所谓的标度函数来表示。修复q≥ 0，（q-）标度函数，W（q）：R→ [0, ∞),（3.10）为零(-∞, 0），在[0，∞), 其特征是Laplacetransform:Z∞e-sxW（q）（x）dx=ψ（s）- q、 s>Φ（q），（3.11），其中（3.12）Φ（q）：=sup{λ≥ 0：ψ（λ）=q}。最佳多重停止、canadizing和相位型拟合9根据[32]的推论8.9，预解测度Θ（q）（x，dy）具有密度θ（q）（y- x） 关于Lebesgue测度，其中θ（q）（z）：=Φ′（q）e-Φ（q）z- W（q）(-z） ，z∈ R、 （3.13）因此，在λ+α>0的条件下，可以使用比例函数重写（3.7）。这种操作可以通过进一步添加更多独立、相同分布的指数随机时间范围来重复应用。事实上，对于任何2个≤ m级≤ M和x∈ R、 （3.14）u（1，m）（x）：=Exe-αη（m，λ）v（1）（Xη（m，λ））= λZ∞e-（λ+α）tEx[u（1，m-1） （Xt）]dt=Mxu（1，m-1） =···=Mmxu（1,0）。3.2. 多个步骤。

现在（3.1）由u（1，M）（x）近似，我们可以近似φ（2）（x），如（2.13）中的φ（2）（x）：=φ（x）+u（1，M）（x）。（3.15）使用此近似，我们可以获得*, 说ea*, 按一阶条件0=eφ（2）′（a）-Φ（α）eφ（2）（a），并获得v（2）：u（2,0）（x）的近似值≡ ev（2）（x）：=（eφ（2）（x），x≥ ea公司*,eφ（2）（ea）*)e-Φ（α）（ea*-x） ，x<ea*.（3.16）与第一步类似，对于任何1≤ m级≤ M、 u（2，M）（x）：=Exe-αη（m，λ）ev（2）（Xη（m，λ））= Mxu（2，m-1） =···=Mmxu（2,0），（3.17），它给出了n=3时（3.1）的近似值。继续以这种方式，我们可以导出由φ（n）（x）：=φ（x）+u（n）定义的近似值-1，M）（x），（3.18）个*n∈ arg{a∈ R:eφ（n）′（a）- Φ（α）eφ（n）（a）=0}，（3.19）u（n，0）（x）≡ ev（n）（x）：=（eφ（n）（x），x≥ ea公司*n、 eφ（n）（ea*n） e类-Φ（α）（ea*n-x） ，x<ea*n、 （3.20）u（n，m）（x）：=Exe-αη（m，λ）ev（n）（Xη（m，λ））= Mmxu（n，0），1≤ m级≤ M、 （3.21）最后，ev（N）（x）是多重停车问题的理想近似值。在本文的其余部分，我们让ea*:= 一*为了便于标记。10 T.LEUNG、K.YAMAZAKI和H.ZHANG4。光谱负相位型酪蛋白为了执行前一节中描述的算法，重要的是可以分析地完成后向电导。也就是说，在应用（3.8）中的运算符M之后，必须保留闭式表达式。在本节中，我们将表明，如果我们关注以下形式（4.1）的相位类型L'evy过程，这是可能的。从[2]的命题1可知，对于任何光谱负L'evy过程X，存在一系列光谱负相型L'evy过程X（n），在空间D[0]中收敛到X，∞)具有左极限的实值右连续函数（c\'adl\'ag）；这意味着X（n）→ Xin分布（见【2】中的备注1和【27】中的推论VII 3.6）。

由此，我们自然地推测X的溶剂可以近似为相型L’evy过程的溶剂。事实上，Egami和Yamazaki【22】在数值上表明，至少当L'evy测度为有限时，一般光谱负L'evy过程的标度函数可以近似。对于满足Asmussen和Rosi'nski[5]条件的有限L'evy测度的情况，Asmussen等人[3]表明，布朗运动可以用作近似频繁微小跳跃的代理（其中他们认为L'evy测度具有完全单调的密度）。在下一节中，我们将通过数值实验分析近似误差。在本节中，设X为光谱负相位型L'evy过程，（4.1）Xt- X=ect+σBt-NtXn=1Zn，0≤ t<∞,对于某些ec∈ R和σ≥ 0。这里B=（Bt）t≥0是标准布朗运动，N=（Nt）t≥0是到达率ρ的泊松过程，Z=（Zn）n=1,2，。。。是一个具有表示（d，α，T）的相型分布随机变量的独立同分布序列。假设这些过程相互独立。回想一下，（0，∞) 如果是由一个吸收状态和D组成的有限状态连续时间马尔可夫链中的吸收时间分布，则为相位型∈ N瞬态。因此，任何相位类型的分布都可以用d、所有瞬态T上的d×d传递强度矩阵和马尔可夫链α的初始分布来表示。设t为d瞬态到吸收态的跃迁概率。

拉普拉斯指数（2.1）为ψ（s）=ecs+σs+ρα（sI- T）-1吨- 1.,（4.2）可扩展到s∈ C，T的特征值的负值除外。对于其余部分，让我们定义：=α+λ=α+M/δ，（4.3），我们假设这是严格正的。最佳多次停车、CANADIZATION和相位型拟合11假设{-ξi，p；我∈ Ip}是具有负实部的等式ψ（s）=p的根的集合。如【30】第5.4节所述，并已在【22】中得到数值证实（另请参见本文第5节中的数值结果），Iphas中的任何根都不太可能大于1。因此，我们可以假设Ipare中的根是不同的。因此，标度函数可以写为w（p）（x）=（Φ′（p）eΦ（p）x-圆周率∈Ipκi，pe-ξi，px，x≥ 0,0，x<0，（4.4），其中κi，p：=s+ξi，pp-ψ（s）s=-ξi，p=-ψ′(-ξi，p）；（4.5）见【22】。这里{ξi，p；i∈ Ip}和{κi，p；i∈ Ip}可能是复数。因此预解密度（3.13）写为θ（p）（z）=（Φ′（p）e-Φ（p）z，z>0，Pi∈Ipκi，peξi，pz，z≤ 0。（4.6）我们在这里的目标是显示每个n的函数u（n，m）≥ 1和0≤ m级≤ M（如前一节中所述递归派生）是一个具有子域（ea）的分段函数*l、 ea公司*l-1)1≤l≤n+1（关于ea的单调性，参见remark2.1*n） 其中，为了便于标注，我们定义了ea*:= ∞和ea*n+1：=-∞. 更具体地说，我们将证明，在每个子域上，它是多项式和指数的乘积之和：u（n，m）（x）=f（n，m，l）（x）（4.7），对于ea*l<x<ea*l-其中，我们定义（n，m，l）（y）：=A（n，m，l）+B（n，m，l）ey+Xi∈IpIn，mXh=0（C（n，m，l）i，he-ξi，pyyh）+In，mXh=0（D（n，m，l）heΦ（p）yyh）+E（n，m，l）EΦ（α）y，1≤ l≤ n+1，y∈ R、 （4.8）In，m：=（n-1） M+M- 1.

这里参数集Γn，m：=（A（n，m，l），B（n，m，l），{C（n，m，l）i，h，i∈ Ip，0≤ h类≤ In，m}，{D（n，m，l）h，0≤ h类≤ In，m}，E（n，m，l））1≤l≤n+1，（4.9）满意度（n，m，1）=E（n，m，1）=0，A（n，m，n+1）=B（n，m，n+1）=C（n，m，n+1）=0。（4.10）12 T.LEUNG、K.YAMAZAKI和H.Zhang其证明和参数集Γn，mca的推导可以归纳完成。沿着与上一节中的论点相同的直线，我们进行反向归纳。首先，基本情况（n=1和m=0）很简单，因为在（3.5）中，函数u（1,0）可以通过设置a（1,0,1）=写入（4.7）-K、 B（1,0,1）=1，E（1,0,2）=φ（ea*) 经验值(-Φ（α）ea*) In，m=-1、根据上一节的讨论，归纳步骤有两种类型。firstkind通过对预解测度应用积分来增加阶跃计数器n，而第二类则增加m。我们将前一步称为第一步，后一步称为第二步。4.1. 归纳步骤I.我们证明如果假设n成立≥ 1和m=m，则它也适用于某些n+1和m=0。

根据该假设，方程式（3.18）和（4.7）给出了ea*l<x<ea*l-1，（4.11）eφ（n+1）（x）=（A（n，M，l）- K） +（B（n，M，l）+1）ex+Xi∈IpIn，MXh=0（C（n，M，l）i，he-ξi，pxxh）+In，MXh=0（D（n，M，l）heΦ（p）xxh）+E（n，M，l）EΦ（α）x和（4.12）EΦ（n+1）′（x）=（B（n，M，l）+1）ex+Xi∈IpIn，MXh=0C（n，M，l）i，h(-ξi，pe-ξi，pxxh+he-ξi，pxxh-1） +英寸，MXh=0D（n，M，l）h（Φ（p）eΦ（p）xxh+heΦ（p）xxh-1） +Φ（α）E（n，M，l）EΦ（α）x。通过（3.19），我们可以确定最佳阈值ea*n+1。现在，根据（3.20），可以通过设置e（n+1,0，n+2）=eφ（n+1）（ea）获得u（n+1,0）的表示*n+1）e-Φ（α）ea*n+1，（4.13）和A（n+1,0，n+2）=B（n+1,0，n+2）=C（n+1,0，n+2）=D（n+1,0，n+2）=0，对于1≤ l≤ n+1A（n+1,0，l）=A（n，M，l）- K、 B（n+1,0，l）=B（n，M，l）+1（4.14）和C（n+1,0，l）=C（n，M，l），D（n+1,0，l）=D（n，M，l），E（n+1,0，l）=E（n，M，l）。（4.15）可以证实，因为通过假设，D（n，M，1）=E（n，M，1）=0，我们得到D（n+1,0,1）=E（n+1,0,1）=0。最佳多次停车、加拿大化和相位型拟合134.2。感应步骤II。

现在足以证明，对于固定的n≥ 1和0≤ m级≤ M- 1，m的假设意味着m+1。对于每x∈ R、 与1≤ L（=Lx）≤ n+1应确保ea*L<x<ea*L-1，Mxu（n，m）λ=1{L≥2} X1≤l≤L-1Zea公司*l-1ea*lΦ′（p）eΦ（p）（x）-y） f（n，m，l）（y）dy+Zea*L-1xΦ′（p）eΦ（p）（x-y） f（n，m，L）（y）dy+Zxea*经典版∈Ipκi，pe-ξi，p（x-y）f（n，m，L）（y）dy+1{L≤n} XL+1≤l≤n+1Zea*l-1ea*lXi公司∈Ipκi，pe-ξi，p（x-y）f（n，m，l）（y）dy=1{l≥2} eΦ（p）xΦ′（p）X1≤l≤L-1.（n，m）l（ea*l、 ea公司*l-1，Φ（p））+eΦ（p）xΦ′（p）（n，m）L（x，ea*L-1，Φ（p））+Xi∈Ipe公司-ξi，pxκi，p（n，m）L（ea*五十、 x，-ξi，p）+1{L≤n} Xi∈Ipe公司-ξi，pxκi，pXL+1≤l≤n+1（n，m）l（ea*l、 ea公司*l-1.-ξi，p），（4.16）式中（n，m）l（s，t，q）：=Ztse-qyf（n，m，l）（y）dy，s<t.（4.17），特别是对于x>ea*（或L=1），Mxu（n，m）λ=eΦ（p）xΦ′（p）（n，m）（x，∞, Φ（p））+Xi∈Ipe公司-ξi，pxκi，p（n，m）（ea）*, x，-ξi，p）+Xi∈Ipe公司-ξi，pxκi，pX2≤l≤n+1（n，m）l（ea*l、 ea公司*l-1.-ξi，p），（4.18），而对于x<ea*n（或L=n+1），Mxu（n，m）λ=eΦ（p）xΦ′（p）X1≤l≤n（n，m）l（ea*l、 ea公司*l-1，Φ（p））+eΦ（p）xΦ′（p）（n，m）n+1（x，ea*n、 Φ（p））+Xi∈Ipe公司-ξi，pxκi，p（n，m）n+1(-∞, x，-ξi，p）。（4.19）通过重复应用分部积分，可以将（4.16）的右侧写成（4.7）形式的闭合形式。由于计算简单但繁琐，我们将以下命题的证明以及递归公式（4.20）和参数集的详细表达式推迟到附录中。14 T.LEUNG、K.YAMAZAKI和H.Zhang提案4.1。修复n≥ 1和0≤ m级≤ M- 1并假设（4.7）、（4.9）和（4.10）保持不变。然后，L=lx是唯一的整数，因此*L<x<a*L-我们有（4.20）u（n，m+1）（x）λ=Mxu（n，m）λ=A（n，m+1，L）+B（n，m+1，L）ex+Xi∈IpIn，m+1Xh=0（C（n，m+1，L）i，he-ξi，pxxh）+In，m+1Xh=0（D（n，m+1，L）heΦ（p）xxh）+E（n，m+1，L）EΦ（α）x，对于某些参数集Γn，m+1：=A（n，m+1，l），B（n，m+1，l），{C（n，m+1，l）i，h，i∈ Ip，h≥ 0}，{D（n，m+1，l）h，h≥ 0}，E（n，m+1，l）1.≤l≤n+1（4.21），满足（4.10）。数值结果在本节中，我们对我们的方法进行了数值评估。

对于X，我们使用形式为（4.1）的谱负L'evy过程，并进行修改，以使（Zn）是以下随机变量的独立、同分布序列：情况1：参数为1的指数随机变量，情况2：参数为（2，1）的Weibull随机变量，情况3：均值为零且方差为1的高斯（折叠正态）的绝对值，其各自的密度为{-x} ，2倍exp-x个和√2πexp-x个, x个∈ (0, ∞).（5.1）情况1是相位型随机变量的特例，其标度函数可以按照（4.4）的形式精确计算。对于情况2和3，使用EM算法通过d=6的相位类型分布来近似它们：拟合的相位类型分布为=-5.6546 0.0000 0.0000 0.0000 0.0000 0.00000.6066 -5.6847 0.0000 0.0166 0.0089 5.05260.2156 4.3616 -5.6485 0.9162 0.1424 0.01265.6247 0.0000 0.0000 -5.6786 0.0000 0.00000.0107 0.0000 0.0000 5.7247 -5.7420 0.00000.0136 0.0000 0.0000 0.0024 5.7022 -5.7183, α =0.00000.00070.99610.00000.00010.0031,（5.2）最佳多次停车、CANADIZATION和相位型拟合15andT=-4.0488 0.0000 0.0000 0.0000 0.0000 0.00000.1320 -4.0012 0.0000 0.0455 3.7040 0.00440.2367 0.8595 -4.2831 0.1897 0.2918 2.37243.1532 0.0000 0.0000 -4.0229 0.0000 0.00000.2497 0.0000 0.0000 3.7024 -4.0124 0.00000.0434 2.1947 0.0938 0.1704 0.1217 -4.9612, α =0.00520.06590.74460.03980.00430.1403,（5.3）分别适用于情况2和3。对于此阶段类型设置，我们使用EMpht，它是用C编写的，并且是公开可用的。有关此方法的更多详细信息，请参阅[4]。在这里，我们选择d=6，因为正如【22】中所证实的，可以准确快速地进行拟合。当d中的精度趋于增加时，运行时间非线性增加；因此，不能选择任意大的d。