(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)