今天在知乎上看到一道阿里的面试题，问题是：

请设计一个抽奖算法，得奖名额设定为100人，在不知道有多少人参与抽奖活动前提下，且保证不同时间的人中奖概率相同，同时不能让太多的人等待结果，防止网络拥塞。

原题链接：https://www.zhihu.com/question/35099557

看到题目立马想到的就是水塘抽样，但是水塘问题不能解决同时不能让太多的人等待结果，不知道是不是提问者转述有问题，姑且不考虑这个要求，过程中可以直接通知没有抽中的人，以下就只是介绍下水塘抽样。

水塘抽样的典型场景

设计一个抽奖系统，参与的人数$N$在抽奖结束之前是不知道的，要从中选$k$个幸运儿，这样就有两种情况：

• 如果人很少的话，就无所谓了，我们可以很快地设计一个随机函数your_rand来很快从$[0,N)$中产生$k$个不重复的数就可以了。
• 如果人很多，那么设计一个高效的your_rand就会成为一个不小的挑战，需要考虑空间和时间复杂度。

水塘抽样就专门为这个而生，水塘抽样是线上算法，可以进行流式计算，复杂度是$O(n)$。

水塘抽样的由来的思考

水塘抽样问题很久之前就由Knuth在The Art of Computer Programming（TAOCP）中提出来的。因为TAOCP这本巨著太过庞大，一直不敢读，所以Knuth的具体的思考过程也就不是很了解，下面是我自己的一些思考。以下分简化情况和一般情况来看：

简化：只抽取一位幸运儿

在这种情况，我们可以得到一个简化的问题，即：

一个装有N个小球的桶中，有一个黑球，安排N个人去抽，那么每个人抽到黑球的概率是多少？

这个模型，只要学过基础的概率论的伙伴们应该都很熟悉，当时老师肯定用这个模型的来论证过无论先抽还是后抽，每次抽到黑球的概率是一致的，比如你去抽福利彩票，不会因为你去晚了就比人家机会小。让我们来看下证明过程：

• step1:考虑第一个球被抽取到的概率是$\frac{1}{N}$
• step2:考虑第二个球被抽到的概率，第二个球能被抽取到，只有在第一个球没有抽到的情况下才能抽到，那么概率就是:$\frac{N-1}{N}*\frac{1}{N-1}=\frac{1}{N}$
• step3:类似，也是$\frac{1}{N}$
• …
• stepN-1:概率是 $\frac{N-1}{N}*\frac{1}{N-1} …\frac{2}{3}{*}\frac{1}{2}=\frac{1}{N}$
• stepN: $\frac{N-1}{N}{*}\frac{1}{N-1} … \frac{2}{3}{*}\frac{1}{2}{*}{1}=\frac{1}{N}$

我们就得到了通项：

每一项的概率都是一样的，很棒！但是我们在线上抽样的时候，无法知道$N$是多少，但是这难不倒我们，尝试做一个简单的变换，令$n^{\prime}=N-(n-1)$，因为对于每一次抽取，概率都是一样的，所以做完这个变换后的概率仍然是$\frac{1}{N}$。代入原来的式子，可以得到：

这样,$P_{n^{\prime}}$ 的值只和第$n^{\prime}$以后的值有关了，也就可以进行流式计算了。

我们来再看下水塘抽样的算法描述：

从S中抽取首1项放入「水塘」中
对于每一个S[j]项：
   随机产生一個范围从0到j的整数r
   若 r==0 则把水塘中的值换成S[j]项

表达的和式子（2）是同一个意思。

普遍情况：抽取k位幸运儿

这个按照以上去分步计算会很复杂，我们采用投机取巧的方法简化成两步：

• 证明在抽取k的情况下，每个人的概率仍然是相同的。
• 对只抽取一位幸运儿这种情况下把概率乘以$k$

首先证明：

从一个装有N个小球的桶中，有k个黑球，安排N个人去抽，那么每个人抽到黑球的概率是相同的。

把$N$个球排成一列有$N!$种方法.为了在第$n$个位置上放黑球,可先从$k$个黑球中取1个放在该位置上,有$k$种方法,再把剩下的$n-1$ 个球排成一排,有$(N-1)!$种排法,于是得到：

至此，可以沿用式（2）进行抽样，算法描述：

从S中抽取首k项放入「水塘」中
对于每一个S[j]项（j ≥ k）：
   随机产生一個范围从0到j的整数r
   若 r < k 则把水塘中的第r项换成S[j]项    #说明：此处的概率为简单情况中的k倍

总结

自此，主要总结了我自己对水塘抽样如何形成的一些思考。有了这些理论，代码就很好写了。

#EOF