博文
一个很漂亮的概率题
|
n个不同颜色的球。每次先后随机拿出两个球，把第二个球的颜色染成第一个球的颜色，放回。重复此过程直到所有球的颜色一样。整个过程总共需要的次数的期望是多少？（这个总次数设为T,我们需要计算的是E[T]。）
理论上似乎多维马尔可夫链建模可以解决。停止时刻是一个停时。具体怎么做？混乱中的切入点在哪里？
（1）给n个颜色编号，i=1,2,....,n。k_i(t)表示t时刻具有颜色i的球的个数，i=1,2,....,n。固定某一种颜色i，k_i(t)是一个随机游走，k_i(t+1)可以是k_i(t)+1，k_i(t)－1，或者k_i(t)。
令p(k)=k(n-k)/n(n-1). 如果k_i(t)＝k，那么
k_i(t+1)＝k+1的概率是p(k)；k_i(t+1)＝k-1的概率也是p(k)；k_i(t+1)＝k的概率就是1-2p(k)。
另外，注意到，k_i(t)作为随机游走的对称性而是一个鞅过程（利用这一点可以简化很多计算）。
（2）令A_i为结束时所有球颜色都是i的事件。再令T_i=T* 1_{A_i}. 显然，T_i的分布仅仅依赖于初始时刻具有颜色i的球的个数，而与其他颜色的球的个数的划分无关。
定义ψ(k)=E[T_i |k_i(0)=k],k=0,1,2,....,n。
ψ(k)即是在初始时刻有k个具有颜色i的球的条件下，T_i的期望。显然有，ψ(0)＝ψ(n)＝0。
再由递归想法，有如下递归关系，
ψ(k)＝[1-2p(k)] ψ(k)+p(k) ψ(k+1)+
p(k) ψ(k-1)+E[ 1_{A_i} |k_i(0)=k]
（3）E[ 1_{A_i} |k_i(0)=k]也就是
P[ A_i|k_i(0)=k]。这个值可以直接计算。由均匀性，可以猜测P[ A_i|k_i(0)=k]＝k/n。
怎么证明呢？利用k_i(t)是一个有界鞅及选时停止定理即可(0和n是吸收壁)，
k_i(0)=E[k_i(T)]=0*P[k_i(T)=0]+n*P[k_i(T)=n]。所以，P[k_i(T)=n]＝k_i(0)/n。
（4）把P[ A_i|k_i(0)=k]＝k/n代入步骤（2）最后的递归方程，我们可以得到一个差分方程，经过一些处理可以得到ψ(k)的显式解。特别地，
ψ(1)＝(n-1)^2/n.
所以，E[T]=∑_{i=1,2,...,n}E[T* 1_{A_i}]=∑_{i=1,2,...,n}ψ(1)=(n-1)^2。
很多看似初等的小问题，也是需要借助一些稍微高级一些的概念来帮助思考的。角度重要，混乱中找到相对有序的突破口，这需要一些无招的能力，虽然不是在很高层面的无招。
https://blog.sciencenet.cn/blog-1213200-857886.html
上一篇：关于测度的弱收敛
下一篇：点过程的随机积分理论框架
