首页 > 代码库 > 蓄水池问题

蓄水池问题

for i in [n+1 N]
  M=rand(1,i)
  if(M<=n)
    swap the ith and Mth data

证明方法:

1.初始情况,当尚未选择时,出现在pool中的n个元素的概率相同都是1,证明当第n+1葛元素以n/(n+1)的概率

被选中时,前n个元素在pool中的概率为n/(n+1)即可;

即任意元素被替换的概率为:n/(n+1)*1/n=1/(n+1)

所以前n个元素被替换的概率为n/(n+1)

1.假设当第i个元素以n/i的概率选中时,前i-1个元素被选中的概率同样n/i

2.证明当第i+1个元素以n/(i+1)的概率选中时,前i个元素被选中的概率同样为n/(i+1)

证明:第i+1个元素的情况为:前i个元素被选中的概率有两种情况:

a:如果第i+1次选择之前,这i个元素在pool中,有假设可知,前ige元素被选中的概率为n/i

b:第i+1此选择没有替换掉现在pool中元素:

先算任意元素被替换的概率:(n/(i+1))*(1/n)=1/(i+1)

因此没有被替换掉的概率为:1-1/(i+1)=i/(i+1)

ab相乘为:n/i*i/(i+1)=n/(i+1);