之前接触到一道面试题大概是这样的：
给你一个大文件，里面每一行包含一个字符串，设计一种算法随机返回k个字符串，要求每一个字符串返回的概率相同.
果断选择看下一题… 而最近在做Algorithm part1 week2的作业中bonus竟然涉及到了这个问题，没想到竟然是一种算法。于是学习了一番，并再次感叹Algorithm真是门神课…
以下的证明是我在网上看到过的最易理解的。同时根据自己的理解修改了一部分
问题简化到k=1
首先我们考虑k=1时的情况。
设当前读取的是第n个元素，采用归纳法分析如下：
- n = 1 时，只有一个元素，直接返回即可，概率为1。
- n = 2 时，前两个元素被选择的概率是相等的，也就是$\frac{1}{2}$。因此可以在[0,2)中随机选取一个整数i，如果i<1就返回第二个元素，否则返回第一个。
- n = 3 时，要求每个元素返回的概率为1/3。注意此时前两个元素留下来的概率均为1/2。做法是：生成一个[0,3)的随机整数i，若i<1，则返回第三个，否则返回上一步留下的那个。元素1和2留下的概率均为：$\frac{1}{2} * (1-\frac{1}{3}) = \frac{1}{3}$，即上一步留下的概率乘以这一步留下（即元素3不留下）的概率。
- …
- 假设 n = m 时，前n个元素留下的概率均为：$\frac{1}{m}$
- 那么当 n = m+1 时，生成[0,m+1)之间的随机整数i并判断i是否小于1，若是则留下元素m+1，否则留下上一步留下的元素。这样一来，元素m+1留下的概率为$\frac{1}{m+1}$，前m个元素留下来的概率均为：$\frac{1}{m}* (1 - \frac{1}{m+1}) = \frac{1}{m+1}$，也就是$\frac{1}{n}$
- 综上可知，算法成立。
问题二
将问题一中的条件变为，k为任意整数的情况，即要求最终返回的元素有k个，这就是水塘抽样（Reservoir Sampling）问题。要求是：取到第n个元素时，前n个元素被留下的几率相等，即k/n。
- 当n$\leq$k时，则可直接加入水塘中，此时概率为1
- n=k+1，第k+1个被选中的概率为$\frac{k}{k+1}$. 对于前k个元素中的任意一个i分析，他留下来的概率为：上一步留下来的概率*[1-(第k+1个留下来的概率*替换i的概率)].也就是$1(1-\frac{k}{k+1} \frac{1}{k})$ = $\frac{k}{k+1}$
- 假设n=m时，每个元素留下的概率均为 $\frac{k}{m}$.
- 那么，当 n = m+1时，第m+1个元素留下的概率为$\frac{k}{m+1}$，前m个元素留下的概率均为：$\frac{k}{m}(1-\frac{k}{m+1} \frac{1}{k})$ = $\frac{k}{m+1}$
- 综上可知，算法成立。