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

第六章第六章 马尔可夫链及随机游动马尔可夫链及随机游动严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。目录o2-SAT问题问题(6.1)算法、期望分析算法、期望分析o马尔可夫链马尔可夫链(6.2)定义、性质、定理、例子定义、性质、定理、例子o图上的随机游动图上的随机游动(6.3)定义、定理、例子定义、定理、例子o电网络电网络(6.4)定义、性质定义、性质o图的连通性图的连通性(6.6)算法算法n无向图无向图s-t连通性算法连通性算法2严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题回顾oK-SAT 问题NP k 3P k=3输入由每个字句集合的合取给出的布尔公式，其中每个字句是文字的析取上章指出:如果公式是满足的，算法至少以1-2-m的概率返回一个满足的赋值 P1043严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题回顾4严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题回顾oA Simple Monte Carlo Algorithm for 2SAT,Papadimitriou,FOCS 1991Paper325:On selecting a satisfying truth assignment 5严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题回顾o方法:从一个赋值开始，随机寻找不满足子句，改变赋值，使其成为满足的(随机尝试改变一个)o具体算法：1.以任意一个真值赋值开始2.while 所有子句不满足选择一个不满足子句;在子句中随机选择一个文字，改变其赋值;3.找到一个真值指派则返回，否则公式不可满足6严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题回顾o例 oX1=0 X2=1 X3=0,不满足,随机选1文字X2,另X2=0,=1满足，再检查其它字句,不满足，令X1=1,则所有字句都满足了。找到了一个真值指派X1=1,X2=0,X3=07严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题-分析分析：为了讨论算法的迭代次数n个变量,S表示n个变量的满足的赋值Ai表示经第i步算法后的变量赋值Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数，当Xi=n时，算法以满足赋值结束。如果算法找到了另外的满足赋值，可能在Xi达n之前就结束。最糟糕的是到Xi=n算法停止。8严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题o观察(Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数)n对于非满足字句，这表示Ai与S在这个字句中至少有1个变量值不一致，子句中有不多于两个的变量(2-SAT),所以增加匹配的个数的概率至少为1/2,即n对于非满足字句，因为字句中有不多于两个的变量(2-SAT),所以减少匹配的个数的概率至多为1/2特殊9严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题o作以下限制，上述公式去等号。将2-SAT问题看作线(整数0,1,2)上的随机游动。o当前位置为i,下一步的位置可能是i-1或i+1，且到这两个位置的概率=1/210严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2-SAT问题o定理6.1 假定n个变量的 2-SAT公式有满足赋值，且2-SAT算法允许运行到找到1个可满足赋值，那么找到一个赋值算法的所期望步数O(n2)证明:算法过程看出一种随机游动,图G的顶点是0,1n,且顶点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证毕o当公式是不可满足的，该算法能返回一个正确答案；当公式是满足时候，该算法不一定能找到一个满足的赋值11严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示定义:一个离散时间随机过程X0,X1,是马尔可夫链，如果状态空间 I=i1,i2,in-1,in n时刻Xn的概率分布向量 PXn=iPXn=j|Xn-1=in-1 一步转移概率性质：Xn依赖于前一状态Xn-1,但与过程图和到达Xn无关无记忆性(马尔可夫性)12严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示线上的随机游动13严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示定义:一步转移矩阵P=(Pi,j)其中Pi,j=Pr(Xt=j|Xt-1=i)性质:转移矩阵每行和为1 晴天晴天 阴天阴天 下雨下雨晴天晴天 0.50 0.25 0.25阴天阴天 0.375 0.25 0.375下雨下雨 0 0 1例例114严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。转移概率矩阵 状态转移图1230.50.25pij:表示天气从状态i转到j的概率第四天天气概率分布15严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示t步转移矩阵:从状态i出发恰好经t步到状态j的概率所以,由于推广，16严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示有向加权图G=(V,E,w)如下:01231/41/23/41/21/61/41/411/31步转移概率矩阵问;1.经3步从状态0到状态3的概率?2.从4个状态中均匀随机选取一个状态开始，经3步后到状态3技术的概率例例217严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示1.从状态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)18严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示例例3：2-SAT问题(Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量数)作如下限制:Y0=X0则Y0,Y1.是马尔可夫链19严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示o首达概率fi,j：从状态i出发经t步首次到状态j的概率其中o首达时间hi,j:从状态i首次到状态j的期望时间hi,j20严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示o定义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返回21严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示例例4马氏链的S=1,2,3,4,转移概率矩阵为:22严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示对于状态4,f4,4=01,所以状态4是非常返的对于状态3,f3,3=2/3+0=2/31,使得Pr(Xt+s=j|Xt=j)=0,除非s能被T整除。一个离散马尔可夫链是周期的，如果链的任一状态是周期的，一个状态或链不是周期的，称作非周期的。定义6.8 一个非周期的正常返状态是遍历状态定义6.9 马尔可夫链是遍历的，如果它的所有状态是遍历的。28严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示o定理6.2(Fundamental Theorem of Markov Chains)任意有限、不可约马尔可夫链有以下性质:n1.所有状态是可遍历的(非周期正常返),fi,i=1,hi,i=1/i，其中i是马尔可夫链在无穷远的未来将处于状态i的概率n2.链有唯一的平稳分布n3.对所有j和in4.假设N(i,t)是马氏链在在t步内访问状态i的次数“不可约”是指每一个状态都可来自任意的其它状态。,且与j无关29严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。马尔可夫链定义及表示o说明n1.从状态i到i的期望时间是hi,i，所以我们期望处于状态i的概率是1/hi,i,即i=1/hi,i30严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动定义7.9:G上的随机游动是由一个质点在G的顶点间移动的序列定义的马尔可夫链MG。在这个过程中，质点在已知时间步的位置是系统的状态。如果质点在顶点i,且如果i有d(i)条出发边，那么质点沿边(i,j)一定到临点j的概率是1/d(i)31严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动o例1 三角形概率矩阵Note for triangle,fa,b=fb,aabc32严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动oQuestionsnHow many steps to get from u to vnHow many steps to get back to initial nodenHow many steps to visit every nodenEasy questions to answer if we consider a simple example33严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动o引理6.3 G上的随机游动收敛于平稳分布,其中v=d(v)/2|E|证明：因为 N(v)表示顶点v的临点集合o引理6.4 hv,v=1/v=2m/d(v)=2|E|/d(v)34严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动定义6.10击中时间Hitting Time(首达时间),hu,v the expected number of steps needed before reaching node j when starting from node i is the hitting time35严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动定义6.11往返时间(commute time)Cu,v=hu,v+hv,uThe commute time is the expected number of steps to reach node j when starting from i and then returning back to iWe can express hitting time in terms of commute time as36严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图上的随机游动定义6.12Cu(G):从u出发到其它定点至少1次的步数覆盖时间(Cover Time):C(G)=max Cu(G)o定理 在任意一个n-顶点的图中，对于所有顶点Cu,vn3 37严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图上的随机游动o例2 n顶点的棒棒图(Lollipop)是一个在n/2个顶点上的团与n/2个顶点上的路相连接的图。结点u是团与路的一部分，令v表示路的另一端点。n/2个顶点的团uv38严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图上的随机游动1.Hitting time from i to j not necessarily same a time from j to i2.Adding more edges shouldnt help reduce the cover time完全图Kn的覆盖时间(nlogn),而Ln的覆盖时间(n3),Ln可以由Kn增加边构成39严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。无向图上的随机游动o引理6.5The commute is bounded by 2mCu,v2m40严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图上的随机游动o例3(练习6.1P127)，对于完全图Kn,nhu,v=n-1nCu(G)=(n-1)Hn-11.t次伯努利试验 前t-1次皆失败，第t次才成功的几率 其中41严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。电网络电网络的图表示:图上每一条边看作具有等效电阻R(i,j)：i到j的等效电阻基尔霍夫定律 电流定律：瞬时流入电路任一节电的电流的代数和为0，即流入=流出欧姆定律 I=/R42严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。电网络o等效电阻nSerial:R=R1+R2.nParallel:R=R1*R2/(R1+R2).R1R1R2R243严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。TheoremChandra et al.STOC 1989oFor any two nodes u and v of a simple m-edge graph G,C(u,v)=H(u,v)+H(v,u)=2mR(u,v),where R(u,v)is the effective resistance in G between nodes u and v with respect to the setting that each edge of G is equipped with one unit of resistance.44严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图的连通性问题-无向图oS-t连通性问题 s-t是否在一个连通分量里,是否存在一条从s到t的路确定方法：图的搜索(深度或广度)随机算法(s-t连通性算法)：1.从s开始随机游动2.如果在4n3步之内到t，则返回存在一条路；否则返回不存在路 定理:s-t连通性算法以1/2概率返回正确答案，当存在s到t的路时，该算法只会犯返回不存在这样路的错误45