※ 引述《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