※ 引述《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.
(下恕刪)
胡言亂語一下
術業有專攻, 大家切磋切磋.
我自己書念得鬆散, 愧對恩師,
不過還沒有到基礎不足到必得先去補念一堆書再回來討論吧?
這次討論倒是讓我查出幾處過去囫圇而過, 沒有嚴謹弄清楚的地方.