第6章-马尔可夫链及随机游动(马坤-周波)

第六章马尔可夫链及随机游动2目录2-SAT问题(6.1)算法、期望分析马尔可夫链(6.2)定义、性质、定理、例子图上的随机游动(6.3)定义、定理、例子电网络(6.4)定义、性质图的连通性(6.6)算法无向图s-t连通性算法32-SAT问题回顾K-SAT问题NPk≥3Pk=3输入由每个字句集合的合取给出的布尔公式，其中每个字句是文字的析取上章指出:如果公式是满足的，算法至少以1-2-m的概率返回一个满足的赋值P10442-SAT问题回顾52-SAT问题回顾ASimpleMonteCarloAlgorithmfor2SAT,Papadimitriou,FOCS1991Paper[325]:Onselectingasatisfyingtruthassignment62-SAT问题回顾方法:从一个赋值开始，随机寻找不满足子句，改变赋值，使其成为满足的(随机尝试改变一个)具体算法：1.以任意一个真值赋值开始2.while所有子句不满足{选择一个不满足子句;在子句中随机选择一个文字，改变其赋值;}3.找到一个真值指派则返回，否则公式不可满足72-SAT问题回顾例X1=0X2=1X3=0,不满足,随机选1文字X2,另X2=0,=1满足，再检查其它字句,不满足，令X1=1,则所有字句都满足了。找到了一个真值指派X1=1,X2=0,X3=0)()(3121XXXX21XX21XX31XX82-SAT问题-分析分析：为了讨论算法的迭代次数n个变量,S表示n个变量的满足的赋值Ai表示经第i步算法后的变量赋值Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数，当Xi=n时，算法以满足赋值结束。如果算法找到了另外的满足赋值，可能在Xi达n之前就结束。最糟糕的是到Xi=n算法停止。92-SAT问题观察(Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数)对于非满足字句，这表示Ai与S在这个字句中至少有1个变量值不一致，子句中有不多于两个的变量(2-SAT),所以增加匹配的个数的概率至少为1/2,即2/1)|1Pr(1jXjXii对于非满足字句，因为字句中有不多于两个的变量(2-SAT),所以减少匹配的个数的概率至多为1/22/1)|1Pr(1jXjXii1)0|1Pr(1iiXX特殊102-SAT问题作以下限制，上述公式去等号。将2-SAT问题看作线(整数0,1,2…)上的随机游动。当前位置为i,下一步的位置可能是i-1或i+1，且到这两个位置的概率=1/2112-SAT问题定理6.1假定n个变量的2-SAT公式有满足赋值，且2-SAT算法允许运行到找到1个可满足赋值，那么找到一个赋值算法的所期望步数O(n2)证明:算法过程看出一种随机游动,图G的顶点是0,1…n,且顶点i与i-1和i+1相邻，问从0到n的期望步数h0。设hj是从顶点j到n的期望步数的上界.hn=0,h0=h1+1,hk=1+(hk+1+hk-1)/2我们得到hk-hk+1=2k+1，由此得h0=1+3+...+(2n-1)=n2证毕当公式是不可满足的，该算法能返回一个正确答案；当公式是满足时候，该算法不一定能找到一个满足的赋值12马尔可夫链定义及表示定义:一个离散时间随机过程X0,X1,…是马尔可夫链，如果n1122n-1n-1nn-1n-1P{X=j|X=i,X=i,,X=i}=P{X=j|X=i}n=1,2,3,状态空间I={i1,i2,……in-1,in}n时刻Xn的概率分布向量P{Xn=i}P{Xn=j|Xn-1=in-1}一步转移概率性质：Xn依赖于前一状态Xn-1,但与过程图和到达Xn无关—无记忆性(马尔可夫性)13马尔可夫链定义及表示线上的随机游动14马尔可夫链定义及表示定义:一步转移矩阵P=(Pi,j)其中Pi,j=Pr(Xt=j|Xt-1=i)性质:转移矩阵每行和为11,0jjPi晴天阴天下雨晴天0.500.250.25阴天0.3750.250.375下雨001例1150.375•转移概率矩阵•状态转移图1230.250.2510.50.500.250.250.3750.250.375001A0.25pij:表示天气从状态i转到j的概率•第四天天气概率分布303PPA16马尔可夫链定义及表示t步转移矩阵:从状态i出发恰好经t步到状态j的概率)1()(ttPPP所以,]|Pr[0)(,iXjXPttji由于1,0,,tjkkkitjiPPP推广，17马尔可夫链定义及表示有向加权图G=(V,E,w)如下:01231/41/23/41/21/61/41/411/34/14/12/1001006/13/102/14/304/10P1步转移概率矩阵问;1.经3步从状态0到状态3的概率?2.从4个状态中均匀随机选取一个状态开始，经3步后到状态3技术的概率例218马尔可夫链定义及表示192/47192/10796/1316/1010036/5144/7924/548/5192/4164/2948/716/33P1.从状态0到3的经3步的概率为41/192验证这样路径有条0-1-0-3,0-1-3-3,0-3-1-3,0-3-3-3概率为43/32+1/96+1/16+3/64=41/1922.从4个状态中均匀随机选取一个状态开始，经3步后到状态3技术的概率(1/4,1/4,1/4,1/4)P3=(17/192,47/384,737/1152,43/288)19马尔可夫链定义及表示例3：2-SAT问题(Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数)2/1)|1Pr(1jXjXii2/1)|1Pr(1jYjYii作如下限制:Y0=X02/1)|1Pr(1jXjXii2/1)|1Pr(1jYjYii1)0|1Pr(1iiYY则Y0,Y1…..是马尔可夫链20马尔可夫链定义及表示首达概率fi,j：从状态i出发经t步首次到状态j的概率0)(,,ttjijirf其中)|,11;Pr(0,)(iXjXtsjXrstjit若首达时间hi,j:从状态i首次到状态j的期望时间hi,jjittjirth,)(0,21马尔可夫链定义及表示定义6.1fi,i=1,i为常返状态(persistent)fi,i1(此时hi,i=∞),i为瞬时状态(transient),也叫非常返状态对于常返状态i,即fi,i=1hi,i∞,常返状态i是正常返的hi,i=∞,常返状态i是零常返的若状态i是正常返的,且非周期,称i为遍历状态在一个有限不可约的马尔可夫链中,所有常返状态时正常返的从i出发,经过有限步,可以以概率1返回22马尔可夫链定义及表示例4马氏链的S={1,2,3,4},转移概率矩阵为:02/102/103/23/100001002/12/1P23马尔可夫链定义及表示对于状态4,f4,4=01,所以状态4是非常返的对于状态3,f3,3=2/3+0=2/31,所以状态3是非常返的对于状态1,f1,1=1/2+(1/2)*1=1,所以状态1是常返的对于状态2,f2,2=0+(1/2)*1+(1/2)*(1/2)+(1/2)*(1/2)*(1/2)+….=1/2+1/4+1/8+….=1,所以状态1是常返的等比数列24马尔可夫链定义及表示232122111)(1,11,1ttrth321...2120111)(2,22,2nttnrth所以,状态1,2是正常返的25马尔可夫链定义及表示定义6.2,6.3强连通图:在有向图G中,如果对于每一对顶点vi,vj,从vi到vj和vj到vi都存在一条路径，则称G是连通图强连通分量:有向图的极大强连通子图(i到j有路径，，从j到i也有路径)26马尔可夫链定义及表示定义6.4马尔可夫链是不可约的:其对应的图由一个强连通分量组成定义6.5定义q(t)=(q1(t),q2(t)…qn(t))为状态概率向量(也叫做t时刻的链的分布),是一个行向量,其分量是状态i在时刻t的概率Pqqtt)1()(ttPqq)0()(容易看出,状态分布于转移概率的关系27马尔可夫链定义及表示定义6.6平稳分布马尔可夫平稳分布是满足P的概率分布回忆Pqqtt)1()(如果一个链达到了平稳分布，那么它在所有未来时间都保持这个分布。这样一个平稳分布表示链的性态中一种不变的状态或平衡，即经过一次转移后概率状态不发生变化28马尔可夫链定义及表示定义6.7在离散马尔可夫链中状态j是周期的，如果存在一个整数T1,使得Pr(Xt+s=j|Xt=j)=0,除非s能被T整除。一个离散马尔可夫链是周期的，如果链的任一状态是周期的，一个状态或链不是周期的，称作非周期的。定义6.8一个非周期的正常返状态是遍历状态定义6.9马尔可夫链是遍历的，如果它的所有状态是遍历的。29马尔可夫链定义及表示定理6.2(FundamentalTheoremofMarkovChains)任意有限、不可约马尔可夫链有以下性质:1.所有状态是可遍历的(非周期正常返),fi,i=1,hi,i=1/Πi，其中Πi是马尔可夫链在无穷远的未来将处于状态i的概率2.链有唯一的平稳分布3.对所有j和i4.假设N(i,t)是马氏链在在t步内访问状态i的次数“不可约”是指每一个状态都可来自任意的其它状态。),...,,(10niiitijthP,,/1lim,且与j无关itttiN),(lim30马尔可夫链定义及表示说明1.从状态i到i的期望时间是hi,i，所以我们期望处于状态i的概率是1/hi,i,即Πi=1/hi,i31无向图上的随机游动定义7.9:G上的随机游动是由一个质点在G的顶点间移动的序列定义的马尔可夫链MG。在这个过程中，质点在已知时间步的位置是系统的状态。如果质点在顶点i,且如果i有d(i)条出发边，那么质点沿边(i,j)一定到临点j的概率是1/d(i)otherwiseEvuudPuv0),()(/132无向图上的随机游动例1三角形概率矩阵02/12/12/102/12/12/10PNotefortriangle,fa,b=fb,aabc33无向图上的随机游动QuestionsHowmanystepstogetfromutovHowmanystepstogetbacktoinitialnodeHowmanystepstovisiteverynodeEasyquestionstoanswerifweconsiderasimpleexample34无向图上的随机游动引理6.3G上的随机游动收敛于平稳分布∏,其中∏v=d(v)/2|E|证明：因为N(v)表示顶点v的临点集合引理6.4hv,v=1/∏v=2m/d(v)=2|E|/d(v)||2)()(1||2)()(EvdudEudvNuvP35无向图上的随机游动定义6.10击中时间HittingTime(首达时间),hu,vtheexpectednumberofstepsneededbeforereachingnodejwhenstartingfromnodeiisthehittingtime36无向图上的随机游动定义6.11往返时间(commutetime)Cu,v=hu,v+hv,uThecommutetimeistheexpectednumberofstepstoreachnodejwhenstartingfromiandthenreturningbacktoiWecanexpresshittingtimeintermsofcommutetimeas