Markov-chain经典讲解

CompanyLOGO马尔科夫链简述主讲人：滕飞CompanyLogo超市收银台模型离散时间n=0,1…顾客到达:伯努利分布(p)（顾客到达与否是相互独立的）客户服务时间:几何分布（q）(购物结算是否完成相互独立)“状态”:在时间为n时，顾客数量nX129100假设我们的超市并不大，只能让10排队(1-p)pq(1-p)p(1-q)pq+(1-p)(1-q)q(1-p)pq+(1-p)(1-q)pq+(1-p)(1-q)p(1-q)q1-qCompanyLogo有限马尔科夫链----：在n次转换（transition）后的状态。nX----所在集合属于有限集合。例如{1，2，…..，m}0X可以是给定的，也可以是随机变量。马尔科夫性质/假设：（未来只与现在的状态有关，与过去无关。）ijP1P()nnXjXi11P(,,,)nnnXjXiXX定义性质CompanyLogo132ij31p33p32p3ip对马尔科夫链性质的解释CompanyLogon次转换后的马尔科夫链可能性在初始状态给定的条件下，状态占用的可能性:0()()ijnrnPXjXiTime0Timen-1Timen….….jlkmi1(1)irn(1)ikrn(1)imrn1jpkjpmjpCompanyLogon次转换后的马尔科夫链可能性递推公式：11()()mijikkjkrnrnp在没有给定初始状态，（开始状态是随机的）1()()()mnnijiPXjPXirni1kmj1ipikpimp1(1)jrn(1)kjrn(1)mjrnTime0TimenTime1CompanyLogon次转换后的马尔科夫链可能性递推公式的另一种形式：111()(1)mijijkrnprn在没有给定初始状态，（开始状态是随机的）1()()()mnnijiPXjPXirnCompanyLogon次转换后的马尔科夫链可能性例子n=0n=1n=2n=100n=10110.50.352/72/700.50.655/75/700.20.352/72/710.80.655/75/7120.50.80.50.211()rn12()rn21()rn22()rnCompanyLogo马尔科夫链一般性收敛问题()ijrn收敛吗22()rn22()rn1230.50.511当n=奇数：=0当n=偶数：=122()rnCompanyLogo极限取决于开始状态吗？11()rn0.30.40.312331()rn21()rn=1=0=1/2对于任何n对于任何nn趋于无穷CompanyLogo常返态和暂态状态i的重现（recurrent）:从状态i开始，无论你到达何处，你都可以通过一种路径回到i状态，则称为状态i为常返态。如果i不能重现，就称为状态i为暂态（transient）。13254876recurrentclasstransientclassrecurrentclassCompanyLogo常返状态和暂态如果i是暂态：i为有穷次数。常返状态类（recurrentclass）：彼此之间相互联系的常返态的组合叫做常返状态类。()nPXi0CompanyLogo周期态如果常返态类中的状态可以分成（d2）的群，以至于所有转换过程都是从一个群到达另一个群，那么我们可以说这些在常返态类的状态是具有周期性的。21123CompanyLogo周期态789651234CompanyLogo周期态789651234CompanyLogo周期态789651234CompanyLogo稳态可能性在开始状态相互独立的情况下存在：条件为1所有常返态都在一个单独的类中。2这个常返态类不是周期性的。假设“存在”，则递推公式为：?)(j一定收敛于nrijkkjikijpnrnr)()(1CompanyLogo稳态可能性当n趋向无穷大，则附加方程：kkjkjpjjj1CompanyLogo关于频率的解释从长期看，停留到j态的频率为：从状态k转换到状态j的频率为：转换到状态j的频率为：kkjkjpjkjkpkkjkp12mj.....CompanyLogon次转换后的马尔科夫链可能性例子120.50.80.50.22112050..2128050..121CompanyLogo生老病死12m-1m001p0p1q1p2qmqmq1ii+1ip1iq11iiiiqpCompanyLogo生老病死特别的，在所有状态下当，并且，11iiiiqpppiqqiqp/iiiqp1ii0mi.....1,0CompanyLogo生老病死当m为无穷大时101nXE（当处于稳态状态下）CompanyLogo例子120.50.80.50.27/217/52我们假定从状态1开始运转。)1,1(1001XXP)1,11()11(0110001XXXPXXP1111111)99(prpCompanyLogo)2,1(101100XXP)1,12()11(01001010100XXXPXXP1211)100(pr121pCompanyLogo吸收概率计算在给定初始状态i的情况下，经过一系列的变换最终到达状态4的概率？ia1532410.20.40.50.60.80.210.3i=4,ai=1i=5,ai=0CompanyLogo考虑241450.20.8128.02.0aaCompanyLogo3210.30.41235.03.0aaaCompanyLogo1320.60.42316.04.0aaaCompanyLogo预期时间内收敛128.02.0aa1235.03.0aaa2316.04.0aaa383.01a426.02a319.03ajjijiapa不直接相连的状态为没有和目标常返态类immmkbkappai的状态为和目标常返态类相连kCompanyLogo预期时间内收敛从最初的状态i到目的常返态类所期望的转换步数31240.50.40.50.60.80.21iCompanyLogo预期时间内收敛12340.60.4233214.06.01CompanyLogo预期时间内收敛31240.50.5122135.05.01CompanyLogo预期时间内收敛2.08.0122144CompanyLogo预期时间内收敛2135.05.013214.06.012.08.01275.1311228750.133对于与常返态类不相邻的状态i有：jijjip1对于与常返态相邻的状态k有：jijjimkppCompanyLogoCompanyLogo平均首通时间和重现时间常返态类中:规定s是常返态，并且只有一条回路。s12平均首通时间状态i到s}},0[min{0iXsXnEtni的解为mttt,...,210stjjijitpt,1siCompanyLogo平均首通时间和重现时间平均重现时间]},1[min{0*sXsXnEtnsjjsjstpt1*s12jCompanyLogo伯努利分布当伯努利试验成功，伯努利随机变量为1。其成功机率为p若伯努利试验失败，伯努利随机变量为0。失败机率为q=1-p，返回CompanyLogo几何分布在第n次伯努利试验中，试验k次才得到第一次成功的机率。详细的说，是：前k-1次皆失败，第k次成功的概率。（简单可以考虑打靶模型，打中停止）分布函数P(X=k)=p*(1-p)^(k-1)，k=1,2,3,……返回