作者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