2010年8月6日星期五

一道问题

好吧,这个博客好久不学术了,那就来伪学术一下...

假设有N个小球,分别标记上1, 2, ..., N。然后执行下面的操作:每一步,随机先后抽出两个小球,把第一个小球的标记修改成第二个小球的标记,再把它们放回去,如此反复,直到所有小球的标记都变成同一个数。问达到此状态所需要的步数的数学期望是多少?

经过一系列并不简单的计算,可以证明,答案是(N-1)^2。我的问题是,不知道对这个结果有没有更简短、更漂亮的解释?

(目前能想到的证明的大致过程:首先不妨假设最后所有小球的标记都变成1。令X_n=第n步后标记为1的小球个数,则X_n是Markov链。可以写出在“X_n在到达0之前先到达N”(即最后所有小球标记都为1)这个条件下的条件转移概率,进而列出过程X从不同的点出发,到达N所需步数的期望的递推方程,并解这个线性方程组。)

没有评论: