PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Interview street: zombie march

看板Prob_Solve (計算數學 Problem Solving)作者neutrino (十年一夢)時間12年前 (2012/10/25 11:08)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/6 (看更多)

※ 引述《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)