随机抽样有关问题（蓄水池有关问题）

随机抽样问题（蓄水池问题）

     本文整理了一些博客的思路：

                 http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html

                            http://blog.csdn.net/fanzitao/article/details/7930886

问题定义

      我们常常碰到如下几个问题：

  （1）在不知道文件总行数的情况下，如何从文件中随机的抽取一行？

   上面的问题，我们并不知道文件有多大，如果知道了，我们就可以利用传统的rand()来生成一个随机数，然后选取相应的记录出来就行了。那么如果不知道文件的大小的时候，我们需要一个概念来帮助我们做出猜想，来使得对每一行取出的概率相等，也即随机。这个概念即蓄水池抽样（Reservoir Sampling）。

  （2）给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

  （3）从给定一个未知长度的整数流，如何随机选取一个数；

蓄水池抽样问题

1.问题1和2的解答

  对于第（1）（2）个问题其实是一个问题。我们首先定义取出的行号为choice，第一次直接以第一行作为取出行 choice ，而后第二次以二分之一概率决定是否用第二行替换 choice ，第三次以三分之一的概率决定是否以第三行替换 choice ……，以此类推，可用伪代码描述如下：

   （3）那么最后，第i个元素被选中的概率为多少呢？

   （4）得证。看不懂，可以参考：http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
           情况2：第i+1到n的选择中，根本没有选中前面的k个元素之一，此时的概率为：
     总结上两种情况，第j个元素选不中j的概率为：
    （3）这样，第i个元素被最后选中的概率就可以想了：第i个元素在第i池选择中被选择进入蓄水池，而从i+1到n过程中都没有选中i，把i从蓄水池中交换出去，这样i就一直留在蓄水池中。
    （4）此时，已全部得证。看不懂，参考：http://blog.csdn.net/fanzitao/article/details/7930886