应用随机过程PPT课件.ppt

1、应用随机过程应用随机过程主讲教师主讲教师 段禅伦段禅伦20112011年秋季学期年秋季学期计算机学院研究生专业基础课程计算机学院研究生专业基础课程应用数学基础应用数学基础(Applied Stochastic processes)(Applied Stochastic processes)第第2 2章章 关于条件概率与条件期望关于条件概率与条件期望-有关有关概率模型概率模型(Probability ModelsProbability Models)的练习的练习引言引言 条件概率条件概率与与条件期望条件期望是概率论最有用的概念是概率论最有用的概念.因为因为:在实践中在实践中,我们常常对于计算在部

2、分信息已知时的概率我们常常对于计算在部分信息已知时的概率和期望感兴趣和期望感兴趣.而这样的概率和期望就是条件概率和条件而这样的概率和期望就是条件概率和条件期望期望;其次其次,在计算需要的概率和期望时在计算需要的概率和期望时,在某些随机变量上在某些随机变量上取条件是极其有用的方法取条件是极其有用的方法.离散情形离散情形 我们知道我们知道,对于任意两个事件对于任意两个事件E E和和F,F,当当P(F)P(F)0 0且给定且给定F F时时,E,E的条件概率被定义为的条件概率被定义为 P(E|F)=P(EF)/P(F).P(E|F)=P(EF)/P(F).因此因此,如果如果X X和和Y Y都是离散随机

3、变量都是离散随机变量,那么对于所有使那么对于所有使PY=yPY=y0 0的的y y值值,在在Y=yY=y给定的条件下给定的条件下,X,X的的条件概率分布列函数条件概率分布列函数定义为定义为 p pX|YX|Y(x|y(x|y)=PX=)=PX=x|Yx|Y=y=.=y=.而对于所有使而对于所有使PY=yPY=y0 0的的y y值值,在在Y=yY=y给定的条件下给定的条件下,X,X的的条件概率分布函数条件概率分布函数定义为定义为 F FX|YX|Y(x|y(x|y)=)=PXx|YPXx|Y=y=y=p pX|YX|Y(a|y(a|y).).在在Y=yY=y给定的条件下给定的条件下,X,X的的条

4、件期望条件期望定义为定义为 EX|Y=y=EX|Y=y=xPXxPX=x|Yx|Y=y=y=xpxpX|YX|Y(x|y(x|y).).若若X X与与Y Y独立独立,那么条件概率分布列函数、条件概率分布那么条件概率分布列函数、条件概率分布函数和条件期望都与无条件时一样函数和条件期望都与无条件时一样.因为因为,当当X X与与Y Y独立时独立时,p pX|YX|Y(x|y(x|y)=PX=)=PX=x|Yx|Y=y=PX=x.=y=PX=x.例例1 1 假设假设X X和和Y Y的联合概率分布列函数的联合概率分布列函数p(x,yp(x,y)给定为给定为 p(1,1)=0.5,p(1,2)=0.1,p

5、2,1)=0.1,p(2,2)=0.3.p(1,1)=0.5,p(1,2)=0.1,p(2,1)=0.1,p(2,2)=0.3.计算在计算在Y=1Y=1给定条件下给定条件下X X的条件概率分布列函数的条件概率分布列函数.解解:由由 p pY Y(1)=p(x,1)=p(1,1)+p(2,1)=0.6.(1)=p(x,1)=p(1,1)+p(2,1)=0.6.及及 p pX|YX|Y(1|1)=PX=1|Y=1=.(1|1)=PX=1|Y=1=.类似地类似地 p pX|YX|Y(2|1)=.(2|1)=.例例2 2 假定假定X X1 1和和X X2 2分别是具有参数分别是具有参数(n(n1 1

6、p),p)与与(n(n2 2,p),p)的独立的的独立的 二项随机变量二项随机变量,计算在计算在X X1 1+X X2 2=m=m给定的条件下给定的条件下X X1 1的条件概的条件概 率分布列函数率分布列函数.解解:记记q=1-p,q=1-p,由条件概率定义与独立性由条件概率定义与独立性,有有 PXPX1 1=k|X=k|X1 1+X+X2 2=m=m=.=.其中其中,运用了运用了X X1 1+X+X2 2=m=m是具有参数是具有参数(n(n1 1+n+n2 2,p),p)的二项随机的二项随机 变量变量(例例2.532.53)的已有结果的已有结果.进而知进而知在给定的在给定的X X1 1+X

