※ 引述《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.
(下恕删)
胡言乱语一下
术业有专攻, 大家切磋切磋.
我自己书念得松散, 愧对恩师,
不过还没有到基础不足到必得先去补念一堆书再回来讨论吧?
这次讨论倒是让我查出几处过去囫囵而过, 没有严谨弄清楚的地方.