怎么介绍?
分类:
2009-01-10 07:11:13
Let X_n be the number of ball with color 1,
F be the even that all balls will end up with color 1,
that is F={X_N=n for some N}.
N=N(F)=min{m|X_m=n}.
Now we are going to prove E(N|X_0=1,F)=(n-1)^2.
First calcalate p_{i,i+1}=P(X_{k+1}=i+1 |X_k=i, F).
we can get
p_{i,i+1}=P(X_{k+1}=i+1| X_k=i,F)
=P(X_{k+1}=i+1,F|X_k=i)/P(F|X_k=i)
=P(X_{k+1}=i+1|X_k=i}*P(F|X_{k+1}=i+1,X_k+i)/P(F|X_k=i)
=P(X_{k+1}=i+1|X_k=i}*P(F|X_0=i+1)/P(F|X_0=i),
we can prove P(X_{k+1}=i+1|X_{k}=i}=i*(n-i)/(n(n-1)),
P(F|X_0=i)=i/n,
so we can get p_{i,i+1}=(i+1)*(n-i)/(n(n-1)),
similiar we get p_{i,i-1}, and p_{i,i}.
Let N_i=E[N|X_0=i,F], then we can prove
N_i-1=N_{i+1}*p_{i,i+1}+N_i*p_{i,i}+N_{i-1}*p_{i,i-1}
just solve the above recursive equation with N_n=0,
we get N_1=(n-1)^2.