未知总数的抽样如何保证相同概率

1.从未知的大量数中随机抽取一个数

解决:假设这个数为choice, 则对于第i个数,以1/i的概率替换它

choice = 1

以1/2的概率替换choice=2

以1/3的概率替换choice=3

直到数据遍历完毕

2.从未知的大量数中抽取出k个

解决:以k/i的概率让第i个数加入抽样集合,如果抽样集合已满,随机替换掉一个

假如要抽取10个

则1,2,3……10为初始化集合

对于11,以10/11的概率加入集合,并随机替换掉一个

对于12,以10/12的概率加入集合,并随机替换掉一个

直到数据遍历完毕

http://archive.cnblogs.com/a/1949762/

原文地址:https://www.cnblogs.com/yangyh/p/2180638.html