第03章 更新理论S

第三章更新理论（RenewalTheory)一、更新过程（arenewalprocess)概念1．定义定义设X1,X2,是非负独立同分布的（independentandidenticallydistributed）iidF，F(0)=P{Xn=0}1。令S0=0,,Sn=X1+X2++Xn,n=1,2,。N(t)=sup{n:Snt}，(3.1.1)，计数过程{N(t),t0}称为更新过程（arenewalprocess)。若将Xn解释为第n-1个事件与第n个事件之间的间隔时间，则第n个事件在时刻Sn发生。由于间隔iid，所以在各个事件发生时刻此过程在概率意义上重新开始，事件发生时刻即系统更新时刻，事件即更新。N(t)就是系统在[0,t]中更新次数SN(t)就是系统在[0,t]中最后一次更新的时刻。SN(t)tSN(t)+12．N(t)的有限性在有限时间内是否会有无限多次更新发生？0SN(t)X1S1X2X3SN(t)+1tS0S2以0[]()nEXxdFx记相继发生的两事件的间隔之均值，从假定Xn0与F(0)1，可得0。由强大数定律可知，以概率1，当n时11nniiSXnn，但因0，所以当n趋于无穷时Sn必将趋于无穷。于是只有有限多个n能使Sn小于或等于t，因此，由(3.1.1N(t)=sup{n:Snt})知N(t)必是有限的，所以N(t)=max{n:Snt}二、N(t)的分布(distributionofN(t))与更新函数（therenewalfunction)1．N(t)的分布到时刻t为止的更新次数大于或等于n当且仅当在t之前或在时刻t发生第n次更新，即()nNtnSt(3.2.1)P{N(t)=n}=P{{N(t)n}-{N(t)n+1}}=P{N(t)n}-P{N(t)n+1}=P{Snt}-P{Sn+1t}(3.2.2)既然随机变量Xi,i1．iidF，所以1nniiSX的分布Fn为F自身的n次卷积。因而，从(3.2.2)我们得到P{N(t)=n}=Fn(t)-Fn+1(t)，n=0,1,2,…2．更新函数（therenewalfunction)令m(t)=E[N(t)]，称m(t)为更新函数，更新理论的大部分内容涉及到确定m(t)性质。m(t)与F之间的关系由下列命题给出。命题(proposition)3.2.1m(t)=1()nnFt证明令1,[0,]0nntI若第次更新发生在内，其它，则N(t)=1nnI，因此m(t)=E[N(t)]=11111[][]{1}{}()nnnnnnnnnnEIEIPIPStFt由于In非负，求期望与求和顺序交换是合理的。X1S1X2X3tS0S2I1=1I2=1I3=1IN(t)=1IN(t)+1=0SN(t)SN(t)+1命题3.2.2对一切0t,m(t)证明因P{Xn=0}1,由概率的连续性可知存在一个0，使得P{Xn}0(若对任意0，有P{Xn}＝0，则P{Xn=0}=1111{{}}lim{}1lim{}1nnnkkkPXPXPXkkk)。定义一个关联的更新过程：0,nXnn若X，若X，且令1()sup{:}nNtnXXt。对此过程更新只能在时刻t=n发生，n=0,1,2,,且在这些时刻的更新次数是独立的几何随机变量-1（例如在t=0点，当X1时10X，第一个事件在t=0发生，当X2时20X，第二个事件在t=0发生，，直到某个k有Xk时kX,第k个事件在t=发生,因此在t=0发生的事件个数服从参数为P{Xn}的几何分布-1）其均值为1{}nPX-1，于是1[()][1][/]{}nENttPX且因nnXX蕴含()()NtNt，所以()[()][()]()mtENtENtmt结论得证。023[]tt{[]1}t三、若干极限定理(somelimittheorems)1.平均更新速率（theaveragerenewalrate)（1）()lim()tNNt命题P{N()=}=1这是因为使所发生的更新总数N()为有限的唯一方法是有一个来到间隔为无穷大。所以P{N()}=P{Xn=,对某个n}=P{1{}nnX}1{}0nnPX,于是当t趋于无穷时N(t)趋于无穷。（2）SN(t)的意义N(t)=max{n:Snt}SN(t)表示在时刻t之前或在时刻t最后一次更新的时刻。SN(t)+1表示时刻t之后第一次更新的时刻(见下图)。0SN(t)X1S1X2X3SN(t)+1tS0S2（3）平均更新速率()limtNtt命题3.3.1以概率1，当t时()1Ntt证明因SN(t)tSN(t)+1，可见(3.3.1)()()1()()()NtNtSStNtNtNt然而．因SN(t)/N(t)是前N(t)个来到间隔的平均值，由强大数定律得出，当N(t)时SN(t)/N(t)。但由于t时N(t)，所以t时SN(t)/N(t)由SN(t)+1/N(t)=()1()1()11[1]()1()()1()NtNtSSNtNtNtNtNt得t时SN(t)+1/N(t)因为t/N(t)介于两变量之间，它们在t时都收敛于。命题3.3.1说以概率1，长时间后更新发生的速率将等于1/。为此称1/为更新过程的速率。0SN(t)X1S1X2X3SN(t)+1tS0S22．期望更新速率（theexpectedaveragerenewalrate)证明更新的平均速度的期望m(t)/t也收敛于1/要用停时与瓦尔德等式。（1）瓦尔德等式（Wald’sEquation)定义整值随机变量N称为独立随机变量序列X1,X2,的停时（astoppingtime)，若对一切n=1,2,，事件{N=n}与Xn+1,Xn+2,独立。直观上看，依次观察诸Xn，以N记在停止观察之前所观察的次数。若N=n，则在观察X1,X2,,Xn之后与观察Xn+1,Xn+2,之前停止观察。例3.3(a)设Xn,n=1,2,，相互独立且使得P{Xn=0}=P{Xn=1}=1/2,n=1,2,，如果我们令1min{:10}nNnXX，则N是一个停时。可以将N看作连续地抛掷一枚均匀硬币的试验的停时，试验在正面出现次数达到10次时停止。11110,10NNXXXX例3.3(b)设Xn,n=1,2,，相互独立且使得P{Xn=-1}=P{Xn=1}=1/2,n=1,2,，则N=min{n:X1+X2++Xn=1}是一个停时。它可以看作为—个赌徒的停时，他在每局赌博中等可能地赢得或输得一元，且决定一旦领先就停止。1111,0NNXXXX定理3.3.2(瓦尔德等式)若X1,X2,是独立同分布的随机变量，期望有限，且N是X1,X2,的停时，使得E[N]，则1[][][]NnnEXENEX证明令1,0,nNnINn,则,0,nnnXNnXINn，则1111NNnnnnnnnnnnNnXXIXIXI，因此(3.3.2)111[][][]NnnnnnnnnEXEXIEXI因为{In=0}={Nn}=11{}nkNk与Xn,Xn+1,Xn+2,独立，所以{0}nI={In=1}与Xn,Xn+1,Xn+2,独立。所以In与Xn独立。从(3.3.2)得11111[][][][][][][]{}[][]NnnnnnnnnnnnEXEXIEXEIEXEIEXPNnEXEN对于例3.3(a)来说，瓦尔德等式蕴含了E[X1+X2++XN]=1/2E[N]然而，由N的定义X1+X2++XN=10，从而E[N]=20。将瓦尔德等式的结论应用到例3.3(b)会有等式E[X1+X2++XN]=E[N]E[X]。然而X1+X2++XN=1及E[X]=0，从而得出矛盾。所以瓦尔德等式不可应用．这就得出结论E[N]=。(2)来到间隔时间的停时以X1,X2,记一更新过程的来到间隔，让我们在t之后的第一个更新即N(t)+1次更新时刻停止。为了证实N(t)+1是序列X1,X2,的停时，注意到N(t)+1=nN(t)=n-1X1+X2++Xn-1tX1+X2++Xn于是事件{N(t)+1=n}只依赖于X1,X2,,Xn，故与Xn+1,Xn+2,独立；因此N(t)+1=n是一个停时。从瓦尔德等式我们得到，当E[X]时E[X1+X2++XN(t)+1]=E[X]E[N(t)+1]系(corollary)3.3.3若，则(3.3.3)E[SN(t)+1]=[m(t)+1](3)基本更新定理(theelementaryrenewaltheorem)定理3.3.4(基本更新定理)当t时()1mtt(其中10)证明首先假设，现在有（见图3.3.1)tSN(t)+1，取期望并用系3.3.3得[m(t)+1]t，()11mttt，所以有（3.3.4）()1liminftmtt另一方面，固定一常数M，且定义一个新的更新过程{,1,2,}nXn如下：,nnXMXMMnn若X，若X,令1nniiSX及1()sup{:}nNtnXXt。由于这个截尾更新过程（truncatedrenewalprocess)的来到间隔时间以为M界，我们得到()1NtStM，因此由系3.3.3,[()1]MmttM，其中[]MnEX，于是()11MMmtMttt，而因nnSS，得()()NtNt及()()mtmt。于是(3.3.5)()1limsuptMmtt，令M得(3.3.6)()1limsuptmtt。从(3.3.4)及(3.3.6)得结论成立。系3.3.3若，则E[SN(t)+1]=[m(t)+1]0tt+M0S1X1S()NtS()1NtS当=，我们再考虑截尾过程；由于当M时M，从(3.3.5)知结论成立。0tt+M0S1X1S()NtS()1NtS()11MMmtMttt(4)N(t)渐近正态分布(N(t)isasymptotically,ast,normallydistributed)我们以证明t时N(t)为渐近正态分布来结束本节。为了证明这一结果，我们不仅使用中心极限定理(以证明Sn是渐近正态的)且要使用关系式(3.3.7)N(t)nSnt定理3.3.5设来到间隔的均值和方差2有限，则2/23()/1lim{}2/yxtNttPyedxt证明令3//trtyt，则/trtyt，/ttryt，1122/()(1)ttttttrryyyytrrt，3()/{}{()}{}/ttrNttPyPNtrPStt（由3.3.7但有一点问题：rt不一定是一个整数）={}trttttSrtrPrr=1/2{(1)}trttSryPyrt现在由中心极限定理，当t(于是rt)趋于时，()/trttSrr收敛于均值为0方差为1的正态随机变量。又因t时1/2(1)yyyt，可见2/23()/1{}2/xyNttPyedxt，又因22/2/21122yxxyedxedx，故结论成立注记(1)在上面的论证中