知识卡片
碰撞估算依赖抽样模型
从n个等概率元素独立有放回抽样直到首次重复,首次碰撞通常在约 √(πn/2) 次抽样附近;示例以重复前不同元素数k计算 2k²/π,抽样次数期望为 O(√n)。实际需要支持均匀随机抽样与记录已见元素,成本应计入。
书中称该估计严格无偏,但 n=1 时 k恒为1、估计值为2/π而不是1,已构成反例;不能以期望抽样次数近似值的平方直接替代二阶矩。去掉最大最小样本后均值也改变估计性质。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
概率计数算法的实现 算法预期的执行时间为: 也就是说,while循环预期的执行次数为: 这个算法与生物学家用来估算有限空间内生物群体规模的标识再捕法很相似。显然,它不可能得到n的确切数值,因为2*k2/π不可能是个整数。但是2*k2/π是n的无偏估计,它的期望值等于n。 表10-1给出了该算法在大量
参考来源
- 位置:《算法技术手册》第10章《估算集合的大小》(spine1680;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1642.html;u291-ch10-004)。
- 结论依据:291全文及03450–03453代码、公式与表实读;n=1反例为直接推导。
- 原始内容:概率计数算法的实现 算法预期的执行时间为: 也就是说,while循环预期的执行次数为: 这个算法与生物学家用来估算有限空间内生物群体规模的标识再捕法很相似。显然,它不可能得到n的确切数值,因为2*k2/π不可能是个整数。但是2*k2/π是n的无偏估计,它的期望值等于n。 表10-1给出了该算法在大量