7、X2 2=m=m的条件下的条件下,X,X1 1的条件概率分布列函数是的条件概率分布列函数是 =PX=PX1 1=k|X=k|X1 1+X+X2 2=m=.=m=.此式描述的分布此式描述的分布,称称超几何分布超几何分布,首见于首见于例例2.342.34.其模型其模型可解释为可解释为:从装有从装有n n1 1只蓝色球和只蓝色球和n n2 2只红色球的袋中只红色球的袋中,随机选取随机选取m m只只球球,求蓝色球个数的分布求蓝色球个数的分布.例例3 3 假定假定X X和和Y Y分别是具有参数分别是具有参数1 1与与2 2的独立泊松随机的独立泊松随机 变量变量.计算在给定计算在给定X+Y=nX+Y=n

8、的条件下的条件下X X的条件期望的条件期望.解解:我们计算在我们计算在X+Y=nX+Y=n给定的条件下给定的条件下X X的条件概率分布列的条件概率分布列 函数时函数时,注意到注意到例例2.362.36的结果和的结果和X X与与Y Y的独立性的独立性,有有 PX=PX=k|X+Yk|X+Y=n=n=.=.上式说明上式说明,在在给定给定两个独立的泊松随机变量两个独立的泊松随机变量X X与与Y Y的和的和X+X+Y=nY=n的条件下的条件下,X X的条件分布是的条件分布是参数为参数为n n和和1 1/(/(1 1+2 2)的的二项分布二项分布.由由例例2.532.53知知,X+Y=n,X+Y=n的条

9、件下的条件下X X的条件期望为的条件期望为 EX|X+Y=n=n .EX|X+Y=n=n .注注:条件期望具有普通期望的一切性质条件期望具有普通期望的一切性质,例如例如 E E X Xi i|Y|Y=y=y=EXEXi i|Y|Y=y.=y.例例4 4 一个试验一个试验,出现三个结果之一出现三个结果之一.结果结果i i出现的概率为出现的概率为 p pi i,i,i=1,2,3,p=1,2,3,p1 1+p+p2 2+p+p3 3=1.=1.假设独立地重复此试验假设独立地重复此试验n n次次,并并 以以X Xi i(i(i=1,2,3)=1,2,3)记其中结果记其中结果i i出现的次数出现的次数

10、求在给定求在给定X X2 2=m=m 时时X X1 1的条件期望的条件期望.解解:对于对于kn-mkn-m,PX PX1 1=k|X=k|X2 2=m=.=m=.显然显然,若若X X1 1=k=k且且X X2 2=m,=m,则则X X3 3=n-k-mn-k-m.且且 PXPX1 1=k,X=k,X2 2=m,X=m,X3 3=n-k-mn-k-m =,=,它是结果它是结果1 1有有k k次次,结果结果2 2有有m m次次,结果结果3 3有有n-k-mn-k-m次的次的n n次试次试验的所有这种序列事件发生的概率验的所有这种序列事件发生的概率.于是于是 PXPX1 1=k|X=k|X2 2=

11、m=.=m=.式中运用了式中运用了X X2 2是具有参数是具有参数n n和和p p2 2的二项分布的事实的二项分布的事实.进而进而,有有 PXPX1 1=k|X=k|X2 2=m=.=m=.记记p p3 3=1-p=1-p1 1-p-p2 2,则上式可等价地写为则上式可等价地写为 PXPX1 1=k|X=k|X2 2=m=.=m=.即在给定即在给定X X2 2=m=m时时X X1 1的条件分布是参数为的条件分布是参数为n-mn-m和和p p1 1/(1-p/(1-p2 2)的的二项分布二项分布.因而还有因而还有 EXEX1 1|X|X2 2=m=(=m=(n-mn-m).).为了易于理解为了易

12、于理解,对对例例4 4中所求的条件概率中所求的条件概率,我们也可以运我们也可以运用下述方式计算用下述方式计算:考虑不出现结果考虑不出现结果2 2的的n-mn-m次试验次试验.在每个这样的试验中在每个这样的试验中,结果结果1 1出现的概率是出现的概率是 PP结果结果1,1,非结果非结果22 P P非结果非结果22 =.=.由此就可得到在给定由此就可得到在给定X X2 2=m=m时时,结果结果1 1出现的次数是以参数出现的次数是以参数n-mn-m和和 二项地分布的二项地分布的.例例5 5 有有n n个部件个部件.对于对于i=1,2,i=1,2,n,n,部件部件i i在雨天运转的在雨天运转的 概率为

13、概率为p pi i;在非雨天运转的概率为在非雨天运转的概率为q qi i.明天将下雨的概明天将下雨的概PP结果结果1|1|非结果非结果2=2=率为率为.计算给定明天下雨时计算给定明天下雨时,运转的部件数的条件期运转的部件数的条件期 望望.解解:令令 X Xi i=若明天下雨若明天下雨,定义定义Y Y为为1;1;而在相反的情形而在相反的情形,定义定义Y Y为为0,0,则则 所求的条件期望为所求的条件期望为 E E X Xi i|Y|Y=1=1=EXEXi i|Y|Y=1=p=1=pi i.连续情形连续情形 如果如果X X和和Y Y有联合概率密度函数有联合概率密度函数f(x,yf(x,y),),那

14、么对于所有那么对于所有f fY Y(y(y)0 0的的y y值值,给定给定Y=yY=y时时X X的条件概率密度函数的条件概率密度函数定义为定义为 f fX|YX|Y(x|y(x|y)=.)=.1,1,部件部件i i明天运转明天运转;0,0,其他情形其他情形.X X的条件概率密度函数如此定义的理由的条件概率密度函数如此定义的理由:对定义式左边乘以对定义式左边乘以dxdx,右边乘以右边乘以(dxdy)/dydxdy)/dy,看出看出 f fX|YX|Y(x,y)dx(x,y)dx=PxXx+dx|yYy+dyPxXx+dx|yYy+dy 换句话说换句话说,对于小的值对于小的值dxdx和和dydy,

15、f fX|YX|Y(x,y)dx(x,y)dx近似地为给定近似地为给定Y Y在在y y和和y+dyy+dy之间时之间时,X,X在在x x和和x+dxx+dx之间的之间的条件概率条件概率.我们知道我们知道,对于所有对于所有f fY Y(y(y)0 0的的y y值值,给定给定Y=yY=y时时X X的条的条件期望件期望定义是定义是 EX|Y=y=EX|Y=y=xfxfX|YX|Y(x,y)dx(x,y)dx.例例6 6(习题习题6 6)假定假定X X和和Y Y有联合概率密度函数有联合概率密度函数 6xy(2-x-y),06xy(2-x-y),0 x x1,01,0y y1;1;0,0,其它其它.对于

16、对于0 0y y1,1,计算给定计算给定Y=yY=y时时X X的条件期望的条件期望.解解:我们首先计算条件密度我们首先计算条件密度 f fX|YX|Y(x,y(x,y)=)=(0 =(0 x x1)1)=.=.因此因此,有有 f(x,yf(x,y)=)=EX|Y=y=.EX|Y=y=.例例7 7 假定假定X X和和Y Y的联合密度为的联合密度为 4y(x-y)e4y(x-y)e-(x+y)-(x+y),0,0 x x,0yx;,0yx;0,0,其它其它.计算给定计算给定Y=yY=y的的EX|Y=y.EX|Y=y.解解:给定给定Y=yY=y时时X X的条件密度为的条件密度为 f fX|YX|Y(

17、x,y(x,y)=(x)=(xy)y)=(x =(xy,wy,w=x-yx-y)f(x,yf(x,y)=)=(=(x-y)ex-y)e-(x-y-(x-y),(),()最后的等号最后的等号,运用了均值为运用了均值为1 1的指数随机变量的期望值的指数随机变量的期望值 也为也为1 1的事实的事实.而且而且,对均值为对均值为1 1的指数随机变量的指数随机变量W,W,我们有我们有 EX|Y=y=EX|Y=y=x(x-y)ex(x-y)e-(x-y)-(x-y)dxdx=(=(w+y)wew+y)we-w-wdwdw =EW =EW2 2+yEW=2+y.(=1)+yEW=2+y.(=1)例例8 8 设

18、设X X和和Y Y的联合密度为的联合密度为 yeye-xyxy,0,0 x x,0,0y y2;2;0,0,其它其它.求求EeEex/2x/2|Y=1|Y=1的值的值.f(x,yf(x,y)=)=解解:给定给定Y=1Y=1时时X X的条件密度为的条件密度为 f fX|YX|Y(x|1)=(x|1)=e e-x-x.由由命题命题2.22.2的的(2)(2)(随机变量函数的数学期望随机变量函数的数学期望)有有 EeEeX/2X/2|Y=1=e|Y=1=ex/2x/2f fX|YX|Y(x|1)dx=e(x|1)dx=ex/2x/2e e-x-xdx=2.dx=2.通过取条件计算期望通过取条件计算期

19、望 让我们以让我们以EX|YEX|Y记随机变量记随机变量Y Y的这样的函数的这样的函数,它在它在Y=yY=y处处取得值是取得值是EX|Y=y.EX|Y=y.注意注意,EX|Y,EX|Y本身是一个随机变量本身是一个随机变量.我们已经讨论了我们已经讨论了条件期望的一个极为重要的性质条件期望的一个极为重要的性质:对于所有的随机变量对于所有的随机变量X X和和Y,EX=EEX|Y.Y,EX=EEX|Y.如果如果Y Y是离散随机变量是离散随机变量,那么上述那么上述重要性质重要性质可写为可写为 EX=EX|Y=EX=EX|Y=yPYyPY=y;=y;如果如果Y Y是密度为是密度为f fY Y(y(y)的连

20、续随机变量的连续随机变量,那么上述那么上述重要性重要性质质可写为可写为 EX=EX|Y=EX=EX|Y=yfyfY Y(y)dy(y)dy.下面是对下面是对X X和和Y Y都是离散随机变量的情形都是离散随机变量的情形,关于关于条件期望重条件期望重要性质要性质的证明的证明:EX|Y=EX|Y=yPYyPY=y=y=xPXxPX=x|Yx|Y=yPYyPY=y=y =x PY=y =x PY=y =xPXxPX=x,Yx,Y=y=y =PX=PX=x,Yx,Y=y=y =PX=x =PX=x =EX.=EX.对条件期望重要性质的解释对条件期望重要性质的解释:条件期望重要性质说明条件期望重要性质说明

21、对于计算对于计算EX,EX,我们可以取我们可以取Y=yY=y给定时给定时X X的条件期望的加权平均的条件期望的加权平均,每一项每一项EX|Y=yEX|Y=y用取条用取条件的那个事件的概率加权件的那个事件的概率加权.以下的例子显示其用途以下的例子显示其用途.例例9 9 小李准备读一章概率书或一章高数书小李准备读一章概率书或一章高数书.如果在他读的如果在他读的 一章概率书中的印刷错误数是均值为一章概率书中的印刷错误数是均值为2 2 的泊松分布的泊松分布,而而 在他读的一章高数书中的印刷错误数是均值为在他读的一章高数书中的印刷错误数是均值为5 5的泊松的泊松 分布分布,那么在假定小李选取哪一本数是

22、等可能的时那么在假定小李选取哪一本数是等可能的时,小小李读到的印刷错误数的期望是多少李读到的印刷错误数的期望是多少?解解:以以X X记印刷错误数记印刷错误数,令令 1,1,如果小李选取高数书如果小李选取高数书;2,2,如果小李选取概率书如果小李选取概率书.则则 EX=EX|Y=1PY=1+EX|Y=2PY=2EX=EX|Y=1PY=1+EX|Y=2PY=2 =.=.例例1010(随机变量的随机变量的随机数量和随机数量和的期望的期望)假定工厂设备每周假定工厂设备每周 出现事故次数的期望为出现事故次数的期望为4,4,又在每次事故中受伤工人数又在每次事故中受伤工人数 是具有相同均值是具有相同均值2

23、2的独立随机变量的独立随机变量;再假定在每次事故再假定在每次事故 中受伤工人数与每周发生的事故数目相互独立中受伤工人数与每周发生的事故数目相互独立.求每周求每周 受伤人数的期望受伤人数的期望.解解:以以N N记事故次数记事故次数,以以X Xi i记在第记在第i i次事故中的受伤人数次事故中的受伤人数,i=,i=Y=Y=1,2,1,2,那么伤者总数可以表示为那么伤者总数可以表示为X=.X=.现在现在 E =EE|N.E =EE|N.但是但是 E|N=n=E|N=nE|N=n=E|N=n =E =E =nEXnEX.由此由此,导出导出 E|N=NEX.E|N=NEX.因此因此 E =ENEX=EN

24、EX.E =ENEX=ENEX.所以所以,一周中受伤人数的期望为一周中受伤人数的期望为ENEX=42=8.ENEX=42=8.随机变量随机变量 等于等于N N个独立同分布的随机变量的和个独立同分布的随机变量的和,称之为称之为复合随机变量复合随机变量,其期望值是其期望值是:E =ENEX.E =ENEX.例例1111(几何分布的均值几何分布的均值)连续抛掷一枚出现正面的概率为连续抛掷一枚出现正面的概率为 p p的硬币的硬币,直至出现正面为止直至出现正面为止.求需要抛掷次数的期望求需要抛掷次数的期望.解解:以以N N记需要抛掷的次数记需要抛掷的次数,令令 1,1,如果第一次抛掷的结果是正面如果第一

25、次抛掷的结果是正面;0,0,如果第一次抛掷的结果是反面如果第一次抛掷的结果是反面.按照按照离散随机变量期望重要性质离散随机变量期望重要性质,有有 EN=EN|Y=1PY=1+EN|Y=0PY=0EN=EN|Y=1PY=1+EN|Y=0PY=0 =pEN|YpEN|Y=1+(1-p)EN|Y=0=1+(1-p)EN|Y=0Y=Y=由于由于Y=1Y=1的定义是第一次抛掷结果是正面的定义是第一次抛掷结果是正面,故需要抛掷故需要抛掷的次数的期望是的次数的期望是1,1,因而因而EN|Y=1=1;EN|Y=1=1;Y=0,Y=0,第一次抛掷结果是反面第一次抛掷结果是反面.但是假定相继的抛掷是独但是假定相继

26、的抛掷是独立的立的,可见在第一次出现反面后直到正面首次出现时的附可见在第一次出现反面后直到正面首次出现时的附加抛掷次数的期望是加抛掷次数的期望是EN.EN.因而因而EN|Y=0=1+EN.EN|Y=0=1+EN.于是于是,有有 EN=p1+(1-p)(1+EN).EN=p1+(1-p)(1+EN).解之得解之得 EN=1/p.EN=1/p.其实其实,N N是有概率分布列函数是有概率分布列函数p(np(n)=p(1-p)=p(1-p)n-1n-1的几何随机的几何随机变量变量,它的期望正如它的期望正如例例2.222.22,通过通过EN=EN=np(nnp(n)很容易很容易算得算得,而无须求助于条件

27、期望而无须求助于条件期望.不过不过,通过下一个例子通过下一个例子,就就会看出会看出“取条件取条件”求期望求期望是一个多么有用的技巧是一个多么有用的技巧.例例1212 某矿工身陷在有三个出口的矿井之中某矿工身陷在有三个出口的矿井之中.经第一个出经第一个出 口的通道行进口的通道行进2 2小时后小时后,他将到达安全地带他将到达安全地带.经第二个出经第二个出 口的通道行进口的通道行进3 3小时后小时后,他将回到矿井原地他将回到矿井原地.经第三个出经第三个出 口的通道行进口的通道行进5 5小时后小时后,他又将回到矿井原地他又将回到矿井原地.假定这位假定这位 矿工每次都等可能地选择任意一个出口矿工每次都等

28、可能地选择任意一个出口,求他直到到达求他直到到达 安全地带所需时间的期望值安全地带所需时间的期望值.解解:以以X X记矿工到达安全地带所需的时间记矿工到达安全地带所需的时间,以以Y Y记他最初选记他最初选 取的出口取的出口.则则 EX=EX|Y=1PY=1+EX|Y=2PY=2+EX=EX|Y=1PY=1+EX|Y=2PY=2+EX|Y=3PY=3 EX|Y=3PY=3 =EX|Y=1+EX|Y=2+EX|Y=3 =EX|Y=1+EX|Y=2+EX|Y=3 但但 EX|Y=1=2,EX|Y=2=3+EX,EX|Y=3=5+EX,EX|Y=1=2,EX|Y=2=3+EX,EX|Y=3=5+EX,

29、所以所以 EX=(2+3+EX+5+EX)EX=(2+3+EX+5+EX)解之得解之得EX=10.EX=10.例例13 13(匹配轮数问题匹配轮数问题)假设在假设在例例2.172.17中中,取到自己帽子的取到自己帽子的 人离开人离开,而其余的人而其余的人(没有没有匹配匹配到的那些人到的那些人)将他们取到将他们取到 的帽子放回房间中央的帽子放回房间中央,混杂后重新取混杂后重新取.假定这个过程连假定这个过程连 续进行到每个人都取到了自己的帽子为止续进行到每个人都取到了自己的帽子为止.a.a.假定假定R Rn n是开始时有是开始时有n n个人出席的轮数个人出席的轮数,求求ERERn n.b.b.设设

30、S Sn n是开始时是开始时n(n2)n(n2)个人参选的总次数个人参选的总次数,求求ESESn n.c.c.求这求这n(n2)n(n2)个人误取的期望数个人误取的期望数.解解:a.:a.由由例例2.172.17知知,不论留在那里的人有多少不论留在那里的人有多少,平均每轮有平均每轮有 一次匹配一次匹配.这就使人想到这就使人想到ERERn n=n=n这个结果是正确的这个结果是正确的.下面给出一个归纳性的证明下面给出一个归纳性的证明.显然显然,ER,ER1 1=1.=1.假定假定对对k=1,2,n-1,k=1,2,n-1,有有ERERk k=k.=k.为了为了计算计算ERERn n,我们先对我们先

31、对第一轮中的匹配数第一轮中的匹配数X Xn n取条件取条件,它给出它给出 ERERn n=ERERn n|X|Xn n=iPXiPXn n=i.=i.现在现在,给定了最初一轮的全部匹配数给定了最初一轮的全部匹配数i,i,需要的轮数将等于需要的轮数将等于1 1加上余下的加上余下的n-in-i个人匹配他们的帽子需要的匹配轮数个人匹配他们的帽子需要的匹配轮数.所所以以 ERERn n=(1+ER=(1+ERn-in-iPXPXn n=i)=i)=1+ER =1+ERn nPXPXn n=0+(=0+(ERERn-in-iPXPXn n=i)=i)=1+ER =1+ERn nPXPXn n=0+(=0

32、n-i)PXn-i)PXn n=i=i =1+ER =1+ERn nPXPXn n=0+n(1-PX=0+n(1-PXn n=0)-EX=0)-EXn n =ERERn nPXPXn n=0+n(1-PX=0+n(1-PXn n=0).=0).其中其中,最后一个式子使用了最后一个式子使用了例例2.172.17建立的结果建立的结果:EXEXn n=1.=1.对以上等式对以上等式,就就ERERn n 解方程解方程,便得便得ERERn n=n.=n.b.b.对于对于n2,n2,取条件于取条件于第一轮中的匹配数第一轮中的匹配数X Xn n,有有 ESESn n=ESESn n|X|Xn n=iPX

33、iPXn n=i=i =(=(n+ESn+ESn-in-i)PX)PXn n=i=i =n+=n+ESESn-in-iPXPXn n=i=i式中式中,ES,ES0 0=0.=0.为了求解以上关于为了求解以上关于ESESn n 的方程的方程,将其改写为将其改写为 ESESn n=n+En+E ()()我们想我们想,如果在每轮中恰有一次匹配如果在每轮中恰有一次匹配,那么共有那么共有n+2+1=n+2+1=n(n+1)/2n(n+1)/2次选取次选取.现在我们在现在我们在()()中来试探形式为中来试探形式为ESESn n=an+bn=an+bn2 2的解的解.为为 了该解在了该解在n2n2时满足时满

34、足()(),需要需要 an+bnan+bn2 2=n+Ea(n-X=n+Ea(n-Xn n)+b(n-X)+b(n-Xn n)2 2 或者或者,等价地等价地 an+bnan+bn2 2=n+a(n-EX=n+a(n-EXn n)+b(n)+b(n2 2-2nEX-2nEXn n+E )+E )利用利用例例2.172.17和和第第2 2章章的的习题习题4.4.所得到的所得到的EXEXn n=1,Var(X=1,Var(Xn n)=)=1 1的结果及的结果及E =Var(XE =Var(Xn n)+E)+E2 2XXn n 知知,只要有只要有 an+bnan+bn2 2=n+an-a+bn=n+a

35、n-a+bn2 2-2nb+2b-2nb+2b即可即可.经试解知经试解知,此式此式当当a=1,b=1/2a=1,b=1/2时成立时成立.也就是也就是 ESESn n=n+n=n+n2 2/2/2满足满足ESESn n 的递推方程的递推方程.这个结论对不对呢这个结论对不对呢?下面下面,我们通过对我们通过对n(2)n(2)做归纳完成做归纳完成 ESESn n=n+n=n+n2 2/2/2的的形式证明形式证明.n=2.n=2.此时此时,必须是第一轮没有人取到自己的帽子必须是第一轮没有人取到自己的帽子(n=2(n=2时时,若第一轮有一人取到了帽子若第一轮有一人取到了帽子,就都取到了帽子就都取到了帽子,

36、因而不会因而不会有第二轮的选取了有第二轮的选取了),),选取数为选取数为2;2;第二轮结束选取第二轮结束选取,选取数选取数也是也是2.2.满足满足 ESES2 2=2+2=2+22 2/2./2.现在将递推关系写成现在将递推关系写成 ESESn n=n+ESn+ESn nPXPXn n=0+=0+ESESn-in-iPXPXn n=i.=i.由于由于n2n2,所以应取所以应取ESES1 1=ES=ES0 0=0.=0.而归纳假设而归纳假设ESESk k=k=k+k+k2 2/2,k=2,3,n-1.(/2,k=2,3,n-1.(其实其实,还有还有PXPXn n=n-1=0).=n-1=0).故

37、故 ESESn n=n+ESn+ESn nPXPXn n=0+(n-i)+(n-i)=0+(n-i)+(n-i)2 2/2PX/2PXn n=i=i =n+ESn+ESn nPXPXn n=0+(n+n=0+(n+n2 2/2)(1-PX/2)(1-PXn n=0)=0)-(n+1)EX -(n+1)EXn n+E /2+E /2将将EXEXn n=1,E =2=1,E =2代入代入,便得便得 ESESn n=n+n=n+n2 2/2./2.c.c.记第记第j j个人取帽子的次数为个人取帽子的次数为C Cj j,j,j=1,2,n.=1,2,n.则则 C Cj j=S Sn n.取期望取期望,

38、并用每个并用每个C Cj j具有同样的均值的事实具有同样的均值的事实,进而有结果进而有结果 ECECj j=ESESn n/n/n=1+n/2.=1+n/2.因此因此,第第j j个人取错帽子的期望为个人取错帽子的期望为 ECECj j-1=n/2.-1=n/2.例例1414 如果连续地做每次成功的概率为如果连续地做每次成功的概率为p p的独立试验直至的独立试验直至 有有k k次相继成功次相继成功,那么所需试验的次数的均值是多少那么所需试验的次数的均值是多少?解解:以以N Nk k记为了得到记为了得到k k次相继的成功必须试验的次数次相继的成功必须试验的次数,并并 以以M Mk k记它的均值记它

39、的均值.通过对通过对k-1k-1次相继成功所必须试验的次相继成功所必须试验的 次数次数N Nk-1k-1取条件取条件,我们就得到我们就得到M Mk k的一个递推方程的一个递推方程.即即 M Mk k=ENENk k=EEN=EENk k|N|Nk-1k-1 而而 ENENk k|N|Nk-1k-1=N=Nk-1k-1+1p+(1-p)(1+EN+1p+(1-p)(1+ENk k)所以所以 ENENk k|N|Nk-1k-1=N=Nk-1k-1+1+(1-p)EN+1+(1-p)ENk k 这是因为若取这是因为若取N Nk-1k-1次试验得到次试验得到k-1k-1次相继的成功次相继的成功,则下一

40、则下一 次或者是成功次或者是成功,我们就接着得到我们就接着得到k k次成功次成功;或者是失败或者是失败,我们就必须重新开始我们就必须重新开始.对此式两边取期望对此式两边取期望,得得 M Mk k=M=Mk-1k-1+1+(1-p)M+1+(1-p)Mk k.或者或者 M Mk k=+=+由于首次成功的次数由于首次成功的次数N N1 1是参数为是参数为p p的几何随机变量的几何随机变量,所以所以 M M1 1=1/p=1/p 并且并且,做递推做递推,则有则有 M M2 2=+,=+,M M3 3=+=+进而进而,更一般地更一般地,有有 M Mk k=+.=+.例例1515(快速排序算法快速排序算

41、法)假设有假设有n n个不同的值个不同的值x x1 1,x,x2 2,x xn n 的的 一个集合一个集合,我们要将它们排列为增加的次序我们要将它们排列为增加的次序,即将它们即将它们 排序排序(sort).(sort).我们知道我们知道,完成递增排序的一个有效算法是完成递增排序的一个有效算法是快速排序快速排序 算法算法.这是一个递推的方法这是一个递推的方法.当当n=2n=2时时,该算法比较两个值该算法比较两个值,将它们置于合适的次序将它们置于合适的次序.当当n n2 2时时,它开始在它开始在n n个值中个值中随机地随机地选取一个譬如选取一个譬如x xi i,然后将其它的然后将其它的n-1n-1

42、个值与个值与x xi i比较比较,注意哪些小于注意哪些小于x xi i,哪些哪些 大于大于x xi i.以以S Si i记小于记小于x xi i的元素的集合的元素的集合,记大于记大于x xi i的元素的元素 的集合的集合.然后对集合然后对集合S Si i和和 分别排序分别排序.最后的次序由集最后的次序由集 合合S Si i的元素的次序的元素的次序,x,xi i和集合和集合 的元素的次序排序组成的元素的次序排序组成.例如例如,假定元素集合是假定元素集合是10,5,8,2,1,4,7.10,5,8,2,1,4,7.我们以我们以1/71/7的概率先选取其中一个的概率先选取其中一个,设为设为4.4.然

43、后将其它然后将其它6 6个值的每一个值的每一个与个与4 4作比较作比较,得到得到 2,1,4,10,5,8,7.2,1,4,10,5,8,7.将集合将集合2,12,1排序得排序得 1,2,4,10,5,8,7.1,2,4,10,5,8,7.在在10,5,8,710,5,8,7中随机选取一个中随机选取一个,譬如是譬如是7.7.将其它三个值与将其它三个值与7 7作比较作比较,得得 1,2,4,5,7,10,8.1,2,4,5,7,10,8.最后最后,将将10,810,8排序并结束排序并结束,得得 1,2,4,5,7,8,10.1,2,4,5,7,8,10.对对该算法有效性该算法有效性的一个量度是做

44、的一个量度是做比较的次数的期望比较的次数的期望.现以现以M Mn n记记n n个不同值的一个集合的个不同值的一个集合的快速排序算法快速排序算法的比较的比较次数的期望次数的期望.为了得到为了得到M Mn n的的一个一个递推式递推式,我们我们取条件于初取条件于初始的取值始的取值,有有 M Mn n=E=E比较数比较数|取到的是第取到的是第j j小的值小的值若初始的取值是第若初始的取值是第j j小的值小的值,则值比则值比j j小的集合的容量是小的集合的容量是j-j-1,1,值比值比j j大的集合的容量是大的集合的容量是n-jn-j.由于对于选定初始取值后由于对于选定初始取值后算法算法接着要作接着要作

45、n-1n-1次比较次比较,因此因此 M Mn n=(n-1+M=(n-1+Mj-1j-1+M+Mn-jn-j)=n-1+M)=n-1+Mk k(M M0 0=0)=0)即即 nMnMn n=n(n-1)+2 M=n(n-1)+2 Mk k.此式此式对对n+1n+1个不同值个不同值的集合的集合一样成立一样成立,所以也有所以也有 (n+1)M(n+1)Mn+1n+1=(n+1)n+2 M=(n+1)n+2 Mk k.后式减前式后式减前式,得得 (n+1)M(n+1)Mn+1n+1-nM-nMn n=2n+2M=2n+2Mn n亦即亦即 (n+1)M(n+1)Mn+1n+1=(n+2)M=(n+2)

46、Mn n+2n+2n从而从而,得得对该式进行迭代对该式进行迭代,有有 =2 (=2 (递推项递推项M M1 1=0)=0)所以所以 M Mn+1n+1=2(n+2)=2(n+2)=2(n+2),(n1).=2(n+2),(n1).利用恒等式利用恒等式对较大的对较大的n,n,得近似式得近似式 M Mn+1n+1=2(n+2)-=2(n+2)-2(n+2)2(n+2)dxdx-dxdx =2(n+2)2ln(n+2)-ln(n+1)+ln2-2ln3 =2(n+2)2ln(n+2)-ln(n+1)+ln2-2ln3 =2(n+2)ln(n+2)-ln +ln2-2ln3 =2(n+2)ln(n+2

47、)-ln +ln2-2ln3 2(n+2)ln(n+2).2(n+2)ln(n+2).下面介绍一个下面介绍一个运用条件期望恒等式运用条件期望恒等式(重要性质重要性质)计算条件计算条件期望期望的例子的例子.例例1616 在在例例2.172.17的有的有n(nn(n1)1)个人的匹配问题中个人的匹配问题中,求给定第求给定第 一个人没有匹配时的匹配数的条件期望一个人没有匹配时的匹配数的条件期望.解解:以以X X记匹配数记匹配数.如果第一个人有一个匹配如果第一个人有一个匹配,令令X X1 1等于等于1;1;否则令否则令X X1 1等于等于0.0.EX=EX|X EX=EX|X1 1=0PX=0PX1

48、1=0+EX|X=0+EX|X1 1=1PX=1PX1 1=1=1 =EX|X =EX|X1 1=0 +EX|X=0 +EX|X1 1=1 .=1 .但是但是,由由例例2.172.17知知,EX=1.,EX=1.此外此外,给定第一个人有一个给定第一个人有一个匹配时匹配时,匹配数的期望等于匹配数的期望等于1 1加上当加上当n-1n-1个人在他们自己个人在他们自己 的的n-1n-1个帽子中选取的匹配数的期望个帽子中选取的匹配数的期望,也就是说也就是说 EX|XEX|X1 1=1=2=1=2 所以所以,有有 EX|XEX|X1 1=0=.=0=.通过取条件计算方差通过取条件计算方差 条件方差也可以用

49、来计算随机变量的方差条件方差也可以用来计算随机变量的方差.特别地特别地,当当我们运用我们运用 Var(XVar(X)=EX)=EX2 2-(EX)-(EX)2 2计算方差时计算方差时,可以通过取条件得到可以通过取条件得到EXEX和和EXEX2 2.例例1717(几何随机变量的方差几何随机变量的方差)连续地做每次成功的概率为连续地做每次成功的概率为 p p的独立试验的独立试验.N.N是首次成功时的试验次数是首次成功时的试验次数.求求Var(NVar(N).).解解:如果首次试验成功则记如果首次试验成功则记Y=1,Y=1,否则记否则记Y=0.Y=0.方差计算公式方差计算公式 Var(NVar(N)

50、EN)=EN2 2-(EN)-(EN)2 2.为计算为计算ENEN2 2,对对Y Y取条件并有取条件并有 ENEN2 2=EEN=EEN2 2|Y.|Y.而而 ENEN2 2|Y=1=1;|Y=1=1;EN EN2 2|Y=0=E(1+N)|Y=0=E(1+N)2 2.因为因为,如果首次试验的结果是成功如果首次试验的结果是成功,那么显然那么显然N=1,N=1,从而从而 N N2 2=1;=1;如果首次试验的结果是失败如果首次试验的结果是失败,那么得到第一次成那么得到第一次成 功所需的试验总次数等于功所需的试验总次数等于1(1(首次试验是失败首次试验是失败)加上进行加上进行 额外试验所需的试验