最近在校论坛上看到了一个叫蓄水池(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:...
蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...
MULTIGRID METHOD FOR RESERVOIR SIMULATION
reservoir engineering modelling opportunities
reservoir_sampling(抽样) stack string tree two_pointers(二级指针?) 248个算法题 简单:64 中等:141 难:43 查看已经完成了多少题目 find . -name "*.java" | grep Medium | wc -l 五大算法: backtracking-...
Android Reservoir存取本地数据
储备池神经网络预测混沌信号MATLAB实例
os-fast-reservoir 快速近似水库采样的Python实现。 安装 $ pip install os-fast-reservoir 用法 原料药 from os_fast_reservoir import ReservoirSampling rs = ReservoirSampling(100) for i in range(1000):...
fun和fun1分别是压力计算函数和压力导数计算函数。计算过程中可以改变不同参数的取值,绘制图形,研究各参数对压力响应的敏感性。敏感性分析时,各参数可输入5个、4个等不同数值。GUI界面清晰,处理方便,易于操作。...
开源项目-miku-rsampling.zip,Simple reservoir sampling for the command line.
Reservoir connectivity evaluation based on the reservoir architecture,尹太举,张昌民,Reservoir connection is a key factor for water flooding recovery. Ways for connection evaluation is though well ...
Simulation platform for pattern recognition based on reservoir computing with memristor networks_基于忆阻网络储层计算的模式识别仿真平台.pdf
很基础的一本油藏数值模拟教材,感兴趣的可以好好看看
学习建模的好教程,欢迎大家下载!
Good book about engineering
Application of FPGA to Real‐Time Machine Learning Hardware Reservoir Computers and Software Image Processing 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国...
Application of FPGA to Real‐Time Machine Learning Hardware Reservoir Computers and Software Image Processing 英文无水印原版pdf pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试...
Seismic low-frequency effects from fluid-saturated reservoir