蓄水池问题

https://blog.csdn.net/Code_LT/article/details/87626770

---

> 从n个数中随机采样出1个数

我们总是选择第一个对象，以1/2的概率选择第二个然后替换第一个，以1/3的概率选择第三个然后替换第二个，以此类推，以1/m的概率选择第m个对象。当该过程结束时，每一个对象具有相同的选中概率，即1/n

> 从n个数中随机采样k个数

从n个数中随机采样k个数。可以类似的思路解决。先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n，证明如下