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

Re: [問題] Interview street: zombie march

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

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

※ 引述《seanwu (sean)》之銘言： : ※ 引述《Leon (Achilles)》之銘言： : : 因為我知道這個一講下去沒人知道我再說甚麼啊, : : 我想這個版學過 Random process 的人應該不多. : 少瞧不起鄉民，我想會看這個板的，學過或聽得懂的人應該不少 :) : : 我想這是重點. : : 因為時間關係, 我寫文章的時候並沒有把所有條件列出來. : : 我所提供的方法, 是在考慮困難的情況下 (簡單的我根本不想看) : : 也就是在 M, N, K 很大的時候, : : 我怎麼去提供一個近似解. : 你可能誤會大家解題的討論方向了，所謂解題是要在題目給定的條件下，找出正確的答案 : 實務上求個近似解當然是不過份，不過照第一篇推文的方向來看，應該不是這樣就滿足了 : 另外老實說，你那個其實是簡單的情況，你的證明大家也都懂了 : 並沒有人說你列的證明有問題，只是你忽略了某些條件 (比方說k的值) : 這樣一來問題是變簡單解得掉了沒錯，不過你解的就不是原本的問題 : 比如我宣稱我會做integer linear programming，可是忽略掉integer一樣 : 那我做完了四捨五入，然後說這是個不錯的近似解，這樣... 沒問題嗎? 這個題目, 要用stationary distribution來解k很大的case是ok. 但若如此, 是不是得定出 "how to decide k is large enough"? 總不能自己隨便定個threshold, 比方k < 10^4 就直接simulate 這樣吧. 那就需要求或估計mixing time 但是求mixing time 在我原本的認識也很困難... (所以才要請教啊!?) 如果少了這個環節(判斷input是否k夠大so that能用這個解), 並不完整. 再來, 關於bipartite graph (導致periodicity) 我看到不少Markov chain的相關paper, 都在前提先claim他討論aperiodic chain; 但是對於其他領域的人來說, 有很多感興趣的graph都是bipartite... tree當然都是bipartite, grid也是bipartite 這個題目講街道, 街道當然通常不是bipartite, 但是說到街道, 我猜應該至少有些人和我一樣, 心裡具象化的第一個簡化特例是grid. (下恕刪) 胡言亂語一下術業有專攻, 大家切磋切磋. 我自己書念得鬆散, 愧對恩師, 不過還沒有到基礎不足到必得先去補念一堆書再回來討論吧? 這次討論倒是讓我查出幾處過去囫圇而過, 沒有嚴謹弄清楚的地方. --- 還有一個衍生問題再請問有沒有人能釐清一下, 我不放心基礎不穩, 查了幾個地方, stationary distribution的定義讓P 是transition π = πP πis the stationary distribution 於是 "stationary distribution 存在" if and only if "irreducible and positive recurrent" (我的理解)沒有要求要aperiodic. "aperiodic and positive recurrent" => ergodic 應該是這樣? 這樣的話berkeley 那份講義沒有寫錯呀, 引入self loop不改變stationary distribution, 對bipartite graph還是成立呀? e.g. 三個點的path, π(0.25, 0.5, 0.25)就是滿足π = πP -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.87.142.18