等概率放球

本文主要是介绍等概率放球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

等概率放球

蓄水池问题

【题目】
有一个机器按自然数序列的方式吐出球（1号球，2号球，3号球，……），你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。
设计一种选择方式，使得当机器吐出第N号球的时候（N>K），你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是$\frac{K}{N}$。

举一个更具体的例子，有一个只能装下10个球的袋子。
当吐出100个球时，袋子里有10个球，并且1~100号中的每一个球被选中的概率都是$\frac{10}{100}$；然后继续吐球。
当吐出1000个球时，袋子里有10个球，并且1~1000号中的每一个球被选中的概率都是$\frac{10}{1000}$；继续吐球。
当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是$\frac{10}{i}$，即吐球的同时，已经吐出的球被选中的概率也动态地变化。

算法思路

保证第i次选球时，前i个球被选入袋中的概率相同为$\frac{K}{i}$(i<=K时，全为1)。
本质上为蓄水池算法：动态变化等概率抽样——每次抽样(放球)时，每个球被抽中的概率都相等，但是每次这个概率数值会更改。
考虑第i次选球时，每个球放入袋中的概率为$\frac{K}{i}$；
第i个球只有这次放入袋中的机会，因此放入袋中的概率等于第i次选球概率，为$\frac{K}{i}$；
第i次在袋中的球被替换的概率为$\frac{K}{i}\times \frac{1}{K}=\frac{1}{i}$;
第i次在袋中的球被保留的概率为$1-\frac{1}{i}=\frac{i-1}{i}$
观察前i-1中的任意一个球个球，第i次留在袋中的概率为
$$(\frac{K}{K+1}\times \frac{K+1}{K+2}\times \frac{K+2}{K+3}\times ...\times \frac{i-2}{i-1}\times \frac{i-1}{i})=\frac{K}{i}$$
即袋中的球和第i个选球放入袋中的概率相同为$\frac{K}{i}$。

相应代码

# 蓄水池算法
import random# uniform rand 1~max
def rand(max):return int(random.random() * max) + 1def getKNumsRand(k, n):if n < 1 or k < 1:return Noneres = [0 for i in range(min(k, n))]# 前k个球直接进入袋中for i in range(1, len(res) + 1):res[i - 1] = i# 从k+1个球起for i in range(k + 1, n + 1):# 第i个球以k/i概率替换袋中的球if rand(i) <= k:res[rand(k) - 1] = ireturn res

小结

蓄水池算法保证每次抽样的公平性，对于第i次抽样，每个样本被抽中的概率相同——$\frac{K}{i}$，其中K为蓄水池容量。
最终每个样本被抽中的概率为$\frac{K}{N}$，其中N为总样本数。N可以不确定，换言之，可以一直抽样，随时喊停，也能保证抽样的等概率。
因此在许多题目都有涉及。

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！

这篇关于等概率放球的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---