作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] Interview street: zombie march
時間Wed Oct 31 23:58:22 2012
※ 引述《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
1F：推 DJWS:我想推文的人都應該有看懂你在說什麼 只是你可能中文不好 11/01 00:11
2F：→ DJWS:一直沒辦法理解大家想討論一個確切解 而非近似解 11/01 00:11
3F：→ DJWS:至於你提供近似解也是一個方向 不過也應該一開始就講明了 11/01 00:13
4F：→ DJWS:免得大家搞不清楚你究竟想不想解決原問題 11/01 00:13
5F：→ Leon:我會寫那些東西, 是因為有人說可以觀察 eignvalue.. 11/01 00:58
6F：→ Leon:Based on what you said on ``eignvalue'', I suppose you 11/01 00:59
7F：→ Leon:already accept the assumption on Markov Chain 11/01 00:59
8F：→ Leon:anyway, I don't think it's good to discuss this topic 11/01 01:00
9F：→ Leon:since not many people know about the concept 11/01 01:00
10F：推 DJWS:是我提出來的 我當然知道呀...求eigenvalue是NP-hard 11/01 07:53
11F：→ DJWS:所以我才說這個方法參考看看就好 11/01 07:53
12F：→ DJWS:還有你eigenvalue打錯字了 XD 11/01 07:54
13F：→ Leon:你.. 是112的嗎? eigenvalue 是 NP-hard ???? 11/01 08:22
14F：→ Leon:我.. 竟然浪費了時間和這群人討論.... 11/01 08:23
15F：→ Leon:我除了這篇留給你看之外, 其他的我全砍了.. 11/01 08:27
16F：推 singlovesong:DJ大口誤吧XDD 11/01 09:25
17F：→ neutrino:"提到eigenvalue"是指我嗎? 我聽過(在你給的這份文件Ch4 11/01 10:57
18F：→ neutrino:也有提到, 不過我還沒時間細看這份)那個second large 11/01 10:58
19F：→ neutrino:eigenvalue與mixing rate的方法 才提起來的 11/01 10:58
20F：→ neutrino:eigen decompose我只知道O(n^3), 所以我想請教mixing 11/01 11:01
21F：→ neutrino:time有什麼好進展. 畢竟自己不是做隨機這方面領域的, 11/01 11:02
22F：→ neutrino:自然希望有更多關鍵字指引, 不然MC,mixing time的文章 11/01 11:03
23F：→ neutrino:對不是鑽這領域的人來說, 可太多了... 11/01 11:04
24F：推 DJWS:就因式分解是NP-hard級別的 然後求eigenvalue可以化作多項式 11/01 15:44
25F：→ DJWS:因式分解 所以求出所有eigenvalue是NP-hard 11/01 15:44
26F：→ DJWS:因為很難算 所以可以用內插法、牛頓法等等的近似演算法求根 11/01 15:45
27F：→ DJWS:所以我們可以用P-time求得一個根 目前所有的eigen-decomposi 11/01 15:46
28F：→ DJWS:tion的演算法，都是基於近似演算法的 11/01 15:47
29F：→ DJWS:這段是之前從別人blog看到的 如果我的理解有誤請告訴我 11/01 15:48
30F：推 DJWS:另外就是 我並不覺得跟你討論是浪費時間 還是能學到新觀念 11/01 15:59
31F：推 DJWS:只是你講的內容實在偏離原問題太多 使得大家沒共識而已... 11/01 16:04
32F：→ DJWS:抱歉...第一句話開頭請改成「多項式因式分解是NP-hard級別」 11/01 16:07
33F：→ suhorng:可不可以題外話問一下XD 像這種求解出來可能是什麼根號 11/01 19:24
34F：→ suhorng:什麼奇怪的實數的問題 我們說計算時間一般是指什麼的的時 11/01 19:25
35F：→ suhorng:間? 比如 (-b+-sqrt(b^2-4ac))/(2a), 是忽略那sqrt時間嗎? 11/01 19:25
36F：推 DJWS:如果是說big-O notation的話 只留下成長最快的那一項就可以 11/01 22:03
37F：→ suhorng:噢, 我說得不太清楚, 這樣問好了 11/01 22:05
38F：→ suhorng:我們說計算這個的時間複雜度 是指計算近似值到某特定精度 11/01 22:05
39F：→ suhorng:的演算法的複雜度嗎?ZY 11/01 22:06
40F：→ DJWS:然後學理上的計算時間 就是演算法的步驟數目 11/01 22:06
41F：→ DJWS:喔喔 我開始理解你想問什麼了 XD 11/01 22:07
42F：→ suhorng:耶XD 11/01 22:07
43F：推 DJWS:時間複雜度和複雜度分類，"應該"是指計算確切值吧! 11/01 22:09
44F：→ DJWS:至於近似演算法也有自己的複雜度分類 11/01 22:11
45F：→ DJWS:例如PTAS的就是指可以P-time得到近似解 誤差小於一定範圍 11/01 22:13
46F：→ suhorng:喔喔~感謝! 11/01 22:14
47F：→ DJWS:我不是很懂複雜度分析 所以有錯還請板友指正 謝謝! 11/01 22:14
48F：→ suhorng:我大概知道跟我想的差在哪理了 11/01 22:14
49F：→ suhorng:有的近似值演算法只能保證算出來答案 與正確值在某一誤差 11/01 22:14
50F：→ suhorng:範圍內 11/01 22:14
51F：→ DJWS:至於eigenbasis實際上是可以無限趨近正確答案的 11/01 22:14
52F：→ suhorng:有的則是可以依要求 花不同時間作到近似到任意精度 11/01 22:15
53F：→ suhorng:大概是這樣? 11/01 22:15
54F：→ DJWS:所以把它分類成P問題 好像也是可以 (?) 11/01 22:15
55F：→ DJWS:對阿 我的理解是這樣! 11/01 22:16
56F：→ suhorng:謝謝:D 11/01 22:17
57F：→ Leon:你如果不懂的話還是少說點話.. 免得誤導別人 11/02 00:45
58F：→ Leon:另外, 我認為你連complexity基礎都沒有, 講甚麼也無用 11/02 01:09
59F：→ Leon:我建議你把你上面解釋 ``eigenvalue is NP-hard'' 那段話 11/02 01:32
60F：→ Leon:寫下來, 拿去給 CSIE 教演算法的老師看看, 11/02 01:32
61F：→ Leon:試著說服他你上面那段話 11/02 01:32
※ 編輯: Leon 來自: 76.169.145.122 (11/02 05:00)
62F：推 DJWS:我的確沒有complexity基礎 有機會我會請教專業人士 11/02 08:55
63F：→ DJWS:如果你能講解的話 那就更好了! 11/02 08:56
64F：→ DJWS:另外你應該是學者吧 想請教你是從事哪個領域的研究 11/02 08:57
65F：→ DJWS:知道領域範疇的話 討論起來比較有交集 / 我自己並不是學者 11/02 08:58
66F：→ Leon:去修課比較快 11/03 03:42
67F：推 DJWS:那麼樓上修過complexity的課嗎？我想知道complexity有哪本教 11/03 09:25
68F：→ DJWS:科書有提到eigenvalue的時間複雜度...我找滿久的都找不到 orz 11/03 09:26
69F：→ Leon:Take class first, because you even don't know the def 11/03 13:00
70F：→ suhorng:定義不是查一查就知到了嗎... DJWS大顯然一定知道呀 11/03 15:32
71F：→ stimim:我覺得 DJWS 說的應該是求 exact value ，而不是數值解 11/03 15:35
72F：→ stimim:也就是答案如果是 sqrt(2) ，就不能輸出 1.414... 11/03 15:37
73F：→ suhorng:那可能是個滿弔詭的地方. sqrt(2)可以看成一個演算法, 輸 11/03 15:51
74F：→ suhorng:出 x^2 - 2 = 0 的正根到任意精度位 11/03 15:52
75F：→ suhorng:而一般任意五次或以上方程式, 其解沒有通用的方法用係數 11/03 15:52
76F：→ suhorng:的加減乘除及某些次方根來表示 11/03 15:53
77F：→ suhorng:所以是必要用其他的表示法 就看接不接受 11/03 15:53
78F：→ Leon:我認為DJWS寫的東西, 與Matrix computation談的complexity 11/03 15:58
79F：→ Leon:定義完全不同, 所以我建議他去修課, 看看別人怎麼定義問題 11/03 15:59
80F：→ Leon:不然就把自己的定義寫成文章投稿 解釋`eigenvalue is NP-hard 11/03 16:00
81F：→ Leon:順便給樓上兩位: finite state machine 怎麼表示 irrational 11/03 16:06
82F：→ Leon:number? 有辦法 exactly 表示 [0,1] 間的 irrational number? 11/03 16:07
83F：推 stimim:我對電腦中的exact value的理解是要像mathematica那樣， 11/03 16:09
84F：→ stimim:1/3 他就寫 1/3 ，sqrt(2) 他就寫 sqrt(2)，pi 就是 pi 11/03 16:10
85F：推 DJWS:所以你也沒修過complexity囉？ 那麼等我問到，我再教你。 11/03 18:46
86F：→ DJWS:如果你有管道可以問的話 也請你幫忙問一下 謝謝! 11/03 18:51
87F：推 suhorng:話說, Mathematica 能對於任意正整數 n, 都給出 11/03 19:41
88F：→ suhorng:x^5 + x - n = 0 的解的 exact value 嗎? 11/03 19:42
89F：→ suhorng:我手邊只有 Maple, 可是不知道怎麼下指令..||| 11/03 19:42
90F：推 FRAXIS:我覺得現在好像是在討論eigenvalue是不是computable number 11/03 20:30
92F：→ suhorng:是好像有這種味道XDDD 11/03 20:34
93F：→ Leon:我認為 DJWS 寫的東西還是不要看比較好, 對知識長進有害 11/04 01:12
94F：→ Leon:你先去念 CLRS 的 algorithm, 再去看 Golomb 的 matrix 11/04 01:13
95F：→ Leon:Computation, 另外, 敢上來嗆人就得先學會 google, 不是嘛? 11/04 01:14
96F：推 DJWS:那我大概有個底了 我想你應該是做訊號方面的! 11/04 10:35
97F：→ DJWS:CLRS我整本都讀過了 至於矩陣運算我真的不熟 11/04 10:37
98F：→ DJWS:還有就是關於eigenvalue的問題 我昨天努力google了很久 11/04 10:37
102F：→ DJWS:求eigenvalue其實就是對特徵多項式作因式分解 故推論為P 11/04 10:43
103F：→ DJWS:至於求eigenvector、求eigenbasis的部分我還沒找到資料 11/04 10:44
104F：→ DJWS:所以我的推文確實推錯了 求eigenvalue是P才對! 不好意思... 11/04 10:45
105F：推 DJWS:另外想問 Golomb 的 matrix 是哪一本書？ 因為找不到書名裡 11/04 10:58
106F：→ DJWS:有 martix 的... 11/04 10:58
107F：推 FRAXIS:Eigenvalue的複雜度可以參考這篇論文 11/04 20:46
108F：→ FRAXIS:The complexity of the matrix eigenproblem, STOC 1999 11/04 20:46
109F：推 FRAXIS:至於書的話 我猜他是在說Matrix Computations, by Golub 11/04 20:49
110F：推 DJWS:謝謝樓上! 有空來去圖書館翻一翻 11/04 22:39