Chinaunix首页 | 论坛 | 博客
  • 博客访问: 772844
  • 博文数量: 217
  • 博客积分: 2401
  • 博客等级: 大尉
  • 技术积分: 2030
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-16 06:58
个人简介

怎么介绍?

文章分类

全部博文(217)

文章存档

2023年(2)

2022年(3)

2021年(29)

2020年(12)

2019年(5)

2018年(5)

2017年(5)

2016年(3)

2015年(6)

2014年(12)

2013年(16)

2012年(9)

2011年(6)

2010年(15)

2009年(30)

2008年(59)

我的朋友

分类:

2009-01-10 07:11:13

You have N balls with N different colors. Randomly you draw two at a time, then painting the first ball to match the second. What is the expected 
number of drawings before all balls are the same color?

Here is what I found so far:
# of balls ------ E(# of drawings)
2 ------ 1
3 ------ 4
4 ------ 9

N ------ (N-1)^2 ???


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.

阅读(676) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~