Re: [問題] Interview street: zombie march

[Leon (Achilles)]

※ 引述《DJWS (...)》之銘言：
: Leon提供了一個證明，
: 證明題目給定的矩陣存在stationary probability distribution，而且很容易證明。
: 但是Leon完全沒有提到，
: 這矩陣究竟是幾步之後才會收斂，只說它難解。

因為我知道這個一講下去沒人知道我再說甚麼啊,
我想這個版學過 Random process 的人應該不多.

: 至於原問題是問：k步之後，究竟state會變成如何？
: Leon提到的這兩個命題，都無法完全解決原問題。

我想這是重點.

因為時間關係, 我寫文章的時候並沒有把所有條件列出來.

我所提供的方法, 是在考慮困難的情況下 (簡單的我根本不想看)
也就是在 M, N, K 很大的時候,
我怎麼去提供一個近似解.


: 所以Leon並沒有解決原本的問題，只是提供了原問題的其中一些性質。
: 各位就算跟Leon繼續辯論下去，也得不到原問題的答案的。
: 至於Leon回文的第一句：「其實是.. 有的, 而且快到你難以想像.」
: 想必這句話是說錯了，其實他並沒有解決原問題。

在研究的路程上, 通常你只能得到 heurisitic solution,
並且你只能解一步狀況下的問題..

我想, 公平的說, 我不用解 eignvalue, eign-vector
就能得到 stationary probability.
在這點的進展, 並且引起討論這是我樂於見到的.

我倒是很期待有人能放上更好的解法.
你要不要試試看?


: 照Leon的文章內容來看，
: 我想原問題應該是滿難解的，
: 原因是牽扯到 Markov Chain mixing time，
: 如果要繼續討論的話，從這關鍵字下手，大家應該會比較有交集。
: 另外我想請教的是，
: Leon推文說到這是圖論問題，
: 那麼目前市面上有沒有哪一本圖論書籍，有涵蓋到這個主題的？

這個問題夯的很呢,
去 google Markov Chain mixing time, random walk, gossip algorithm

連 S. Boyd 都在這個領域發過文章.


這個人寫的論文比較淺顯,
也有例子, 你也可以在 page 15 以後找到他推論 mixing time 的公式

http://keithbriggs.info/documents/Min_Chen_MSc.pdf

