蓄水池问题

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);