随即抽样问题:
要求从N个元素中随机的抽取k个元素,其中N无法确定。
是在 《计算机程序设计与艺术》 中看到的这个题目,书中只给出了解法,没给出证明。
解决方法是叫Reservoir Sampling (蓄水池抽样)
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
证明:
每次都是以 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
故证明成立
分享到:
相关推荐
开源项目-miku-rsampling.zip,Simple reservoir sampling for the command line.
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
划分水库采样的持续学习不均衡 该存储库包含官方的PyTorch实施和ECCV2020论文的数据集。... title = "{Imbalanced Continual Learning with Partitioning Reservoir Sampling}" booktitle = {ECCV}, yea
libraryDependencies += "lgbt.princess" %% "reservoir-core" % "0.4.0" // the core library supporting synchronous reservoir sampling libraryDependencies += "lgbt.princess" %% "reservoir-akka-stream" % ...
os-fast-reservoir 快速近似水库采样的Python实现。 安装 $ pip install os-fast-reservoir 用法 原料药 from os_fast_reservoir import ReservoirSampling rs = ReservoirSampling(100) for i in range(1000):...
java random原始代码有储层的随机抽样 无需随机更换容器即可进行随机采样的代码。 它从包含n个项目的文件中随机选择k个项目的样本。 通常,n足够大,无法容纳到主存储器中。 此算法也适用于流数据 ...
随机抽样Java 8中针对使用容器进行随机采样的问题的一组算法。 储层采样是一类随机算法,用于从包含n项的列表S中随机选择k项的样本,其中n是很大或未知数。 通常, n足够大,以致该列表无法放入主内存中。...
reservoir_sampling(抽样) stack string tree two_pointers(二级指针?) 248个算法题 简单:64 中等:141 难:43 查看已经完成了多少题目 find . -name "*.java" | grep Medium | wc -l 五大算法: backtracking-...
抽样:Clojure中的随机抽样
mongodb-collection-sample 来自MongoDB集合的样本文档。 安装 npm install --save mongodb-collection-sample 例子 npm install mongodb lodash mongodb-collection-sample var sample = require ( 'mongodb-...
tsv-utils:eBay的TSV实用程序:用于大型表格数据文件的命令行工具。 过滤,统计,抽样,联接等
Contents List of symbols . . . . . . . . ....1 Introduction ....2 Statistical definitions ....2.1 Probability density function ....2.2 Statistical moments ....2.2.1 Expected value....2.2.2 Variance ....