教科書, 通常都是要晚個好幾年....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.170.76.59
推 DJWS:我想推文的人都應該有看懂你在說什麼  只是你可能中文不好
→ DJWS:一直沒辦法理解大家想討論一個確切解　而非近似解
→ DJWS:至於你提供近似解也是一個方向　不過也應該一開始就講明了
→ DJWS:免得大家搞不清楚你究竟想不想解決原問題
→ Leon:我會寫那些東西, 是因為有人說可以觀察 eignvalue..
→ Leon:Based on what you said on ``eignvalue'', I suppose you
→ Leon:already accept the assumption on Markov Chain
→ Leon:anyway, I don't think it's good to discuss this topic
→ Leon:since not many people know about the concept
推 DJWS:是我提出來的 我當然知道呀...求eigenvalue是NP-hard
→ DJWS:所以我才說這個方法參考看看就好
→ DJWS:還有你eigenvalue打錯字了 XD
→ Leon:你.. 是112的嗎? eigenvalue 是 NP-hard ????
→ Leon:我.. 竟然浪費了時間和這群人討論....
→ Leon:我除了這篇留給你看之外, 其他的我全砍了..
推 singlovesong:DJ大口誤吧XDD
→ neutrino:"提到eigenvalue"是指我嗎? 我聽過(在你給的這份文件Ch4
→ neutrino:也有提到, 不過我還沒時間細看這份)那個second large
→ neutrino:eigenvalue與mixing rate的方法 才提起來的
→ neutrino:eigen decompose我只知道O(n^3), 所以我想請教mixing
→ neutrino:time有什麼好進展. 畢竟自己不是做隨機這方面領域的,
→ neutrino:自然希望有更多關鍵字指引, 不然MC,mixing time的文章
→ neutrino:對不是鑽這領域的人來說, 可太多了...
推 DJWS:就因式分解是NP-hard級別的  然後求eigenvalue可以化作多項式
→ DJWS:因式分解  所以求出所有eigenvalue是NP-hard
→ DJWS:因為很難算  所以可以用內插法、牛頓法等等的近似演算法求根
→ DJWS:所以我們可以用P-time求得一個根  目前所有的eigen-decomposi
→ DJWS:tion的演算法，都是基於近似演算法的
→ DJWS:這段是之前從別人blog看到的  如果我的理解有誤請告訴我
推 DJWS:另外就是  我並不覺得跟你討論是浪費時間  還是能學到新觀念
推 DJWS:只是你講的內容實在偏離原問題太多  使得大家沒共識而已...
→ DJWS:抱歉...第一句話開頭請改成「多項式因式分解是NP-hard級別」
→ suhorng:可不可以題外話問一下XD 像這種求解出來可能是什麼根號
→ suhorng:什麼奇怪的實數的問題 我們說計算時間一般是指什麼的的時
→ suhorng:間? 比如 (-b+-sqrt(b^2-4ac))/(2a), 是忽略那sqrt時間嗎?
推 DJWS:如果是說big-O notation的話  只留下成長最快的那一項就可以
→ suhorng:噢, 我說得不太清楚, 這樣問好了
→ suhorng:我們說計算這個的時間複雜度 是指計算近似值到某特定精度
→ suhorng:的演算法的複雜度嗎?ZY
→ DJWS:然後學理上的計算時間  就是演算法的步驟數目
→ DJWS:喔喔 我開始理解你想問什麼了 XD
→ suhorng:耶XD
推 DJWS:時間複雜度和複雜度分類，"應該"是指計算確切值吧!
→ DJWS:至於近似演算法也有自己的複雜度分類
→ DJWS:例如PTAS的就是指可以P-time得到近似解  誤差小於一定範圍
→ suhorng:喔喔~感謝!
→ DJWS:我不是很懂複雜度分析  所以有錯還請板友指正  謝謝!
→ suhorng:我大概知道跟我想的差在哪理了
→ suhorng:有的近似值演算法只能保證算出來答案 與正確值在某一誤差
→ suhorng:範圍內
→ DJWS:至於eigenbasis實際上是可以無限趨近正確答案的
→ suhorng:有的則是可以依要求 花不同時間作到近似到任意精度
→ suhorng:大概是這樣?
→ DJWS:所以把它分類成P問題  好像也是可以 (?)
→ DJWS:對阿  我的理解是這樣!
→ suhorng:謝謝:D
→ Leon:你如果不懂的話還是少說點話.. 免得誤導別人
→ Leon:另外, 我認為你連complexity基礎都沒有, 講甚麼也無用
→ Leon:我建議你把你上面解釋 ``eigenvalue is NP-hard'' 那段話
→ Leon:寫下來, 拿去給 CSIE 教演算法的老師看看,
→ Leon:試著說服他你上面那段話
※ 編輯: Leon            來自: 76.169.145.122       (11/02 05:00)
推 DJWS:我的確沒有complexity基礎  有機會我會請教專業人士
→ DJWS:如果你能講解的話  那就更好了!
→ DJWS:另外你應該是學者吧  想請教你是從事哪個領域的研究
→ DJWS:知道領域範疇的話  討論起來比較有交集 / 我自己並不是學者
→ Leon:去修課比較快
推 DJWS:那麼樓上修過complexity的課嗎？我想知道complexity有哪本教
→ DJWS:科書有提到eigenvalue的時間複雜度...我找滿久的都找不到 orz
→ Leon:Take class first, because you even don't know the def
→ suhorng:定義不是查一查就知到了嗎... DJWS大顯然一定知道呀
→ stimim:我覺得 DJWS 說的應該是求 exact value ，而不是數值解
→ stimim:也就是答案如果是 sqrt(2) ，就不能輸出 1.414...
→ suhorng:那可能是個滿弔詭的地方. sqrt(2)可以看成一個演算法, 輸
→ suhorng:出 x^2 - 2 = 0 的正根到任意精度位
→ suhorng:而一般任意五次或以上方程式, 其解沒有通用的方法用係數
→ suhorng:的加減乘除及某些次方根來表示
→ suhorng:所以是必要用其他的表示法 就看接不接受
→ Leon:我認為DJWS寫的東西, 與Matrix computation談的complexity
→ Leon:定義完全不同, 所以我建議他去修課, 看看別人怎麼定義問題
→ Leon:不然就把自己的定義寫成文章投稿 解釋`eigenvalue is NP-hard
→ Leon:順便給樓上兩位: finite state machine 怎麼表示 irrational
→ Leon:number? 有辦法 exactly 表示 [0,1] 間的 irrational number?
推 stimim:我對電腦中的exact value的理解是要像mathematica那樣，
→ stimim:1/3 他就寫 1/3 ，sqrt(2) 他就寫 sqrt(2)，pi 就是 pi
推 DJWS:所以你也沒修過complexity囉？ 那麼等我問到，我再教你。
→ DJWS:如果你有管道可以問的話　也請你幫忙問一下  謝謝!
推 suhorng:話說, Mathematica 能對於任意正整數 n, 都給出
→ suhorng:x^5 + x - n = 0 的解的 exact value 嗎?
→ suhorng:我手邊只有 Maple, 可是不知道怎麼下指令..|||
推 FRAXIS:我覺得現在好像是在討論eigenvalue是不是computable number
→ FRAXIS:http://en.wikipedia.org/wiki/Computable_real
→ suhorng:是好像有這種味道XDDD
→ Leon:我認為 DJWS 寫的東西還是不要看比較好, 對知識長進有害
→ Leon:你先去念 CLRS 的 algorithm, 再去看 Golomb 的 matrix
→ Leon:Computation, 另外, 敢上來嗆人就得先學會 google, 不是嘛?
推 DJWS:那我大概有個底了 我想你應該是做訊號方面的!
→ DJWS:CLRS我整本都讀過了  至於矩陣運算我真的不熟
→ DJWS:還有就是關於eigenvalue的問題  我昨天努力google了很久
→ DJWS:多項式因式分解是P  包括有理數/代數擴展 http://ppt.cc/vnOA
→ DJWS:特徵多項式是GapL  http://ppt.cc/xBLC
→ DJWS:特徵多項式事實上也有P演算法 http://ppt.cc/T_E3
→ DJWS:求eigenvalue其實就是對特徵多項式作因式分解  故推論為P
→ DJWS:至於求eigenvector、求eigenbasis的部分我還沒找到資料
→ DJWS:所以我的推文確實推錯了  求eigenvalue是P才對! 不好意思...
推 DJWS:另外想問 Golomb 的 matrix 是哪一本書？ 因為找不到書名裡
→ DJWS:有 martix 的...
推 FRAXIS:Eigenvalue的複雜度可以參考這篇論文
→ FRAXIS:The complexity of the matrix eigenproblem, STOC 1999
推 FRAXIS:至於書的話 我猜他是在說Matrix Computations, by Golub
推 DJWS:謝謝樓上! 有空來去圖書館翻一翻