i***q
发帖数: 1095 | 1 Suppose that balls are tossed into b bins. Each toss is independent, and
each ball is equally likely to end up in any bin. What is the expected
number of ball tosses before at least one of the bins contains two balls? | z****e
发帖数: 2024 | 2 number of ball tosses before at least one of the bins contains two balls
注意，这里要的是before。就是 step to reach one of the bins contains two
balls 再减一。
解析结果是：
\sum_{k=1}^{b-1}\frac{(b-1)!/(k-1)!}{b^(b-k)}+1
或者写成：
求和从k=1到b-1,求和对象：[(b-1)!/(k-1)!]/b^(b-k)。求和以后加一，就是所要结果。
数值模拟：
%matlab simulation for b=25;
b=25;
NT=5000;
samplesum=0;
for i=1:NT
counter=0;
arrbin=zeros(1,b);
while 1
counter=counter+1;
tossbin=ceil(rand()*b);
arrbin(tossbin)=arrbin(tossbin)+1;
if max(arrbin)==2
break; | z****e
发帖数: 2024 | 3 几个结果：
b=1, step number 1.
b=10, step number 3.66.
b=15, step number 4.55.
b=30, step number 6.55.
key hint:
N_k=k/b+(b-k)/b*(N_{k+1}+1)=(b-k)/b*N_{k+1}+1; |
|
