Re: [問題] Interview street: zombie march

[DJWS (...)]

※ 引述《Leon (Achilles)》之銘言：
: ※ 引述《shaopin (problem maker)》之銘言：
: : 題目是要問: 最後 有最多zombie的五個node上的zombie數量
: : 在此請教不知道更快的做法是否是跟那只選五個最多的zombie node
: : 有關? 但我還是不知道怎麼做??
: 其實是.. 有的, 而且快到你難以想像.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: 接下來我們探討幾個問題:
: 1. 給定一個 Markov Chain, Stationary probability distribution
:    是否存在?
: Ans: 這問題很大, 在 Random Process 有個章節專門探討這個問題,
: 但在這個題目 ( actually it's a special graph),
: stationary probability distribution 是存在的, 我們之後會證明.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: 2. 請問幾步之後他會收斂到 stationary probability?
: Ans: 這問題也是很大, 因為這牽扯到 Markov Chain mixing time,
: 這是 Markov Chain Monte Carlo 的核心問題, 也.. 難解.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: 但是, 求解 stationary probability distribution 的過程,
: 漂亮的令你難以想像.

Leon提供了一個證明，
證明題目給定的矩陣存在stationary probability distribution，而且很容易證明。
但是Leon完全沒有提到，
這矩陣究竟是幾步之後才會收斂，只說它難解。

至於原問題是問：k步之後，究竟state會變成如何？
Leon提到的這兩個命題，都無法完全解決原問題。
所以Leon並沒有解決原本的問題，只是提供了原問題的其中一些性質。
各位就算跟Leon繼續辯論下去，也得不到原問題的答案的。

至於Leon回文的第一句：「其實是.. 有的, 而且快到你難以想像.」
想必這句話是說錯了，其實他並沒有解決原問題。

照Leon的文章內容來看，
我想原問題應該是滿難解的，
原因是牽扯到 Markov Chain mixing time，
如果要繼續討論的話，從這關鍵字下手，大家應該會比較有交集。

另外我想請教的是，
Leon推文說到這是圖論問題，
那麼目前市面上有沒有哪一本圖論書籍，有涵蓋到這個主題的？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.136.162
※ 編輯: DJWS            來自: 36.225.136.162       (10/31 22:19)
推 singlovesong:MC 應該是stochastic process 的範疇
→ singlovesong:另外我記得mixing time 沒有辦法求吧
→ singlovesong:如果可以求的話我們就知道MCMC要走幾步了
→ Leon:mixing time 是可以算的..
→ Leon:我想我應該停止寫這個主題, 畢竟寫的東西要有人看得懂才有意
→ DJWS:我也覺得這應該是隨機程序　沒想到圖論領域也有人在研究 XD