最近在校论坛上看到了一个叫蓄水池(Reservoir Sampling
)抽样的问题,感觉很有趣,记录如下:
题目:要求从N个元素中随机的抽取k个元素,其中N无法确定。
解法:
Init : a reservoir with the size: k
for i= k+1 to N
M=random(1, i);
if( M < k)
SWAP the Mth value and ith value
end for
上述伪代码的意思是:先选中第1到k个元素,作为被选中的元素。然后依次对第k+1至第N个元素做如下操作:
每个元素都有k/x的概率被选中,然后等概率的(1/k)替换掉被选中的元素。其中x是元素的序号。
网上找到的证明,用数学归纳法证的:
每次都是以 k/i 的概率来选择
例: k=1000的话, 从1001开始作选择,1001被选中的概率是1000/1001,1002被选中的概率是1000/1002,与我们直觉是相符的。
接下来证明:
假设当前是i+1, 按照我们的规定,i+1这个元素被选中的概率是k/i+1,也即第 i+1 这个元素在蓄水池中出现的概率是k/i+1
此时考虑前i个元素,如果前i个元素出现在蓄水池中的概率都是k/i+1的话,说明我们的算法是没有问题的。
对这个问题可以用归纳法来证明:k < i <=N
1.当i=k+1的时候,蓄水池的容量为k,第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现在蓄水池的概率为 k/(k+1), 很明显结论成立。
2.假设当 j=i 的时候结论成立,此时以 k/i 的概率来选择第i个元素,前i-1个元素出现在蓄水池的概率都为k/i。
证明当j=i+1的情况:
即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候,此时任一前i个元素出现在蓄水池的概率都为k/(i+1).
前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中,②得保证第i+1次选择的时候不被替换掉
①.由2知道在第i+1次选择前,任一前i个元素出现在蓄水池的概率都为k/i
②.考虑被替换的概率:
首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 k/i+1,其次是因为随机替换的池子中k个元素中任意一个,所以不幸被替换的概率是 1/k,故
前i个元素(池中元素)中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1
则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/i+1
综合① ②,通过乘法规则
得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1
故证明成立
自己的思考:
很多人都会想,问什么这么做呢?这种方法是怎么想到的呢?我刚开始也很困惑,后来仔细想了一遍问题,就豁然开朗了。题目中明确规定N无法确定
,这就意味着,无论N或大或小,这N个元素都要被等概率的抽取出来。那么,可以这么考虑,N是一个动态增加的数字,例如:先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素,变成了120个元素等概率抽取10个,怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢?
其实很简单,再看一眼上面的算法,第x个元素被选中的概率为k/x,这个可以等价为有x个元素,等概率抽取k个元素,每个元素被抽中的概率。也就是说,每当元素数量增加1的时候,就要对所有元素等概率抽取一次,这样当然能保证目前元素数量下是等概率抽取,这也是元素数量增加后,下次概率计算的先决条件。
分享到:
相关推荐
蓄水池抽样》 Blog: 《结构之法 算法之道》 Something about bit op: Something about array rotate: A Linear Time Majority Vote Algorithm 题解: Maximum Gap: Something about largest-rectangle-in-histogram:...
蓄水池算法,又称Reservoir Sampling,是一种在未知大小的大数据流中随机抽取固定数量样本的算法。在LeetCode平台上,这个算法常被用于解决实际编程挑战,例如处理大规模无序数据集的问题。这里我们主要探讨蓄水池...
蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...
储备池计算(Reservoir Computing,简称RC)是一种新兴的机器学习方法,特别是在处理时间序列预测问题上表现出色。本文将详细解析"储备池神经网络预测混沌信号MATLAB实例"的相关知识点,以及如何利用MATLAB实现混沌...
本文探讨了在数据集大小未知的情况下进行随机抽样的问题,并提出了一种高效的方法——水库抽样算法(Reservoir Sampling Algorithm)。该算法能够在一次遍历过程中,利用常数空间复杂度选取一个不放回的随机样本,...
蓄水池算法,也称为Reservoir Sampling,是一种在未知大小的大数据流中随机抽取固定数量样本的算法。在LeetCode平台上,它可能被用于解决涉及概率抽样的问题。本项目"leetcode-ts-template"是一个专门为LeetCode挑战...
这个项目的核心是实现Reservoir Sampling算法,这是一种在大数据集上进行无偏随机抽样的算法,尤其适用于内存限制的环境。下面我们将深入探讨Reservoir Sampling算法、其原理以及在命令行中的应用。 Reservoir ...
本文将深入探讨Clojure中实现随机抽样的方法,主要关注Reservoir Sampling和Stream Sampling两种策略。 首先,让我们了解什么是随机抽样。随机抽样是指在不破坏总体分布的前提下,从一个较大的数据集中抽取一部分...
Android Reservoir是一个轻量级的库,专门为Android应用设计,用于高效、安全地存储和检索本地数据。这个库简化了应用程序在本地持久化数据的过程,无论是小规模的数据,如偏好设置,还是中等规模的数据,如JSON对象...
根据提供的信息,《Reservoir Engineering Handbook》是一本关于储层工程的专业书籍,主要涵盖了与石油、天然气等储层相关的基础知识及流体性质等内容。下面将基于标题、描述以及部分章节内容来详细阐述本书涉及的...
Vitter的水库采样算法(Reservoir Sampling)是一种在大数据集上进行随机抽样的高效算法,由Jeffrey Scott Vitter于1985年提出。这个算法在处理大数据流时特别有用,因为它允许在固定内存空间内对任意大小的数据流...
reservoir_sampling(抽样) stack string tree two_pointers(二级指针?) 248个算法题 简单:64 中等:141 难:43 查看已经完成了多少题目 find . -name "*.java" | grep Medium | wc -l 五大算法: backtracking-...
该文档中提到了几种具有代表性的取样算法,包括蓄水池取样(reservoir sampling)、简洁取样(concise sampling)、计数取样(count sampling)、链式取样(chain-sampling)和DV取样(DVsampling)等。蓄水池取样常...
2. **蓄水池(Reservoir)**:ESN的蓄水池层一般由大量的神经元构成,它们的连接权重是随机生成的,并保持不变。这种设计使得网络能够以内在的复杂动态行为处理输入序列。 3. **读出权重(Readout Weights)**:与...
fun和fun1分别是压力计算函数和压力导数计算函数。计算过程中可以改变不同参数的取值,绘制图形,研究各参数对压力响应的敏感性。敏感性分析时,各参数可输入5个、4个等不同数值。GUI界面清晰,处理方便,易于操作。...
### 地统计储层建模相关知识点 #### 标题:地统计储层建模(Geostatistical Reservoir Modeling) **地统计储层建模**是石油地质领域中的一个重要分支,它通过数学方法和统计技术来研究地下油气藏的空间分布特征。...
帝国理工大学地球科学与工程系的这份课程资料介绍了储层工程模拟的相关机会。该课程由J-P. Latham、J. Xiang和X. Garcia共同讲授,并在2009年的PERM会议上进行了分享。课程资料主要探讨了虚拟地质工作台(VGW)在储层...