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

Re: [問題] Interview street: zombie march

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

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

(1) 原題目是要求 simulating a given Markov chain with given state , find time-t distribution? 還是要求stationary distribution? 我反覆check 原網頁, 我理解是偏向前者. (2) 無論如何, periodicity究竟要怎麼面對, 怎麼處理? 這不是trivial的問題各位或許可以查一下手邊的書, 看看是不是其實書上都有討論Markov Chain是否是aperiodic的前提. 我以為是我書念得太鬆散, survey以後才注意到這其實值得討論. google 一下 "markov chain periodicity", 可以找到一些教材之類的, 舉幾個例子看看他們怎麼處理: www.cs.berkeley.edu/~sinclair/cs294/n2.pdf 他的作法是 P是transition matrix, irreducible, 引進 P' = a*P + (1-a) * I 0<a<1 則P' is aperiodic. 同時, P 和 P'有相同的stationary distribution. (漂亮!) (但是這是為了求stationary distribution. "This operation corresponds to introducing a self-loop at all vertices of G(P) with probability 1 – α." 在我們的問題, 一個vertex上的Zombie, 留在原地的機率是0 ) www.cs.iastate.edu/~pavan/633/lec7.pdf 直接把討論限定在non-bipartite, connected, undirected graph www2.aku.edu.tr/.../markov_chains_and_random_walks.ppt 同上 www.math.ucla.edu/~pejman/intro2prob/LiveMeeting11.pdf 這份講義比較完整討論recurrence, transience, periodicity people.csail.mit.edu/costis/6896sp11/lec2.pptx "For an irreducible Markov chain P, if G(P) is undirected then aperiodicity is equivalent to G(P) being non-bipartite." (3) 前面有幾位觀察到(0-10-0) <-> (5-0-5)或者 (1-3-1-3-1) 的例子, 其實都是bipartite graph, 而且只要bipartite就有這個問題. (除非題目只問stationary distribution, =>用berkeley講義那招) 這不是什麼"極端"的例子. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.211.32.194 ※ 編輯: neutrino 來自: 218.211.32.194 (10/31 15:21)