※ 引述《Leon (Achilles)》之铭言： : 2. 请问几步之後他会收敛到 stationary probability? : Ans: 这问题也是很大, 因为这牵扯到 Markov Chain mixing time, : 这是 Markov Chain Monte Carlo 的核心问题, 也.. 难解. : 但是, 求解 stationary probability distribution 的过程, : 漂亮的令你难以想像. : We can define the Graph G = (v,e), : Let node j is the neightbor of node i, : and we define the number of neighbor for node i as N(i). : Then the transition probability (i,j) is = 1/N(i), : if j is the neighbor of i. : Otherwise, it's 0. : And, obvious;y, sum of N(i) = 2|e| : 然後这是我们的 Claim: : The stationary probability for node i = 1/2|e| * N(i). : 证明非常的简单: : if p is the station probability, then p = M*p, M is the transition. : Thus, let's consider probability for node i after transition : It will equal to : sum_{j in neighbor of i} p(j,i) p(j) : = sum_{..} 1/N(j) * 1/2|e|* N(j) : = 1/2|e| sum_{..}* 1 : = 1/2|e| N(i) : ---------- : 上面讲的那麽多, 简单的ㄧ句话就是, 有最多 edge 那个 vetrice 会有最大的 : stationary probability : ---------- : 我试了几个小例子, 应该是对的 : 如果错的话请不吝指正. 假定说e(v,t)是node v 在时间 t的时候的expected amount 如果把 e(v, t) == e(v, t+1) for all v 称作在t的时候 进入某种"稳态" (这也是前面推文几个程式判定的方法) //这个 2.可以很直觉地两句话讲完: 则2.提到的证明, 跟下面这个figure很有关系 如果每个node i上, 依照他有N(i)个edge, 就放N(i)个殭屍. 则下个时间, 任何node i, 都会从他的每个edge各送出一个殭屍(expectedly), 也各收到一个 (expectedly). 所以这是个"稳态". ======= 回到这个quiz, 但是, 不是每个initial state都能达到稳态. 像前面有人举例过的, 0-2-0 和 1-0-1 循环 (从2-0-0开始也是掉入这个循环) 事实上如果所有node v_0, v_1, ... v_n 排列成path, 只要所有奇数node上的殭屍数=0, 则下个timestamp所有偶数node上的殭屍数=0, 而下下个timestamp 所有奇数node上的殭屍数=0... 更进一步说, 如果G 是bipartite, 假定node被color成黑和红, 则每个timestamp, 黑node的殭屍总数 和 红node的殭屍总数 互换. 又, 依照这次的题目constrain, 随便给一个depth很深的tree, 我就想不太到真的去计算k个transition的效果以外的方法 @@ matrix M, M^k可以用lg k次matrix相乘, 可是这个M有点大, 乘一乘以後又不sparse了... 如果他的测试资料都会进稳态, 他的测试资料是(故意?)放水? 或者条件没给完整... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.211.32.194 ※ 编辑: neutrino 来自: 218.211.32.194 (10/25 11:14) ※ 编辑: neutrino 来自: 218.211.32.194 (10/25 11:23) ※ 编辑: neutrino 来自: 218.211.32.194 (10/25 11:50) ※ 编辑: neutrino 来自: 218.211.32.194 (10/25 12:22)