(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讲义那招)
这不是什么"极端"的例子.